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.

We could rephrase the condition on the girth by requiring that the minimal number of vertices at a graph distance 4
from a given vertex in the subgraph be 24. Can 23 be attained? I found an infinite family of subgraphs that attain 22.

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 x1x2x3 (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)

Any assignment → {(a), (b), (c), (d), (e), (f)} yields a 4-regular induced subgraphs on the 4-dimensional grid
with girth = 8 provided any two consecutive integers are assigned to two neighbours in the following graph:

k = n ≥ 5
The maximal girth is at least 6, as attained 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. (Note that each vertex has degree 2 or 3.)



That means that the intersection of each unit 5-hypercube in the grid 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.
(While this is non-trivial for n = 5 (verified with a computer search), it is easily seen that the intersections of a
positive proportion of all 5-hypercubes with Γ must necessarily contain vertices of degree at least 4 for n ≥ 7.)

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

A general upper bound
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  . 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



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

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


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 orthotope.
A few iterations of this elimination process leaves 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 + x4x2 + 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: 2xz (mod 4) or 2yz - 1 (mod 4)}


The second one is the only one that lacks 3-dimensional symmetry. It has a "layer" through 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)}