A Multidimensional Complexity Onion
Today, we're going to do something magical.
But first, we're going to move through many, many different ideas in quick succession.
Hold on to your chopping boards, because this multidimensional complexity onion needs peeling.
Compact Graph Notation
The first thing we need to do is define a text-based notation for our graphs. While many exist- Graph6 being my personal favourite for its compactness- these are hardly human-readable. What we need is a specialised notation for our graphs that is easy to compute from a picture of a graph.
The way we do this is we start with a graph. For now, we will ignore graphs with loops. We identify the longest chain of vertices in this graph and write the number of vertices down.
Our example graph (in black) embedded on L3H (in yellow). Longest chain (graph backbone) coloured in red.
Following this, we open a bracket, and wrote down the numbers of the vertices that have branches coming off them. We number the backbone in such a way that the longest branch is attached to the lowest numbered vertex as we can manage, and that the numbers in general are as low as we can get them.
Our fully labelled graph. While 6(4,5) is also a valid labelling, it is incorrect as 6(2,3) has lower branch numbers overall.
We label loops in a similar manner- we write down the size of the largest loop, then follow it with the letter L to indicate a loop. We then list the branches as normal.
If a branch is multiple vertexes long, we indicate the number of vertices with a superscript number, e.g. 6(2,3²).
Branched side chains (can y'all tell I'm a chemist yet?) are indicated by a squared bracket, with the regular notation for the side chain inside: 12(5[4(2)]) indicates a chain of 12 and a chain of 4 connected by vertices 5 and 2 respectively.
A fully labelled graph of the chemical compound Norbornane. Hopefully it is evident as to why its label is 6L(1{4²}).
Bridging in loops is indicated in a similar manner, with curly braces indicating the connecting node and a power indicating the number of nodes (including the terminal node) in the bridge: 6L(1{4²}) is the graph of the chemical Norbornane.
More complicated examples can be thought up, but these will be more than sufficient for our purposes.
Proof by Induction
Now we're going to talk about a proof technique. We'rlve already seen one: Proof by Exhaustion, back in our post "Gettin' Griddy". Proof by Exhaustion is where you check every single case by hand, and make sure that each case is true. In Proof by Induction, however, we start with a base case (0), and prove that. We then prove that if the theorem holds for case N, it also holds for case N+1. By doing this, we prove that if it holds for 0, it holds for 1, and therefore holds for 2, and therefore holds for 3, and so on, and we also prove it holds for 0, therefore it holds for all cases N.
What we're actually about to do is not a Proof by Induction- we're instead going to construct a Proof by Induction, and prove that it's true by Exhaustion. Does that sound complicated? It actually isn't, bear with me.
How do we create new graphs?
We start with a base case- a single vertex. This obviously embeds onto the given lattice, as every lattice has more than 1 vertex (1 < ∞). Now, for the inductive step. We take an existing graph we know embeds, and, without loss of generality, attach a single embedded vertex to it. We then connect this vertex using every possible combination of embedded edges it can have. Finally, we wrote down all the graph codes of these graphs as given above, and cross off any duplicates. If we repeat this for all embeddable graphs of vertex number N, we can create a list of all graphs with vertex number N+1. As such, our proof is complete- we can now construct every possible embeddable graph of N vertexes.
Here is a graphical representation of the process on L3H:
Constructing every embeddable graph up to N=6 on L3H (in yellow) by Induction.
As it can be seen, it is easy to find all 5 embeddable graphs of 6 nodes on 3H in this manner- and it is much, much quicker than checking all 99 possible planar graphs! These graphs are 6(), 6L(), 5(2), 5(3), and 4(2,3). We only had to check 19 cases, not 99, so this is much more efficient! We'll calculate just how efficient in a later series of posts...
Completing L3H
So, we have a general procedure for finding all the lattice graphs for a particular lattice. Remember our table from the last post? Here it is in full:
A table showing the number of lattice embeddable graphs on L3H up to N=8.
As you can see, the number of lattice embeddable graphs is very small on L3H compared with the number of planar graphs. Unfortunately, there is no discernable pattern to the sequence, and it's also unknown to the Online Encyclopedia of Integer Sequences. However it is clear there should be some structure to it, as we have a procedure for constructing it!
What structure? Well, we don't actually know! But find out next time what we do know, where we'll be momentarily diving into some deeper graph theory, and also giving more information about what we can say about this wonderful topic.
But for now, some challenge homework. Using our procedure above, can you:
1 (Easy). Find all graphs up to N=8 that will embed on L3H? This is easy as I've given you both how many there are and I've done this for you up to N=6!
2 (Medium). Find all graphs up to N=8 that will embed on L3I, the Truncated Trihexagonal Lattice- shown in this post's header image?
3 (Hard). Find all graphs up to N=8 that will embed on L4S, the square lattice of connectivity 4 (shown in Gettin' Griddy)?
If anyone submits correct answers or an attempt at any of these by next week, and posts it in the comments or emails me (with a full derivation), I'll shout you out in next week's post! I'll also be incredibly impressed. :D
-Wolfie
