Gráfico de forzamiento

En teoría de grafos , un grafo forzante es aquel cuya densidad determina si una secuencia de grafos es cuasialeatoria. El término fue acuñado por primera vez por Chung, Graham y Wilson en 1989. ^{[ 1 ]} Los grafos forzantes desempeñan un papel importante en el estudio de la pseudoaleatoriedad en secuencias de grafos.

La conjetura de forzamiento afirma que los grafos de forzamiento son precisamente los grafos bipartitos cíclicos. Se ha descrito como "uno de los principales problemas abiertos en combinatoria extremal ". ^{[ 2 ]}

Sea t ( H , G ) = ⁠ # copias etiquetadas de H en G / v ( G ) ^{v ( H )} ⁠ , conocida como la densidad de subgrafos (en particular, t ( K ₂ , G ) es la densidad de aristas de G ). Una secuencia de grafos { G _n } se denomina cuasialeatoria si, para todos los grafos H , la densidad de aristas t ( K ₂ , G _n ) se aproxima a algún p y t ( H , G _n ) se aproxima a p ^e(H) a medida que n aumenta, donde e ( H ) es el número de aristas en H . Intuitivamente, esto significa que una secuencia de grafos con una densidad de aristas dada tiene el número de homomorfismos de grafos que se esperaría en una secuencia de grafos aleatoria. Un grafo F se denomina forzante si para todas las secuencias de grafos { G _n } donde t ( K ₂ , G _n ) se aproxima a p cuando n tiende a infinito, { G _n } es cuasialeatorio si t ( F , G _n ) se aproxima a p ^{e ( F )} . En otras palabras, se puede verificar que una secuencia de grafos es cuasialeatoria simplemente comprobando la densidad de homomorfismos de un solo grafo. ^{[ 3 ]}

Existe una segunda definición de grafos forzantes que utiliza el lenguaje de los grafones . Formalmente, un grafo se denomina forzante si todo grafón W tal que t ( F , W ) = t ( K² _, W ) ^{e ( F )} es constante. Intuitivamente, tiene sentido que estas definiciones estén relacionadas. El grafón constante W ( x , y ) = p representa el grafo aleatorio de Erdős-Rényi G ( n , p ) , por lo que cabría esperar que tuviera una estrecha relación con los grafos cuasialeatorios. De hecho, estas definiciones son equivalentes.

El primer grafo forzante a considerar es el 4-ciclo C ₄ , ya que guarda una estrecha relación con otras condiciones de cuasialeatoriedad. En el mismo artículo, Chung, Graham y Wilson demostraron que todo ciclo par C _{2 t} y los grafos bipartitos completos de la forma K _{2, t} con t ≥ 2 son forzantes. ^{[ 1 ]} Conlon, Fox y Sudakov ampliaron este último resultado para incluir todos los grafos bipartitos con dos vértices en una parte que son completos a la otra parte ^{. [ 3 ]}

Las familias de forzamiento proporcionan una generalización natural de los grafos de forzamiento. Una familia de grafos F es forzante { G _n } es cuasialeatoria siempre que t ( F , G _n ) se aproxime a p ^{e ( F )} para todo F ∈ F . Caracterizar las familias de forzamiento es mucho más complejo que caracterizar los grafos de forzamiento, por lo que se conocen pocas. Las familias de forzamiento conocidas incluyen:

• { K ₂ , C _{2 t} } , donde t es un entero positivo;
• { C _{2 s} , C _{2 t} } , donde s y t son enteros positivos con s ≠ t ;
• { K ₂ , K _{2, t} } , donde t ≥ 2 ; y
• { K _{2, s} , K _{2, t} } , donde s ≠ t y s , t ≥ 2 . ^{[ 1 ]}

La conjetura de forzamiento fue planteada por Skokan y Thoma en 2004 ^{[ 4 ]} y formalizada por Conlon, Fox y Sudakov en 2010. ^{[ 3 ]} Proporciona una caracterización para los grafos de forzamiento, formalizada de la siguiente manera:

Un grafo es forzante si y solo si es bipartito y contiene un ciclo.

Una dirección de esta afirmación es bien conocida. Chung, Graham y Wilson demostraron que si un grafo tiene un ciclo impar, no puede ser forzante, ^{[ 1 ] por lo} que si un grafo es forzante, entonces debe ser bipartito. Además, Conlon, Fox y Sudakov argumentaron que t(H, Gn) se aproxima a p e(H) para todo bosque H cuando {Gn} es una secuencia de grafos _casi regulares ( ^{y no necesariamente} cuasialeatorias ) . [ 3 ] _Por lo ^{tanto , un} grafo forzante debe ser bipartito y tener al menos un ciclo. La otra dirección aún no se ha demostrado, pero no se ha encontrado ningún grafo forzante que no tenga ambas propiedades.

La conjetura de forzamiento también implica la conjetura de Sidorenko , una conjetura de larga data en el campo. Se sabe que todos los grafos de forzamiento son de Sidorenko, por lo que si la conjetura de forzamiento es verdadera, entonces todos los grafos bipartitos con al menos un ciclo serían de Sidorenko. ^{[ 3 ]} Dado que los árboles son de Sidorenko, ^{[ 5 ]} todos los grafos bipartitos serían de Sidorenko.