Skip to main content
3 of 3
minor edit: wikipedia link + expand acronym
Ilya Nikokoshev
  • 15.1k
  • 12
  • 77
  • 129

The density hex

Gale famously showed that the determinacy of n-player, n-dimensional Hex is equivalent to the Brouwer fixed point theorem in n dimensions.

We can (and Gale does) view this as saying that if you d-color the vertices of a certain graph specifically, the graph with vertex set $[n]^d$ and two vertices $v, w$ adjacent iff the max norm of $v - w$ is 1 and all the nonzero components of $v - w$ have the same sign -- then there's a certain monochromatic path. Alternatively, you can think of d-coloring a d-dimensional $n \times \ldots \times n$ cube, and the determinacy of Hex/Brouwer fixed-point says that a certain "twisted path" must exist.

Here's what I want to know:

Is there a topological proof of the density version of the determinacy of Hex?

The density version ends up following from density Hales-Jewett, since combinatorial lines are paths in the underlying graph. But density Hales-Jewett is hard, and this seems like it should admit a proof along the lines of Gale's.

What I mean by the "density version" is: for any $\delta > 0$, and fixed n, for sufficiently large dimension d any choice of $\delta n^d$ moves must connect two opposite sides of the hypercube/d-dimensional Hex board. (I'm fairly sure this is the correct statement, but it's possible I'm wrong. Let me know if this is for some reason utterly trivial or false.)

Harrison Brown
  • 12.6k
  • 14
  • 70
  • 105