21 votos

El hexágono de densidad

Gale famosamente mostró que la determinabilidad de Hex de n jugadores y n dimensiones es equivalente al teorema del punto fijo de Brouwer en n dimensiones.

Podemos (y Gale lo hace) ver esto como si dijéramos que si se colorean con d los vértices de un cierto grafo en concreto, el grafo con conjunto de vértices $[n]^d$ y dos vértices $v, w$ adyacentes si la norma máxima de $v - w$ es 1 y todos los componentes no nulos de $v - w$ tienen el mismo signo entonces hay un cierto camino monocromático. Alternativamente, puedes pensar en d-colorear un d-dimensional $n \times \ldots \times n$ cubo, y la determinabilidad del punto fijo de Hex/Brouwer dice que debe existir un cierto "camino torcido".

Esto es lo que quiero saber:

¿Existe una prueba topológica de la versión de densidad de la determinación de Hex?

La versión de la densidad se deriva de la densidad Hales-Jewett ya que las líneas combinatorias son caminos en el grafo subyacente. Pero la densidad de Hales-Jewett es difícil, y esto parece que debería admitir una prueba del tipo de la de Gale.

Lo que quiero decir con la "versión de densidad" es: para cualquier $\delta > 0$ y n fijo, para una dimensión d suficientemente grande cualquier elección de $\delta n^d$ los movimientos deben conectar dos lados opuestos del hipercubo/tablero hexagonal dimensional. (Estoy bastante seguro de que esta es la afirmación correcta, pero es posible que me equivoque. Avísame si por alguna razón esto es totalmente trivial o falso).

6voto

Pierre Spring Puntos 2398

Para una cuestión estrechamente relacionada, cuando no se insiste en que todos los componentes no nulos de v-w tengan el mismo signo, entonces se conoce la respuesta: Véase el siguiente artículo: B. Bollobas, G. Kindler, I. Leader, y R. O'Donnell, Eliminating cycles in the discrete torus, LATIN 2006: Theoretical informatics, 202{210, Lecture Notes in Comput. Sci., 3887, Springer, Berlín, 2006. También: Algorithmica 50 (2008), no. 4, 446-454. Este grafo se denomina G_ \inf y existe una nueva y bella demostración a través del teorema de Brunn Minkowski por Alon y Feldheim. Para este gráfico se obtiene una forma bastante fuerte de un resultado de densidad, y los resultados son completamente nítidos.

El artículo de Alon y Klartag http://www.math.tau.ac.il/~nogaa/PDFS/torus3.pdf es una buena fuente y también estudia el caso en el que sólo permitimos una única coordenada no nula en v-u. Se da un resultado aún más agudo en otro documento por Noga Alon. Allí, hay una brecha log n que puede ser problemática si estamos interesados en el caso de que n sea fijo y d grande. Véase también Correo electrónico: .

Como señala Harrison, el gráfico que propone (que podemos llamar gráfico de Gale-Brown) se encuentra entre los dos gráficos. Así que no se conoce la respuesta, pero podemos esperar que algunos métodos isoperimétricos discretos puedan ser útiles.

La afirmación es un resultado de tipo isoperimétrico, por lo que puede considerarse una versión cuantitativa de la noción topológica de conectividad.

Dos observaciones más: 1) El resultado de Gale parece dar un ejemplo de un grafo en el que puede haber una gran diferencia entre el número cromático y la coloración fraccionaria. Esto es raro y otro ejemplo importante es el grafo de Kneser donde analizar su número cromático es un uso famoso (de Lovasz) de un método topológico.

2) Hex está estrechamente relacionado con la percolación planar y la propiedad topológica basada en la dualidad planar es muy importante en el estudio de la percolación planar y 1/2 es la probabilidad crítica. (Véase por ejemplo este documento ) Parece que podríamos tener aquí una interesante extensión de alta dimensión con algún significado especial para elegir cada vértice con probabilidad 1/d.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X