21
$\begingroup$

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.)

Improve this question
$\endgroup$
8
  • $\begingroup$ Actually, what is the density version of the determinacy of Hex? $\endgroup$
    – Ilya Nikokoshev
    Commented Dec 13, 2009 at 11:25
  • 2
    $\begingroup$ "Gale famously showed..." I did not know it. Any link/reference? $\endgroup$
    – Gil Kalai
    Commented Dec 13, 2009 at 12:17
  • 4
    $\begingroup$ David Gale, The game of hex and the Brouwer fixed-point theorem, American Mathematical Monthly, Dec 1979, 818-827. $\endgroup$
    – Konrad Swanepoel
    Commented Dec 13, 2009 at 12:21
  • 3
    $\begingroup$ @Harrison: can you move the statement of what you had in mind to the statement of question? $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Dec 13, 2009 at 17:01
  • 1
    $\begingroup$ I have found the Gale paper online: cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/… $\endgroup$
    – Kristal Cantwell
    Commented Dec 13, 2009 at 21:13

1 Answer 1

Reset to default
6
$\begingroup$

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 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.

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) It seems that we might have here an interesting high dimensional extension with some special significance to chosing each vertex with probability 1/d.

Improve this answer
$\endgroup$
6
  • $\begingroup$ "Note that the topological proof of the coloring theorem does not rely on assuming n being fixed and d is large. when d is fixed (two) and n is large the coloring result is correct but the density result is far from being correct." This is essentially what motivates the question -- it seems to suddenly change from a topological problem to a combinatorial one, and I'd be very interested to see a way of bridging the gap. Incidentally, the failure of the density version fixing d and varying n is because there are sets with positive measure but lots of connected components. $\endgroup$
    – Harrison Brown
    Commented Dec 14, 2009 at 20:14
  • $\begingroup$ The combination of a measure (in the wrong continuous density version) and fixed points (in the coloring version) makes me think of ergodic theory, but I don't know enough about ergodic theory to know if this is meaningful. As to your (#) statement, certainly any two consecutive vertices in the path lie in a combinatorial line, but three consecutive vertices can determine a comb. subspace of large dimension. I guess we can think of combinatorial lines as paths that remain locally comb. lines no matter what adjacency structure we put on them. Can we use this to derive DHJ from density hex? $\endgroup$
    – Harrison Brown
    Commented Dec 14, 2009 at 20:49
  • $\begingroup$ I think we can expect for n fixed (say n=3) and d large a simpler combinatorial proof with much better bounds. anyway I think the results on separating all cycles in [0,1]^n and their discrete analogues are relevant. Look here (and the links there) :gilkalai.wordpress.com/2009/05/27/… $\endgroup$
    – Gil Kalai
    Commented Dec 14, 2009 at 21:02
  • $\begingroup$ Huh -- Looking at the paper, I realize I heard Alon give a talk on the isoperimetric proof, and I even remember thinking "This might apply to this problem..." Apparently I then proceeded to forget about it entirely! But I don't think it's proved directly in either Bollobas et al or Alon-Klartag; their $G_\infty$ is slightly different from my graph and somewhat larger. But I'd be very surprised if the basic method didn't extend; I'll try it later. (Taking a break from mathematics today. Or so I'm telling myself...) $\endgroup$
    – Harrison Brown
    Commented Dec 15, 2009 at 11:46
  • $\begingroup$ Yes, your graph seems intermediate one between G_\infty considered by BKLO and G_1 considered by AK; and your question for G_1 is also interesting and does not seem to be known (and also for the specific graph you study). $\endgroup$
    – Gil Kalai
    Commented Dec 15, 2009 at 17:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .