Infinite-dimensional hex

Question

Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they connect their assigned faces by a path (potentially using diagonal moves). Once a vertex is chosen, it cannot be chosen by any other player, and the game ends once every vertex has been chosen.

This game must always be won by at least one player. David Gale gives a simple proof here. If we restrict the notion of "adjacent" we can obtain a game more like Hex, which we can prove has a unique winner using a slick induction on $k$.

But what happens if we take $n = \omega$?

More formally, suppose we partition $[k]^\omega$ into $A_1, A_2, \ldots$. We say that two points $x,y$ are adjacent if $|x(i) - y(i)| \leq 1$ for each $i$. Does there necessarily exist an $i$ and a path $x_1, x_2, \ldots, x_n \in A_i$ such that $x_m$ is adjacent to $x_{m+1}$ for each $m$, $x_1(i) = 0$, and $x_n(i) = k-1$?

---

One reason to think this might hold up in the infinite-dimensional case is that it works when $k = 2$, which suggests that the infinite dimension isn't fundamentally a deal-breaker. If $k = 2$, then every pair of points is adjacent, so in order for us to fail each $A_i$ must either be a subset of $\left\{x : x(i) = 0\right\}$ or $\left\{x : x(i) = 1\right\}$. Without loss of generality we can assume the former. But then the constant function $x(i) := 1$ is not in any of the $A_i$.

Edit: the case $k = 3$ also works, although I found it a lot harder. (I doubt this proof is the best one. It is strikingly different in character from more typical fixed point arguments, which seems related to the fact that it produces paths of length exactly $3$. I doubt the idea will generalize, though I think this still provides more evidence that the claim is true.)

A partial assignment is an $a \in \left([k] \cup \left\{ *\right\}\right)^{\omega}$, and we say that $x$ satisfies $a$ if $\forall i : a(i) \in \left\{*, x(i)\right\}$. The partial assignments form a poset in the natural way ($a > a'$ iff satisfying $a'$ is easier than satisfying $a'$).

Say that a partial assignment is good if it never takes on the value $1$, and if whenever coordinate $i$ is unequal to $*$, there are no points satisfying the assignment which receive label $i$. It is easy to check that the intersection of any chain of good partial assignments is itself good, so there is some maximal good assignment $a$.

Define $x$ by $x(i) = 1$ if $a(i) = *$, $x(i) = a(i)$ otherwise. Let $i$ be the label of $x$. Because $a$ was good, coordinate $i$ cannot be set in $a$. Because $a$ was maximal, setting coordinate $i$ to $0$ must yield a bad assignment. This means that some point consistent with $a$ which has label $i$ and which has $i^{\text{th}}$ coordinate $0$. Similarly, there is some point consistent with $a$ which has label $i$ and which has $i^{\text{th}}$ coordinate $2$. But together with $x$, these three points form a path which has all of the desired properties.

Answer 1

It seems the claim is false, though I don't have a good sense for what the actual counterexample looks like. With luck, I've made an error somewhere.

Consider the normed space $\ell^{\infty}$. One can show that there is a Lipschitz retraction from the unit ball $[-1, 1]^{\omega}$ to the unit sphere.

Let $f$ be this retraction, let $k$ be some integer much greater than the Lipschitz constant of $f$, and consider my claim for $[k]^{\omega}$. We'll define an outcome of the game as follows:

For a point $x \in [k]^{\omega}$, consider the point $b(x) = \frac {2x}{k} - 1$ in the unit ball. By definition $f(b(x))$ has some coordinate in the interval $[-1, 1/k-1] \cup [1-1/k, 1]$. Let $i$ be one such coordinate, and assign the point $x$ the color $i$. I claim the resulting grid has no winning player.

Suppose for a contradiction that player $i$ won. That implies there is some sequence of adjacent points $x_1, x_2, \ldots, x_m$ all of color $i$ for which the $i^{\text{th}}$ coordinate goes from $0$ to $k-1$. The $i^{\text{th}}$ coordinate of $x_1$ is $0$, so the $i^{\text{th}}$ coordinate of $b(x_1)$ is $-1$ and hence the $i^{\text{th}}$ coordinate of $f(b(x_1))$ is also $-1$. Similarly, the $i^{\text{th}}$ coordinate of $f(b(x_m))$ is $1$. But since each $x_j$ is assigned color $i$, the $i^{\text{th}}$ coordinate of each $f(b(x_j))$ is in $[-1, 1/k-1] \cup [1 - 1/k, 1]$.

So there must be some $j$ such that $f(b(x_j)) \in [-1, 1/k-1]$ and $f(b(x_{j+1})) \in [1/k-1, 1]$. But since $x_j$ and $x_{j+1}$ are adjacent, $||b(x_j) - b(x_{j+1})||_{\infty} < 2/k$. Since $||f(b(x_j)) - f(b(x_{j+1}))||_{\infty} > 1 - 2/k$, this contradicts the assumption that $f$ has Lipschitz constant much less than $k$.