La conjetura de Sidorenko

La conjetura de Sidorenko es una conjetura importante en el campo de la teoría extremal de grafos , planteada por Alexander Sidorenko en 1986. En términos generales, la conjetura afirma que para cualquier grafo bipartito${\displaystyle H}$y gráfico${\displaystyle G}$en${\displaystyle n}$vértices con grado promedio${\displaystyle pn}$, hay al menos${\displaystyle p^{|E(H)|}n^{|V(H)|}}$copias etiquetadas de${\displaystyle H}$en${\displaystyle G}$, salvo un pequeño término de error. Formalmente, proporciona una desigualdad intuitiva sobre las densidades de homomorfismos de grafos en grafones . La desigualdad conjeturada puede interpretarse como una afirmación de que la densidad de copias de${\displaystyle H}$en un grafo se minimiza asintóticamente mediante un grafo aleatorio, como cabría esperar.${\displaystyle p^{|E(H)|}}$fracción de subgrafos posibles que son una copia de${\displaystyle H}$si cada arista existe con probabilidad${\displaystyle p}$.

Dejar${\displaystyle H}$ser un gráfico. Entonces${\displaystyle H}$Se dice que tiene la propiedad de Sidorenko si, para todos los grafones${\displaystyle W}$la desigualdad

${\displaystyle t(H,W)\geq t(K_{2},W)^{|E(H)|}}$

es cierto, donde${\displaystyle t(H,W)}$es la densidad de homomorfismo de${\displaystyle H}$en${\displaystyle W}$.

La conjetura de Sidorenko (1986) afirma que todo grafo bipartito tiene la propiedad de Sidorenko. ^{[ 1 ]}

Si${\displaystyle W}$es un gráfico${\displaystyle G}$, esto significa que la probabilidad de una asignación aleatoria uniforme de${\displaystyle V(H)}$a${\displaystyle V(G)}$ser un homomorfismo es al menos el producto sobre cada arista en${\displaystyle H}$de la probabilidad de que ese borde se asigne a un borde en${\displaystyle G}$Esto significa, aproximadamente, que un grafo elegido al azar con un número fijo de vértices y grado promedio tiene el número mínimo de copias etiquetadas de${\displaystyle H}$Esta conjetura no es sorprendente, ya que el lado derecho de la desigualdad representa la probabilidad de que la aplicación sea un homomorfismo si cada aplicación de aristas es independiente. Por lo tanto, cabe esperar que ambos lados sean al menos del mismo orden. La extensión natural a los grafones se derivaría del hecho de que cada grafón es el punto límite de alguna secuencia de grafos.

El requisito de que${\displaystyle H}$es bipartito para tener la propiedad de Sidorenko es necesario — si${\displaystyle W}$es un grafo bipartito, entonces${\displaystyle t(K_{3},W)=0}$desde${\displaystyle W}$no tiene triángulos . Pero${\displaystyle t(K_{2},W)}$es el doble del número de aristas en${\displaystyle W}$, por lo que la propiedad de Sidorenko no se cumple${\displaystyle K_{3}}$Un argumento similar demuestra que ningún grafo con ciclos impares posee la propiedad de Sidorenko. Dado que un grafo es bipartito si y solo si no tiene ciclos impares, esto implica que los únicos grafos posibles que pueden tener la propiedad de Sidorenko son los grafos bipartitos.

Como se señaló anteriormente, para probar la propiedad de Sidorenko basta con demostrar la desigualdad para todos los grafos.${\displaystyle G}$. A lo largo de esta sección,${\displaystyle G}$es un gráfico en${\displaystyle n}$vértices con grado promedio${\displaystyle pn}$. La cantidad${\displaystyle \operatorname {hom} (H,G)}$se refiere al número de homomorfismos de${\displaystyle H}$a${\displaystyle G}$Esta cantidad es la misma que${\displaystyle n^{|V(H)|}t(H,G)}$.

Las demostraciones elementales de la propiedad de Sidorenko para algunos grafos se derivan de la desigualdad de Cauchy-Schwarz o de la desigualdad de Hölder . Otras se pueden realizar utilizando la teoría espectral de grafos , especialmente teniendo en cuenta la observación de que el número de caminos cerrados de longitud${\displaystyle \ell }$desde el vértice${\displaystyle i}$al vértice${\displaystyle j}$en${\displaystyle G}$es el componente en el${\displaystyle i}$fila y${\displaystyle j}$columna -ésima de la matriz${\displaystyle A^{\ell }}$, dónde${\displaystyle A}$es la matriz de adyacencia de${\displaystyle G}$.

Aquí hay una lista de algunos grafos bipartitos.${\displaystyle H}$que se ha demostrado que poseen la propiedad de Sidorenko.${\displaystyle H}$tener bipartición${\displaystyle A\sqcup B}$.

• Los caminos poseen la propiedad de Sidorenko, como demostraron Mulholland y Smith en 1959 (antes de que Sidorenko formulara la conjetura). ^{[ 4 ]}
• Los árboles poseen la propiedad de Sidorenko, que generaliza los caminos. Esto fue demostrado por Sidorenko en un artículo de 1991. ^{[ 5 ]}
• Los ciclos de longitud par poseen la propiedad de Sidorenko, como se demostró anteriormente. Sidorenko también lo demostró en su artículo de 1991.
• Los grafos bipartitos completos poseen la propiedad de Sidorenko. Esto también se demostró en el artículo de Sidorenko de 1991.
• Grafos bipartitos con${\displaystyle \min\{|A|,|B|\}\leq 4}$poseer la propiedad de Sidorenko. Una prueba para${\displaystyle \min\{|A|,|B|\}\leq 3}$Se puede encontrar en el artículo de Sidorenko de 1991.
• Gráficos de hipercubo (generalizaciones de${\displaystyle Q_{3}}$) tienen la propiedad de Sidorenko, como lo demostró Hatami en 2008. ^{[ 6 ]}
  • En términos más generales, los grafos de normalización (tal como los introdujo Hatami) poseen la propiedad de Sidorenko.
• Si hay un vértice en${\displaystyle A}$es decir, vecinos de cada vértice en${\displaystyle B}$(o viceversa), entonces${\displaystyle H}$tiene la propiedad de Sidorenko como lo demostraron Conlon, Fox y Sudakov en 2010. ^{[ 7 ]} Esta demostración utilizó el método de elección aleatoria dependiente .
• Para todos los grafos bipartitos${\displaystyle H}$, existe algún entero positivo${\displaystyle p}$de tal manera que el${\displaystyle p}$-explosión de${\displaystyle B}$tiene la propiedad de Sidorenko. Aquí, el${\displaystyle p}$-explosión de${\displaystyle H}$se forma reemplazando cada vértice en${\displaystyle B}$con${\displaystyle p}$copias de sí mismo, cada una conectada con sus vecinos originales en${\displaystyle A}$Esto fue demostrado por Conlon y Lee en 2018. ^{[ 8 ]}
• Se han intentado algunos enfoques recursivos que toman una colección de grafos que poseen la propiedad de Sidorenko para crear un nuevo grafo que también posee dicha propiedad. El principal progreso en este sentido fue realizado por Sidorenko en su artículo de 1991, Li y Szegedy en 2011, ^{[ 9 ]} y Kim, Lee y Lee en 2013. ^{[ 10 ]}
  • El artículo de Li y Szegedy también utilizó métodos de entropía para demostrar la propiedad para una clase de grafos llamados "árboles de reflexión".
  • El artículo de Kim, Lee y Lee extendió esta idea a una clase de grafos con una subestructura similar a un árbol, denominados "grafos ordenables en árbol".

Sin embargo, existen gráficos para los que la conjetura de Sidorenko aún no ha sido confirmada. Un ejemplo es el gráfico de la " banda de Möbius ".${\displaystyle K_{5,5}\setminus C_{10}}$, formado al eliminar un${\displaystyle 10}$-ciclo del grafo bipartito completo con partes de tamaño${\displaystyle 5}$.

László Lovász demostró una versión local de la conjetura de Sidorenko, es decir, para grafos que son "cercanos" a grafos aleatorios en el sentido de la norma de corte. ^{[ 11 ]}

Una secuencia de gráficos${\displaystyle \{G_{n}\}_{n=1}^{\infty }}$se denomina cuasialeatorio con densidad${\displaystyle p}$para cierta densidad${\displaystyle 0<p<1}$si para cada gráfico${\displaystyle H}$:

${\displaystyle t(H,G_{n})=(1+o(1))p^{|E(H)|}.}$

La secuencia de grafos tendría, por lo tanto, propiedades del grafo aleatorio de Erdős-Rényi.${\displaystyle G(n,p)}$.

Si la densidad de borde${\displaystyle t(K_{2},G_{n})}$está fijo en${\displaystyle (1+o(1))p}$, entonces la condición implica que la secuencia de grafos está cerca del caso de igualdad en la propiedad de Sidorenko para cada grafo${\displaystyle H}$.

Del artículo de Chung, Graham y Wilson de 1989 sobre grafos cuasialeatorios, basta con lo siguiente:${\displaystyle C_{4}}$contar para coincidir con lo que se esperaría de un gráfico aleatorio (es decir, la condición se cumple para${\displaystyle H=C_{4}}$). ^{[ 12 ]} El artículo también pregunta qué gráficos${\displaystyle H}$tener esta propiedad además${\displaystyle C_{4}}$Estos gráficos se denominan gráficos de forzamiento , ya que su número controla la cuasialeatoriedad de una secuencia de gráficos.

La conjetura subyacente afirma lo siguiente:

Un gráfico${\displaystyle H}$es forzante si y solo si es bipartito y no un árbol.

Es fácil ver que si${\displaystyle H}$Si es forzante, entonces es bipartito y no un árbol. Algunos ejemplos de grafos forzantes son los ciclos pares (mostrados por Chung, Graham y Wilson). Skokan y Thoma demostraron que todos los grafos bipartitos completos que no son árboles son forzantes. ^{[ 13 ]}

La conjetura de Sidorenko para grafos de densidad${\displaystyle p}$Esto se deduce de la conjetura de forzamiento. Además, la conjetura de forzamiento demostraría que los grafos que se aproximan a la igualdad en la propiedad de Sidorenko deben satisfacer condiciones de cuasialeatoriedad. ^{[ 14 ]}

• Gráfico común