Skip to main content
4 of 5
added 243 characters in body
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

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

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

Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327