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 x_{1} + 2x_{2} + ... + nx_{n}
(mod 2n + 1) for the vertices (x_{1}, x_{2}, ..., x_{n}).
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 |
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
(x_{1}, ..., x_{n}) 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 x_{4} in we shall find the vertices
(x_{1}, x_{2}, x_{3}, x_{4}) that are to be included in our constructed graph Γ.
First, include all vertices satisfying x_{1} ≡ x_{2}
≡ x_{3} (mod 2).
Second, include the set of vertices satisfying one of these conditions, depending on x_{4}:
(a) x_{1} ≡ 0 (mod 2), x_{2} ≡ 1 (mod 2)
(b) x_{1} ≡ 1 (mod 2), x_{2} ≡ 0 (mod 2)
(c) x_{1} ≡ 0 (mod 2), x_{3} ≡ 1 (mod 2)
(d) x_{1} ≡ 1 (mod 2), x_{3} ≡ 0 (mod 2)
(e) x_{2} ≡ 0 (mod 2), x_{3} ≡ 1 (mod 2)
(f) x_{2} ≡ 1 (mod 2), x_{3} ≡ 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
x_{1} + ... + x_{n} = 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 G_{4} 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 (2^{u(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: |
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(G_{1}) = {(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" through it
as shown in this image. On both sides, it continues like G_{3}.
Vertex set:
v(G_{2}) = {(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 G_{1}, but it is
somewhat harder to visualize mentally.
Vertex set:
v(G_{3}) = {(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(G_{4}) = {(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)}