Gettin' Griddy
So we have this infinite 2D factory floor, but are only allowed to place machines in neat rows and columns. How can we encode this in the language of Graph Theory?
Introducing: The Lattice.
--
What is a Lattice?
A Lattice Graph (in this context) is an infinite collection of vertices, joined in some predictable way by an infinite collection of edges. The vertices can be arranged like this...
The Infinite Square Lattice, L4S.
Like this...
The Infinite Triangular Lattice, L6T.
Or even like this!
The Infinite Snub Trihexagonal Lattice, L5H. Colours are to show similar regions. I am never drawing this again.
There are many, many, MANY lattices- far too many to list them all- but we'll focus on a few select examples.
Why do we care about lattices?
They encode all of the information we care about!
Well, I say that. Let's prove it.
Proposition 1: Lattices encode our row/column restriction
Certainly the square lattice above does. But what about generally? All the restriction really means is that there is some predictable order to our possible placings. As this is a defining quality of a lattice, we can say this condition holds.
This is technically a relaxation of our property, but it's a far more useful generalisation! We will call this property Periodicity.
Proposition 2: Lattices encode our 2D restriction
Again, this is pretty much obvious. As the definition of a (planar) Lattice includes the fact that it is 2D, this is trivially true. We will call this property Planarity.
Proposition 3: Lattices encode our length restriction
This is where things get interesting. It turns out that lattices don't include this restriction. However, it turns out that the general form of our theorem, which we're slowly building to, doesn't actually need this restriction! All the theorem requires is that each vertex of the lattice has the same connectivity, which is a much weaker condition. However, it has (almost) nothing to do with edge length. I say almost as it turns out that all lattices (that I know of) with a constant vertex connectivity have edge lengths from a very restricted set- usually there are only one or two kinds of edge length (if you're feeling brave, try to find me a counterexample. I have a feeling, though no proof, that constant vertex connectivity and periodicity together force a constant edge length). Either way, the connectivity of each vertex is by far the more important property to conserve. We will call this property Constant Connectivity.
That was some heavy maths. Have a cookie.
Lattice Names
I use an abbreviation scheme to distinguish the lattices I'm talking about in text. I will, from now on, always write LNX, where L indicates we mean a lattice, N is the connectivity of the lattice, and X is an identifier for the general shape of the lattice. S is usually a square-based lattice, H is a hexagonal-based lattice, T a triangular-based lattice, etc etc. The first time I mention a lattice by name, I'll include a picture so you can see it, and explain the abbreviation in the caption if it isn't obvious.
The next steps
Now we know what a lattice is, I'm going to outline our next steps. I won't actually do any of these here, as this post is very maths-heavy already, but I'd like to show you our road map going forwards.
In the next post, we'll take what we've learned about lattices and graphs and put the two together, forming our main, very general, theorem. From there, we'll focus in on a particular case, to glean as much detail and insight from this as we can. Finally, we will attempt to generalise our results, and in doing so, learn much more about the problem than we thought we could...
Hopefully, by now, you're starting to see things as a mathematician does. If not, take things back a step, or try and put this post into the context of our factory! What do Planarity, Constant Connectivity and Periodicity mean for our rules of the factory?
If you're ready to see our general theorem, tune in soon- but first, some homework. Can you list me all graphs that have less than or equal to 5 nodes, and fit on our infinite Square Lattice L4S? Here's a hint: there are 10 of them! Remember, a graph is the same as another if, when drawn without a lattice, they can look the same on a page.
If you're stuck with this, I'll show you how to do it in the next post- so stay tuned!
-Wolfie <3
