Regular grid subgraphs of maximal girth

Abstract

The unit-distance graph on the $n$-dimensional integer lattice ${\mathbb{Z}}^n$ is called the $n$-dimensional grid. We attempt to maximize the girth of a $k$-regular (possibly induced) subgraph of the $n$-dimensional grid, and provide examples and bounds for selected values of $n$ and $k$, along with more general results. A few cases involving alternative lattices are also considered.

arXiv comment13 pages. In Section 3, an infinite family of examples in 4 dimensions is given in this version. It covers the examples given in the first version. Some other very minor edits also in Section 3, and the paragraph about "spread" at the end of Section 1 is made a bit more clear and concise