Non-induced grid subgraphs
by Jan Kristian Haugland

The n-dimensional grid is the unit-distance graph on the n-dimensional integer lattice n. What is the maximal girth of a cubic subgraph of the 3-dimensional grid?
If the subgraph is required to be induced, then the maximum is 10 (cf. the main Grid subgraphs page), but in the general case, we only know that it is either 12, 14 or 16.
Here is a collection of all examples I have found of cubic subgraphs of girth 12. There are three infinite families and five additional examples.
I have also included three 4-dimensional examples that attain a girth of 16.

Infinite family no. 1

Let f, g : → {0, 1}.
If z ≡ 0 (mod 3), then (x, y, z) and (x+1, y, z) are adjacent if x + y ≡ f(z/3) (mod 2), and (x, y, z) and (x, y+1, z) are adjacent if x + y ≡ g(z/3) (mod 2).
If z ≡ 1 (mod 3), then (x, y, z) and (x+1, y, z) are adjacent.
If z ≡ 2 (mod 3), then (x, y, z) and (x, y+1, z) are adjacent.
If x + y + z ≡ 0 (mod 2), then (x, y, z) and (x, y, z+1) are adjacent.

Infinite family no. 2

Let f : × → {0, 1} such that f(x, y) + f(x+1, y) ≤ 1 ∀ x, y.

(x, y, z) and (x+1, y, z) are adjacent if one of the following sets of conditions holds:
(i) z ≡ 0 (mod 2), x + y ≡ 0 or 2 (mod 3)
(ii) z ≡ 0 (mod 2), x + y ≡ 1 (mod 3), f((x+y-1)/3, z/2) = 0
(iii) z ≡ 1 (mod 2), x + y ≡ 1 (mod 3), f((x+y-1)/3, (z-1)/2) = 1

(x, y, z) and (x, y+1, z) are adjacent if one of the following sets of conditions holds:
(i) z ≡ 1 (mod 2), x + y ≡ 0 or 2 (mod 3)
(ii) z ≡ 1 (mod 2), x + y ≡ 1 (mod 3), f((x+y-1)/3, (z-1)/2) = 0
(iii) z ≡ 0 (mod 2), x + y ≡ 1 (mod 3), f((x+y-1)/3, z/2) = 1

(x, y, z) and (x, y, z+1) are adjacent if one of the following sets of conditions holds:
(i) z ≡ 0 (mod 2), x + y ≡ 1 or 2 (mod 3)
(ii) z ≡ 1 (mod 2), x + y ≡ 0 (mod 3)

Setting f(x, y) = 0 ∀ x, y gives a graph with the property that the number of vertices at a graph distance 6 from a given vertex v, minimized over all vertices v of the graph, is 84.
This is the highest value attained among all these graphs (in 3 dimensions), and could be seen as a measure of how close we are to finding a graph of girth 14, as such a graph would attain the value 96.

Infinite family no. 3

The description of this family is based on layers, which in this context means sets of edges joining vertices (x1, y1, z1) and (x2, y2, z2) where x1 + y1 + z1 = k and x2 + y2 + z2 = k + 1 for some k.
Within each layer, the connections depend only on the residues of x, y and z (mod 2). Thus is k is even, the possible edges are shown as gray lines in the following tile.



If k is odd, we apply the inverted labelling.



Here are the 18 possible patterns for the layers. Edges are black, non-edges are gray. A double arrow shows the "orientation" of each pattern.

"Dense" layers use 8 of the 12 possible edges of each tile. If the sets of hexagons that the edges form (in the projection - the layers are of course not actually flat) lie on straight lines, we call it a dense straight layer.

   

If the hexagons instead form a zigzag pattern, we call it a dense zigzag layer.

         

The complements of the dense straight layers are called sparse straight layers.

   

Likewise, the complements of the dense zigzag layers are called sparse zigzag layers.

         

In order to construct a graph, we start with a doubly infinite sequence {..., L-1, L0, L1, L2, ...} of dense straight layers.
In between them, we are going to insert 1 or 3 other layers, as we shall see soon. But first, we make sure the initial sequence satisfies two rules.

(a) These dense straight layers can only have two different orientations.
(b) If i is even, then Li and Li+1 must have different orientation.

If i is odd and Li and Li+1 have different orientation, then a single sparse straight layer is inserted between them. There are no restrictions on the orientation.
Otherwise, three layers are inserted between Li and Li+1, of which the first and the last must be identical. If i is odd and Li and Li+1 have the same orientation,
then the centre layer in the new three layers that are inserted must be dense straight with the same orientation as Li-1 and Li+2, and each of the other two must be sparse zigzag with the same orientation as the centre.
If i is odd and Li and Li+1 (necessarily) have different orientation, then the centre must be dense zigzag with different orientation than both Li and Li+1.
Each of the other two must be the sparse zigzag that is the complement of the centre.

Singular examples

The first singular example consists of 6 classes A, ..., F of vertices. Any translation along a vector in the lattice spanned by {[2, 1, -1], [-1, 1, 0], [0, 0, 2]} is an automorphism.

The neighbours of a vertex in class A are: A vertex in class B in positive y-direction, a vertex in class D in positive z-direction and a vertex in class F in negative x-direction.
The neighbours of a vertex in class B are: A vertex in class A in negative y-direction, a vertex in class C in positive y-direction and a vertex in class E in negative z-direction.
The neighbours of a vertex in class C are: A vertex in class B in negative y-direction, a vertex in class D in positive x-direction and a vertex in class F in positive z-direction.
The neighbours of a vertex in class D are: A vertex in class A in negative z-direction, a vertex in class C in negative x-direction and a vertex in class E in positive x-direction.
The neighbours of a vertex in class E are: A vertex in class B in positive z-direction, a vertex in class D in negative x-direction and a vertex in class F in positive x-direction.
The neighbours of a vertex in class F are: A vertex in class A in positive x-direction, a vertex in class C in negative z-direction and a vertex in class E in negative x-direction.

We can express this much shorter, like this:
AB (y+), D (z+), F (x-)
BA (y-), C (y+), E (z-)
CB (y-), D (x+), F (z+)
DA (z-), C (x-), E (x+)
EB (z+), D (x-), F (x+)
FA (x+), C (z-), E (x-)

The second singular example consists of 12 classes A, ..., L of vertices. Any translation along a vector in the lattice spanned by {[3, 3, -1], [-1, 1, 0], [0, 0, 2]} is an automorphism.

Applying the same shorthand notation as above, the neighbours of each vertex are given by:
AB (x+), G (z-), L (x-)
BA (x-), C (x+), H (z+)
CB (x-), D (y+), I (z-)
DC (y-), E (x+), J (z-)
ED (x-), F (x+), K (z+)
FE (x-), G (x+), L (z-)
GA (z+), F (x-), H (y+)
HB (z-), G (y-), I (y+)
IC (z+), H (y-), J (x+)
JD (z+), I (x-), K (y+)
KE (z-), J (y-), L (y+)
LA (x+), F (z+), K (y-)

The third singular example consists of 12 classes A, ..., L of vertices. Again, any translation along a vector in the lattice spanned by {[3, 3, -1], [-1, 1, 0], [0, 0, 2]} is an automorphism.

AB (x+), G (z-), L (x-)
BA (x-), C (x+), H (z+)
CB (x-), D (x+), I (z-)
DC (x-), E (x+), J (z-)
ED (x-), F (x+), K (z+)
FE (x-), G (x+), L (z-)
GA (z+), F (x-), H (y+)
HB (z-), G (y-), I (y+)
IC (z+), H (y-), J (y+)
JD (z+), I (y-), K (y+)
KE (z-), J (y-), L (y+)
LA (x+), F (z+), K (y-)

The fourth singular example consists of 12 classes A, ..., L of vertices. Any translation along a vector in the lattice spanned by {[3, 3, 0], [-1, 1, 0], [0, 0, 2]} is an automorphism.

AB (x+), F (x-), H (z-)
BA (x-), C (x+), I (z+)
CB (x-), D (y+), J (z-)
DC (y-), E (y+), K (z+)
ED (y-), F (y+), L (z-)
FA (x+), E (y-), G (z+)
GF (z-), H (x+), L (x-)
HA (z+), G (x-), I (y+)
IB (z-), H (y-), J (y+)
JC (z+), I (y-), K (y+)
KD (z-), J (y-), L (x+)
LE (z+), G (x+), K (x-)

The fifth singular example consists of 12 classes A, ..., L of vertices. Any translation along a vector in the lattice spanned by {[0, 1, -4], [1, 1, 0], [-1, 2, 1]} is an automorphism.
The vertex set of this graph has density 12/13 in 3, and it is the only known example that does not use all available vertices.

AB (x+), D (z+), K (z-)
BA (x-), C (x+), L (z-)
CB (x-), D (x+), F (z+)
DA (z-), C (x-), E (y-)
ED (y+), F (y-), H (z+)
FC (z-), E (y+), G (x+)
GF (x-), H (x+), J (z+)
HE (z-), G (x-), I (x+)
IH (x-), J (x+), L (z+)
JG (z-), I (x-), K (y-)
KA (z+), J (y+), L (y-)
LB (z+), I (z-), K (y+)

4 dimensions

I have found three cubic subgraphs of the 4-dimensional grid of girth 16. Each of them consists of 24 classes A, ..., X of vertices,
and any translation along a vector [x, y, z, w] such that xyzw (mod 2) and x + y + z + w ≡ 0 (mod 6) is an automorphism.

Example 1:
AB (x-), C (z+), W (z-)
BA (x+), F (x-), X (w+)
CA (z-), D (z+), G (x+)
DC (z-), E (w+), H (w-)
ED (w-), F (w+), K (z+)
FB (x+), E (w-), L (x-)
GC (x-), H (y-), M (x+)
HD (w+), G (y+), I (y-)
IH (y+), J (y-), O (w-)
JI (y+), K (z-), P (z+)
KE (z-), J (z+), L (y-)
LF (x+), K (y+), R (y-)
MG (x-), N (x+), S (y+)
NM (x-), O (w+), T (w-)
OI (w+), N (w-), P (x+)
PJ (z-), O (x-), Q (x+)
QP (x-), R (x+), U (z+)
RL (y+), Q (x-), V (y-)
SM (y-), T (z-), W (y+)
TN (w+), S (z+), U (z-)
UQ (z-), T (z+), V (w-)
VR (y+), U (w+), X (w-)
WA (z+), S (y-), X (y+)
XB (w-), V (w+), W (y-)

Example 2:
AB (y-), C (w+), W (w-)
BA (y+), F (z-), X (z+)
CA (w-), D (y+), G (w+)
DC (y-), E (x+), H (x-)
ED (x-), F (y+), K (x+)
FB (z+), E (y-), L (z-)
GC (w-), H (z-), M (w+)
HD (x+), G (z+), I (x-)
IH (x+), J (x-), O (z-)
JI (x+), K (x-), P (w+)
KE (x-), J (x+), L (w-)
LF (z+), K (w+), R (z-)
MG (w-), N (z+), S (w+)
NM (z-), O (y+), T (y-)
OI (z+), N (y-), P (y+)
PJ (w-), O (y-), Q (y+)
QP (y-), R (w+), U (y+)
RL (z+), Q (w-), V (z-)
SM (w-), T (x-), W (w+)
TN (y+), S (x+), U (y-)
UQ (y-), T (y+), V (x-)
VR (z+), U (x+), X (z-)
WA (w+), S (w-), X (x+)
XB (z-), V (z+), W (x-)

Example 3:
AB (x-), C (w+), W (w-)
BA (x+), F (z-), X (z+)
CA (w-), D (z+), G (w+)
DC (z-), E (x+), H (x-)
ED (x-), F (w+), K (x+)
FB (z+), E (w-), L (z-)
GC (w-), H (y-), M (w+)
HD (x+), G (y+), I (x-)
IH (x+), J (x-), O (w-)
JI (x+), K (x-), P (z+)
KE (x-), J (x+), L (y-)
LF (z+), K (y+), R (z-)
MG (w-), N (x+), S (w+)
NM (x-), O (y+), T (y-)
OI (w+), N (y-), P (y+)
PJ (z-), O (y-), Q (y+)
QP (y-), R (x+), U (y+)
RL (z+), Q (x-), V (z-)
SM (w-), T (z-), W (w+)
TN (y+), S (z+), U (y-)
UQ (y-), T (y+), V (w-)
VR (z+), U (w+), X (z-)
WA (w+), S (w-), X (y+)
XB (z-), V (z+), W (y-)

Back to Grid Subgraphs