3
$\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}\}.$$

For which $n\geq 2$ is there an orientation of $(\mathbb{Z}^n, E_n)$ such that for every two vertices $x,y\in \mathbb{Z}^n$ there is a directed path from $x$ to $y$?

$\endgroup$
9
$\begingroup$

Color the vertices of $\mathbb{Z}^n$ by black and white according to their parity. For all but one "direction" (by direction I mean the direction of $x-y$), orient the edges from white to black. Orient the edges of the remaining direction from black to white. Then, for any $x∈\mathbb{Z}^n$ with neighbour $y$, there is a directed path from $x$ to $y$ with length at most three. It follows that, for every two vertices $x,y∈\mathbb{Z}^n$ there is a directed path from $x$ to $y$.

$\endgroup$
3
$\begingroup$

Here is a somewhat different solution phrased in a slightly more colorful language. For $\mathbb{Z}^2$, draw a spiral starting from $(0,0)$, i.e. edges $(0,0)$ to $(1,0)$, $(1,0)$ to $(1,1)$, $(1,1)$ to $(0,1)$ to $(-1,1)$, etc. Then it is possible to go from $(0,0)$ to any other point by following the spiral.

Now draw a chimney $(n+1,0)$ to $(n,0)$ for $n \in \mathbb{N}$. Then it is possible to go from any point to $(0,0)$ by following the spiral until it crosses the chimney and then dropping down the chimney. Hence all points in $\mathbb{Z}^2$ are connected.

For $\mathbb{Z}^3$, connect all floors $\mathbb{Z}^2 \times k$ for $k \in \mathbb{Z}$ as above and connect the floors by two elevators, one going up, the other one going down, i.e. draw edges $(0,0,k)$ to $(0,0,k+1)$ and $(0,1,k)$ to $(0,1,k-1)$ for $k \in \mathbb{Z}$. Then $\mathbb{Z}^3$ is connected (go from the starting room to the elevator, change floors, go to the desired room).

The step from $\mathbb{Z}^n$ to $\mathbb{Z}^{n+1}$ is the same. (The remaining edges can be oriented randomly.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.