2
$\begingroup$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are direct neighbors if there is $k\in\{1,\ldots,n\}$ such that $|x_k-y_k|= 1$, and $x_i = y_i$ for all $i\in \{1,\ldots,n\}\setminus\{k\}$. Let $$E_n= \big\{\{x,y\}\in [\mathbb{Z}^n]^2: x,y \text{ are direct neighbors}\}.$$

If $G$ is an infinite graph, an $\omega$-Hamilton path is a bijection $f:\omega\to V(G)$ such that for all $n\in \omega$ we have $\{f(n),f(n+1)\}\in E(G)$.

It can easily be seen that there is a $\omega$-Hamilton path for $(\mathbb{Z}^2, E_2)$: start at $(0,0)$ and "spiral outwards", informally speaking.

For what $n>2$ is there a $\omega$-Hamilton path for $(\mathbb{Z}^n, E_n)$?

$\endgroup$
3
  • 4
    $\begingroup$ In "E. Vazonyi: Über Gitterpunkte des mehrdimensionalen Raumes. Acta Litt. Sci. Szeged 9, 163--173 (1939)", it is shown that there is such a path for every $n$ (as well as a Hamilton double ray, i.e. a Hamilton path that is infinite on both sides). $\endgroup$ Commented Jul 1, 2018 at 9:07
  • $\begingroup$ Could you add this as an answer so we can close this thread, please? Thanks! $\endgroup$ Commented Jul 1, 2018 at 20:00
  • $\begingroup$ Done, I also included a proof sketch for convenience. $\endgroup$ Commented Jul 2, 2018 at 10:33

1 Answer 1

4
$\begingroup$

In "E. Vazonyi, Über Gitterpunkte des mehrdimensionalen Raumes, Acta Litt. Sci. Szeged 9, 163-173 (1939).", it is shown that there is such a path for every $n$ (as well as a Hamilton double ray, i.e. a Hamilton path that is infinite on both sides).

Since the publication is in German, I include a short proof sketch:

It isnt hard to construct a Hamilton double ray $R$ in $\mathbb Z^2$. Now $\mathbb Z^{n-1} \times R$ is a spanning copy of $\mathbb Z^n$ in $\mathbb Z^{n+1}$ and by induction we can find a spanning copy of $\mathbb Z^2$ in $\mathbb Z^n$ for every $n >2$. A Hamilton path or double ray of this subgraph clearly is a Hamilton path or double ray of the $n$-dimensional grid.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .