Skip to main content
minor edit: wikipedia link + expand acronym
Source Link
Ilya Nikokoshev
  • 15.1k
  • 12
  • 77
  • 129

Gale (reference in the comments) famously showedfamously 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 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?

Is there a topological proof of the density version of the determinacy of Hex?

The density version ends up following from density Hales-JewettHales-Jewett, since combinatorial lines are paths in the underlying graph. But DHJdensity 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: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.)

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

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

added 392 characters in body
Source Link
Harrison Brown
  • 12.6k
  • 14
  • 70
  • 105

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

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 DHJ is hard, and this seems like it should admit a proof along the lines of Gale's.

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

Source Link
Harrison Brown
  • 12.6k
  • 14
  • 70
  • 105

The density hex

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 DHJ is hard, and this seems like it should admit a proof along the lines of Gale's.