Gale [famously showed](http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/brouwer-hex.pdf) 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](http://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem), 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.)



The density hex
For a closely related question when you do not insist that all non zero components of v-w has the same sign, then the answer is known: See the following paper: B. Bollobas, G. Kindler, I. Leader, and R. O'Donnell, Eliminating cycles in the discrete torus, LATIN 2006: Theoretical informatics, 202{210, Lecture Notes in Comput. Sci., 3887, Springer, Berlin, 2006. Also: Algorithmica 50 (2008), no. 4, 446-454. This Graph is referred to as G\_\inf and there is a beautiful new proof via the Brunn Minkowski's theorem by Alon and Feldheim. For this graph a rather strong form of a density result follows, and the results are completely sharp.


The paper by Alon and Klartag <http://www.math.tau.ac.il/~nogaa/PDFS/torus3.pdf> is a good source and it also studies the case where we allow only a single non zero coordinate in v-u. An even sharper result is given [in another paper](http://www.math.tau.ac.il/~nogaa/PDFS/torusone1.pdf) by Noga Alon. There, there is a log n gap which can be problematic if we are interested in the case that n is fixed and d large. See also this [post](http://gilkalai.wordpress.com/2009/05/27/answer-to-test-your-intuition-3/).


As Harrison points out, the graph he proposes (that we can call the Gale-Brown graph) is in-between the two graphs. So the unswer is not known but we can hope that some discrete isoperimetric methods can be helpful. 


The statement is an isoperimetric-type result so this can be regarded as a quantitative version of the topological notion of connectivity. 


Two more remarks: 1) The Gale result seems to give an example of a graph where there might be a large gap between coloring number and fractional coloring. This is rare and an important other example is the Kneser graph where analyzing its chromatic number is a famous use (of Lovasz) of a topological method.


2) Hex is closely related to planar percolation and the topological property based on planar duality is very important in the study of planar percolation and 1/2 being the critical probability. (See eg [this paper](http://uk.arxiv.org/PS_cache/math/pdf/0508/0508580v2.pdf)) It seems that we might have here an interesting high dimensional extension with some special significance to chosing each vertex with probability 1/d. 


