Grid subgraphs
by Jan Kristian Haugland

Definition: The n-dimensional grid is the unit-distance graph on n.

Main problem: Given integers n and k satisfying n 2 and 3 k 2n, what is the maximal girth of a
k-regular induced subgraph of the n-dimensional grid, and how many such subgraphs attain it (up to isometry)?

It is assumed throughout that the null graph is not a valid example of a k-regular graph.

A general example: One of the simplest possible ways to construct a k-regular induced subgraph of the n-dimensional
grid is to give k + 1 permissible residues of x1 + 2x2 + ... + nxn (mod 2n + 1) for the vertices (x1, x2, ..., xn).
If a subgraph thus constructed does not have any cycles of length 4, the girth must in fact be equal to 10.
For k = 3, 4, 5, 6, 7, 8, 9 and 10, the smallest n that allows this is 3, 5, 9, 14, 21, 28, 36 and 48 respectively.
For (n, k) = (3, 3) and (5, 4), girth = 10 is optimal, so the construction is both simple and potentially powerful.

Results in brief:

k = 3

k = 4

k = 5

k = 6

k = 7

n = 2

4

4

n = 3

10

6

4

4

n = 4

12

8

4

4

4

n = 5

16

10

6

6

4

n = 6

?

12

6 or 8

8

4


Results - details: The cases are gathered in sections according to the sign of n - k.

Section A: k > n

If n is odd and k = n+1, then the maximal girth is 6, which is attained by only
one k-regular induced subgraph (up to isometry). Otherwise, the maximal girth is 4.

Proof: If there is a pair u, v of neighbouring vertices that in total have more than 2n-2 neighbours not on the
line through u and v, then it is immediate by the pigeonhole principle that there is a 4-cycle through u and v.
This is the case for any pair of neighbours if k is at least n+2, and then the girth must be equal to 4.

If k = n+1, then it may be possible to avoid such pairs, but only if the neighbours of each vertex match up in antipodal
pairs, which means that k must be even, and so n must be odd. Otherwise, the girth must still be equal to 4.

If n is odd and k = n+1, let us assume that we can avoid 4-cycles. Starting with one vertex and its paired up neighbours,
we find that there is only one way to do each extension (i.e., adding the neighbours of a vertex). It follows that there is
at most one (n+1)-regular induced subgraph of the n-dimensional grid without 4-cycles up to isometry.
And such a thing exists: Let (x1, ..., xn) be a vertex if and only if ∑ (-1)xi = ± 1. The girth is 6.

Section B: k = n

n = 3, k = 3
There are four different cubic induced subgraphs of the 3-dimensional grid with girth = 10 (which
is optimal) up to isometry. A description of each one is given in the appendix of this page.

A proof of this result can be found here:
Classification of certain subgraphs of the 3-dimensional grid, J. Graph Theory 42(2003), 34-60.

n = 4, k = 4
If we have a 4-regular induced subgraph Γ of the n-dimensional grid, there must exist unit
n-hypercubes in the grid such that their intersection with Γ have at least as many edges as vertices
(and at least one), hence a cycle. In the case n = 4, it follows that the girth of Γ is at most 8.
Here is a way to construct infinitely many different examples for which this is attained.

For every fixed x4 in we shall find the vertices (x1, x2, x3, x4) that are to be included in our constructed graph Γ.

First, include all vertices satisfying x1 ≡ x2 ≡ x3 (mod 2).

Second, include the set of vertices satisfying one of these conditions, depending on x4:

(a) x1 ≡ 0 (mod 2), x2 ≡ 1 (mod 2)
(b) x1 ≡ 1 (mod 2), x2 ≡ 0 (mod 2)
(c) x1 ≡ 0 (mod 2), x3 ≡ 1 (mod 2)
(d) x1 ≡ 1 (mod 2), x3 ≡ 0 (mod 2)
(e) x2 ≡ 0 (mod 2), x3 ≡ 1 (mod 2)
(f) x2 ≡ 1 (mod 2), x3 ≡ 0 (mod 2)

Two consecutive values of x4 can have the sets corresponding to two neighbours in the figure:



There are infinitely many ways to walk around in the figure, which gives infinitely
many 4-regular induced subgraphs on the 4-dimensional grid with girth = 8.

k = n > 4
The maximal girth is at least 6, as achieved by the graph with vertex set given by x1 + ... + xn = 0 or 1.
So let us assume that Γ is an n-regular induced subgraph of the n-dimensional grid with girth 8.
There must exist unit 5-hypercubes in the grid with at least 5/4 as many edges as vertices (and not zero)
from Γ. But up to isometry, there is only one induced subgraph of the unit 5-hypercube with this property
and girth at least 8, namely the one shown here. The edges in the "4th" and "5th" dimension are not drawn.



That means that the intersection of each unit 5-hypercube with Γ - except possibly for a subset of density 0 -
must be isometric to it. This is only possible for n = 6. So for all other values 5, the maximal girth is 6.

Up to isometry, there is only one 6-regular induced subgraph Γ of the 6-dimensional grid with girth = 8.
It is closely related to G4 from the case k = n = 3 (cf. the appendix). The vertex set of the latter can be
defined by (x, y, z) ≡ (a, b, c) (mod 4) for one out of 40 points (a, b, c) with 0 a, b, c < 4. For each
one, replace 0 by (0, 0), 1 by (0, 1), 2 by (1, 1) and 3 by (1, 0). E.g., (0, 3, 2) becomes (0, 0, 1, 0, 1, 1).
We can now define Γ to have vertices congruent to one of these points (mod 2). (Or we can think of
the 40 points as the 6-bit binary representations of 0, 1, 3, 4, 6, 10, 11, 12, 13, 15, 17, 18, 21, 22, 23,
24, 25, 26, 28, 31, 32, 35, 37, 38, 39, 40, 41, 42, 45, 46, 48, 50, 51, 52, 53, 57, 59, 60, 62 and 63.)

Section C: k < n

Upper bounds
By estimating the smallest integer r such that the number of vertices at a graph distance r
from a fixed vertex is larger in a k-regular tree than in the n-dimensional grid, one can
deduce that an upper bound for the girth is given by 2n f(k) where f(x) is the inverse function of

1 + x (2u(x) u(x)-2u(x) (1-u(x))-(1-u(x)) (x-u(x))-(x-u(x)))1/x

for u(x) = 1 + x - (1 + x2)1/2. The first few values of f are:
f(3) = 4.672270, f(4) = 2.321195, f(5) = 1.568570, f(6) = 1.193914.
For larger x, f(x) is approximately 2(e/(x-1) + (e/(x-1))3/3).

When k is almost as large as n, we can do slightly better. Up to isometry, there are only two
induced subgraphs of the unit 6-hypercube with (at least one vertex,) at least 5/4 as many
edges as vertices and girth 10. Both have exactly 5/4 as many edges as vertices and
girth = 10. It follows immediately that the maximal girth of a k-regular induced subgraph
of the n-dimensional grid is at most 8 for n 6 and k > 5n / 6. A closer investigation of those
two subgraphs of the unit 6-hypercube shows that the result also holds for n = 6, k = 5.

An alternative approach is to count the number of edges in the grid joining a vertex at
a graph distance 2 from a fixed vertex v in the subgraph and a vertex of the grid at a
graph distance 3 from v in the grid. It can be shown that the girth is at most 6 when

-4n2k + 4nk2 + k3 - 8n2 + 6nk - 8k2 + 8n + 2k > 0

when k is even and

-4n2k + 4nk2 + k3 - 8n2 + 6nk - 8k2 + 10n + 2k > 4

when k is odd, i.e., when k > (0.8284... + o(1)) n.
It is of course possible to extend this, e.g., by counting pairs of vertices such that
one has graph distance 2 in the subgraph and the other one has graph distance 4 in
the grid from a fixed vertex. But I have not explored the possibilities here very far.

n = 4, k = 3
The following graph has girth = 12. The vertex set consists of

(x1, x2, x3, x4)
(x1 + 1, x2, x3, x4)
(x1 + 2, x2, x3, x4)
(x1 - 1, x2, x3, x4)
(x1, x2 - 1, x3, x4)
(x1 + 1, x2, x3 + 1, x4)
(x1, x2 - 1, x3, x4 + 1)
(x1 + 2, x2 + 1, x3, x4)

for every (x1, x2, x3, x4) satisfying

x1 ≡ x2 (mod 2)
x3 ≡ x4 (mod 2)
x1 + 3x2 + 3x3 - x4 ≡ 0 (mod 5)

Is there a 3-regular induced subgraph of the 4-dimensional grid with girth at least 14?

n = 5, k = 3
The following graph has girth = 16. The vertex set consists of

(x1, x2, x3, x4, x5)
(x1 + 1, x2, x3, x4, x5)
(x1, x2 + 1, x3, x4, x5)
(x1, x2 - 1, x3, x4, x5)
(x1 + 1, x2, x3, x4 + 1, x5)
(x1 + 1, x2, x3, x4 - 1, x5)
(x1, x2 + 1, x3 + 1, x4, x5)
(x1, x2 + 1, x3 - 1, x4, x5)
(x1, x2 - 1, x3, x4, x5 + 1)
(x1, x2 - 1, x3, x4, x5 - 1)
(x1, x2 + 2, x3 - 1, x4, x5)
(x1, x2 - 2, x3, x4, x5 + 1)

for all (x1, x2, x3, x4, x5) satisfying

x3 + x4 + x5 ≡ 0 (mod 3)
x1 + x3 - x4 ≡ 0 (mod 3)
x2 ≡ 0 (mod 3)
x1 + x2 ≡ 0 (mod 2)

n = 5, k = 4
The induced subgraph with vertex set given by

x1 + 2x2 + 3x3 + 4x4 + 5x5 ≡ 1, 3, 4, 5 or 9 (mod 11)

has girth = 10, and this is best possible. (Note that the permissible residues are
exactly the quadratic residues, but there are of course other, equivalent possibilities.)

Here is another one with girth = 10: (x1, x2, x3, x4, x5) is a vertex if

(x1 - x5, x2 - x5, x3 - x5, x4 - x5) ≡ (0, 0, 0, 0), (1, 0, 0, 0), (2, 0, 0, 0),
(1, 1, 0, 0), (1, 2, 0, 0), (1, 1, 1, 0), (0, 2, 1, 0), (0, 1, 2, 0), (1, 1, 2, 0),
(2, 1, 2, 0), (2, 0, 0, 1), (0, 2, 0, 1), (2, 0, 1, 1), (1, 1, 1, 1), (0, 2, 1, 1),
(0, 0, 2, 1), (1, 0, 2, 1), (2, 0, 2, 1), (0, 1, 2, 1), (0, 2, 2, 1), (2, 0, 0, 2),
(2, 1, 0, 2), (2, 2, 0, 2), (1, 0, 1, 2), (1, 1, 1, 2), (0, 2, 1, 2), (1, 2, 1, 2),
(2, 2, 1, 2), (0, 1, 2, 2) or (2, 2, 2, 2) (mod 3).

Are these the only 4-regular induced subgraphs of the 5-dimensional grid with girth equal to 10, up to isometry?

The proof that the girth can not exceed 10 requires some calculation, but here is the basic idea.
We start with a set S of potentially admissible intersections of a 4-regular induced subgraph with a unit
5-hypercube in the grid. Assuming that the girth is at least 12, we can argue that each element in S must
have as many edges as vertices (other configurations may occur, but with density 0). Now we can
eliminate from S any element that can not be "extended", regardless of how it is oriented, in both positive
and negative x1-direction to form a potentially admissible intersection with a 3×1×1×1×1 sized "prism".
A few iterations of this elimination process will leave S empty.

n = 6, k = 4
The following graph has girth = 12. The vertex set consists of

(x1,     x2, x3, x4,     x5, x6)
(x1 + 1, x2, x3, x4,     x5, x6)
(x1 + 2, x2, x3, x4,     x5, x6)
(x1, x2,     x3, x4 + 1, x5, x6)
(x1, x2 + 1, x3, x4 + 1, x5, x6)
(x1, x2 + 2, x3, x4 + 1, x5, x6)
(x1, x2, x3,     x4 + 2, x5, x6)
(x1, x2, x3 + 1, x4 + 2, x5, x6)
(x1, x2, x3 + 2, x4 + 2, x5, x6)

for all (x1, x2, x3, x4, x5, x6) satisfying

x1 + x2 + x3 ≡ 0 (mod 3)
x4 + x5 + x6 ≡ 0 (mod 3)
x1 + x4 ≡ x2 + x5 (mod 3)

Appendix
The images were created with POV-Ray.

The four optimal subgraphs in the case n = 3, k = 3


The first one has a very simple structure indeed. With this image, no further explanation should be necessary.
Vertex set: v(G1) = {(x, y, z) 3: 2x ≡ z (mod 4) or 2y ≡ z - 1 (mod 4)}


The second one is the only one that lacks 3-dimensional symmetry. It has a "layer" trough it as shown in this image. On both sides, it continues like G3.
Vertex set: v(G2) = {(x, y, z) 3: x + 3y + 5z 3 and ≡ 2, 3, 4 or 6 (mod 7) or x + 3y + 5z 0 and ≡ 0, 1, 4 or 6 (mod 7)}


The third one has a structure that is as simple as that of G1, but it is somewhat harder to visualize mentally.
Vertex set: v(G3) = {(x, y, z) 3: x + 2y + 3z ≡ 0, 1, 2 or 4 (mod 7)}


The last, and perhaps the most complicated one, can be constructed using "building blocks" like this one.
Vertex set: v(G4) = {(x, y, z) 3: (x, y, z) or (x + 2, y + 2, z + 2) ≡ (0, 0, 0), (2, 0, 0), (3, 0, 0), (0, 1, 0), (2, 1, 0), (0, 2, 0), (1, 2, 0),
(2, 2, 0), (1, 3, 0), (3, 3, 0), (0, 0, 1), (1, 0, 1), (1, 1, 1), (2, 1, 1), (3, 1, 1), (0, 2, 1), (3, 2, 1), (1, 3, 1), (2, 3, 1) or (3, 3, 1) (mod 4)}