Conjetura de la litera

Conjetura en combinatoria probabilística

La conjetura de la litera (también escrita como conjetura de la litera ) es una afirmación de la teoría de la percolación , una rama de las matemáticas que estudia el comportamiento de los grupos conectados en un grafo aleatorio . La conjetura recibe su nombre por su analogía con una estructura de litera . Fue postulada por primera vez por Pieter Kasteleyn en 1985. ^{[1] Nikita Gladkov,} Igor Pak y Alexander Zimin publicaron en arXiv en octubre de 2024 una preimpresión que presentaba un contraejemplo propuesto para la conjetura . ^[2]

Descripción

La conjetura tiene muchas formulaciones equivalentes. ^[3] En la formulación más general, implica dos grafos idénticos , denominados "litera superior" y "litera inferior". Estos grafos son isomorfos , lo que significa que comparten la misma estructura. Se agregan aristas adicionales, denominadas "postes", para conectar cada vértice en la litera superior con el vértice correspondiente en la litera inferior.

A cada arista del gráfico se le asigna una probabilidad. Las aristas de la litera superior y sus aristas correspondientes de la litera inferior comparten la misma probabilidad. Las probabilidades asignadas a los postes pueden ser arbitrarias.

Luego se forma un subgrafo aleatorio del grafo de literas eliminando independientemente cada borde en función de la probabilidad asignada.

Enunciado de la conjetura

La conjetura de la litera establece que en el subgrafo aleatorio resultante, la probabilidad de que un vértice en la litera superior esté conectado a algún vértice en la litera superior es mayor o igual a la probabilidad de que esté conectado a , la copia isomorfa de en la litera inferior. ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y'}$ ${\displaystyle y}$

Interpretación y significado

La conjetura sugiere que es más probable que dos vértices de un grafo permanezcan conectados después de eliminar aleatoriamente algunos bordes si la distancia del grafo entre los vértices es menor. Esto es intuitivo, y preguntas similares para los paseos aleatorios y el modelo de Ising se resolvieron positivamente. ^{[4] [5]} La motivación original para la conjetura fue su implicación de que, en una percolación en la cuadrícula cuadrada infinita, la probabilidad de estar conectado a para es mayor que la probabilidad de estar conectado a . ^[4] ${\displaystyle (0,0)}$ ${\displaystyle (x,y)}$ ${\displaystyle x,y\geq 0}$ ${\displaystyle (0,0)}$ ${\displaystyle (x+1,y)}$

A pesar de su intuición, demostrar esta conjetura no es sencillo y es un área activa de investigación en la teoría de la percolación. ^[6] Se demostró para tipos específicos de grafos, como ruedas , ^{[7] grafos} completos , ^{[8] grafos} bipartitos completos y grafos con simetría local. ^[9] También se demostró en el límite para cualquier grafo. ^{[10] [11]} ${\displaystyle p\to 1}$

Referencias

1. van den Berg, Jacob; Kahn, Jeff (2001). "Una desigualdad de correlación para eventos de conexión en percolación". Anales de probabilidad . 29 (1): 123–126. doi :10.1214/aop/1008956324. JSTOR  2652916 . Consultado el 17 de diciembre de 2023 .
2. Nikita Gladkov; Ígor Pak; Aleksandr Zimin (3 de octubre de 2024). "La conjetura de la litera es falsa". arXiv : 2410.02545 [matemáticas.CO].
3. Rudzinski, James; Smyth, Clifford (2016). "Formulaciones equivalentes de la conjetura de la litera". Revista de matemáticas y estadística de Carolina del Norte . 2 : 23–28 . Consultado el 17 de diciembre de 2023 .
4. Häggström, Olle (1998). "Sobre una conjetura de Bollobás y Brightwell relativa a los paseos aleatorios en gráficos de productos". Combinatoria, probabilidad y computación . 7 (4): 397–401.
5. Häggström, Olle (2003). "Probabilidad en gráficos de literas". Actas de la FPSAC . 3 : 19–27.
6. Grimmett, Geoffrey R. (2022). "Problemas seleccionados en teoría de la probabilidad". Revista Europea de Combinatoria . arXiv : 2205.07318 .
7. Leandro, Madeleine (2009). «Sobre la conjetura de la litera» (PDF) . Självständiga arbeten i matematik . Consultado el 17 de diciembre de 2023 .
8. van Hintum, Peter; Lammers, Piet (2018). "La conjetura de la litera en el grafo completo". Revista Europea de Combinatoria . 76 : 175–177. arXiv : 1803.07647 . doi :10.1016/j.ejc.2018.10.002.
9. Richthammer, Thomas (2022). "Conjetura de Bunkbed para grafos bipartitos completos y clases relacionadas de grafos". arXiv : 2204.12931 [math.PR].
10. Hutchcroft, Tom; Kent, Alexander; Nizić-Nikolac, Petar (2023). "La conjetura de la litera se cumple en el límite p↑1" (PDF) . Combinatoria, probabilidad y computación . 32 (3). Cambridge University Press: 363–369. doi :10.1017/S096354832200027X. S2CID  263889353.
11. Hollom, Lawrence (2023). "Una nueva prueba de la conjetura de la litera en el límite p ↑1". arXiv : 2302.00031 .