Skip to main content
forgot closing curly bracket \}
Source Link

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)$$\{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)$?

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)$?

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)$?

Source Link

$\omega$-Hamilton paths in $\mathbb{Z}^n$

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)$?