Skip to main content
2 of 3
added 392 characters in body
Harrison Brown
  • 12.6k
  • 14
  • 70
  • 105

The density hex

Gale (reference in the comments) 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 DHJ 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