Conjetura de la litera

Un ejemplo de gráfico de literas

La conjetura de la litera (también escrita como conjetura de la litera ) es un enunciado de la teoría de la percolación , una rama de las matemáticas que estudia el comportamiento de los clústeres conectados en un grafo aleatorio . La conjetura recibe su nombre por su analogía con la estructura de una litera . Fue planteada por primera vez por Pieter Kasteleyn en 1985. ^{[ 1 ]} En 2024, Nikita Gladkov, Igor Pak y Alexander Zimin presentaron un contraejemplo a la conjetura de la litera, demostrando que es falsa. ^{[ 2 ] [ 3 ] [ 4 ]}

La conjetura tiene muchas formulaciones equivalentes. ^{[ 5 ]} En la formulación más general, involucra dos grafos idénticos , denominados litera superior e inferior . Estos grafos son isomorfos , lo que significa que comparten la misma estructura. Se agregan aristas adicionales, llamadas postes , para conectar cada vértice de la litera superior con el vértice correspondiente de la litera inferior.

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

A continuación, se forma un subgrafo aleatorio del grafo de literas eliminando independientemente cada arista en función de la probabilidad asignada.

De forma equivalente, se puede suponer que todos los bordes tienen la misma probabilidad de eliminación.${\displaystyle 0<p<1}$. ^{[ 5 ]}

La conjetura de la litera afirma que, en el subgrafo aleatorio resultante, la probabilidad de que un vértice x en la litera superior esté conectado a algún vértice y en la litera superior es mayor o igual que la probabilidad de que x esté conectado a y ′ , la copia isomorfa de y en la litera inferior.

La conjetura sugiere que dos vértices de un grafo tienen más probabilidades de permanecer conectados después de eliminar aleatoriamente algunas aristas si la distancia del grafo entre los vértices es menor. Esto es intuitivo, y cuestiones similares para caminatas aleatorias y el modelo de Ising se resolvieron positivamente. ^{[ 6 ] [ 7 ]} La motivación original de la conjetura fue su implicación de que, en una percolación en la cuadrícula cuadrada infinita, la probabilidad de que (0, 0) esté conectado a ( x , y ) para x , y ≥ 0 es mayor que la probabilidad de que (0, 0) esté conectado a ( x + 1, y ) . ^{[ 6 ]}

A pesar de su carácter intuitivo, demostrar esta conjetura no es sencillo y constituye un área activa de investigación en la teoría de la percolación. ^{[ 8 ]} Se demostró para tipos específicos de grafos, como ruedas , ^{[ 9 ]} grafos completos , ^{[ 10 ]} grafos bipartitos completos y grafos con simetría local. ^{[ 11 ]} También se demostró en el límite p → 1 para cualquier grafo. ^{[ 12 ] [ 13 ]} Se han publicado contraejemplos de generalizaciones de la conjetura de la litera para la percolación de sitios, hipergrafos y grafos dirigidos . ^{[ 14 ]}