Return to Answer

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.

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.

I do not think that we can expect a topological proof. 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. When n is fixed and d is large the nature of the problem becomes similar to density Hales Jewett (while weaker) since (#)the paths in the graphs are not so different from combinatorial lines(#).

(Of course, if the question is "Is there a topological proof in the literature then I am quite certain that answer is no.)

The problem is interesting as it is a problem of a type "can we expect a method X leads to a solution of problem Y". Definite answers and even formal ways to pose the questions appear to be very hard. On the other hand, some heuristic arguments can be useful. But I am not aware of many such questions/heuristic answers in the literature.

Regarding my heuristic argument, the statement between the two (#)s looks especially questionable. But even if it is not the case that paths in the graph (when n is fixed and d very large) are "similar" to combinatorial lines, I would still regard the possibility of a topological proof rather unlikely.

Indeed the answer to the problem (if I understqanf it correctly) 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. The paper by Alon and Klartag http://www.math.tau.ac.il/~nogaa/PDFS/torus3.pdf is a good source. There is a beautiful new proof via the Brunn Minkowski's theorem by Alon and Feldheim.

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

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.

I do not think that we can expect a topological proof. 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. When n is fixed and d is large the nature of the problem becomes similar to density Hales Jewett (while weaker) since (#)the paths in the graphs are not so different from combinatorial lines(#).

(Of course, if the question is "Is there a topological proof in the literature then I am quite certain that answer is no.)

The problem is interesting as it is a problem of a type "can we expect a method X leads to a solution of problem Y". Definite answers and even formal ways to pose the questions appear to be very hard. On the other hand, some heuristic arguments can be useful. But I am not aware of many such questions/heuristic answers in the literature.

Regarding my heuristic argument, the statement between the two (#)s looks especially questionable. But even if it is not the case that paths in the graph (when n is fixed and d very large) are "similar" to combinatorial lines, I would still regard the possibility of a topological proof rather unlikely.

I do not think that we can expect a topological proof. 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. When n is fixed and d is large the nature of the problem becomes similar to density Hales Jewett (while weaker) since (#)the paths in the graphs are not so different from combinatorial lines(#).

(Of course, if the question is "Is there a topological proof in the literature then I am quite certain that answer is no.)

The problem is interesting as it is a problem of a type "can we expect a method X leads to a solution of problem Y". Definite answers and even formal ways to pose the questions appear to be very hard. On the other hand, some heuristic arguments can be useful. But I am not aware of many such questions/heuristic answers in the literature.

Regarding my heuristic argument, the statement between the two (#)s looks especially questionable. But even if it is not the case that paths in the graph (when n is fixed and d very large) are "similar" to combinatorial lines, I would still regard the possibility of a topological proof rather unlikely.

Indeed the answer to the problem (if I understqanf it correctly) 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. The paper by Alon and Klartag http://www.math.tau.ac.il/~nogaa/PDFS/torus3.pdf is a good source. There is a beautiful new proof via the Brunn Minkowski's theorem by Alon and Feldheim.

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