En teoría de grafos , un grafo forzado 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 forzados desempeñan un papel importante en el estudio de la pseudoaleatoriedad en secuencias de grafos.
La conjetura de forzamiento establece que los grafos de forzamiento son exactamente los grafos bipartitos cíclicos. Se la ha descrito como "uno de los principales problemas abiertos en la combinatoria extremal ". [2]
Sea t ( H , G ) = # copias etiquetadas de H en G/v ( sol ) v ( al ) , conocida como densidad de subgrafos (en particular, t ( K 2 , 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 2 , G n ) se acerca a algún p y t ( H , G n ) se acerca 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 uno esperaría en una secuencia de grafos aleatoria. Un grafo F se denomina forzador si para todas las secuencias de grafos { G n } donde t ( K 2 , G n ) se acerca a p cuando n tiende a infinito, { G n } es cuasialeatoria si t ( F , G n ) se acerca a p e ( F ) . En otras palabras, se puede verificar que una secuencia de gráficos es cuasialeatoria simplemente comprobando la densidad de homomorfismo de un solo gráfico. [3]
Existe una segunda definición de grafos forzados que utiliza el lenguaje de los grafones . Formalmente, un grafo se llama forzador si cada grafo W tal que t ( F , W ) = t ( K 2 , W ) e ( F ) es constante. Intuitivamente, tiene sentido que estas definiciones estén relacionadas. El grafo constante W ( x , y ) = p representa el grafo aleatorio de Erdős–Rényi G ( n , p ) , por lo que se podría esperar que tuviera una relación estrecha con los grafos cuasialeatorios. De hecho, estas definiciones son equivalentes. [ cita requerida ]
El primer gráfico de forzamiento que se debe considerar es el de 4 ciclos C 4 , ya que tiene una estrecha relación con otras condiciones de cuasialeatoriedad. En el mismo artículo, Chung, Graham y Wilson demostraron que cada ciclo par C 2 t y los gráficos 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 gráficos bipartitos con dos vértices en una parte que son completos hasta 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 complicado que caracterizar los grafos de forzamiento, por lo que se conocen pocas. Las familias de forzamiento conocidas incluyen:
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 gráficos de forzamiento, formalizada de la siguiente manera:
Un gráfico es forzado si y sólo 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 forzado, [1] por lo que si un grafo es forzado, entonces debe ser bipartito. Además, Conlon, Fox y Sudakov argumentaron que t ( H , G n ) se acerca a p e ( H ) para cada bosque H cuando { G n } es una secuencia de grafos casi regular (y no necesariamente cuasialeatoria). [3] Por lo tanto, un grafo forzado debe ser bipartito y tener al menos un ciclo. La otra dirección aún está por demostrar, pero no se ha encontrado ningún grafo forzado 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 Sidorenko, por lo que si la conjetura de forzamiento es verdadera, entonces todos los grafos bipartitos con al menos un ciclo serían Sidorenko. [3] Dado que los árboles son Sidorenko, [5] todos los grafos bipartitos serían Sidorenko.