Hipótesis Sidorenko

La conjetura de Sidorenko de la teoría de grafos se refiere a una estimación del número de homomorfismos de algún gráfico (arbitrario pero fijo) en un gráfico arbitrario . Ella afirma que para un bipartito este número nunca es menor que para un gráfico de tamaño aleatorio con la misma densidad de borde esperada que . $H$ $GRAMO$ $H$ $|G|$ $GRAMO$

La conjetura fue propuesta por Alexander Sidorenko en 1986 [1] (un caso particular fue probado incluso antes [2] ). Ha sido probado por varios métodos para algunas clases de grafos , pero está lejos de ser una solución general. $H$

Redacción

Denotemos el número de homomorfismos de gráfico a gráfico . En particular, denotemos el número de aristas en . Denotemos también la "densidad" de tales homomorfismos entre todas las asignaciones de vértices a vértices . ${\ estilo de visualización h_ {H} (G)}$ $H$ $GRAMO$ $h_{K_{2}}(G)$ $GRAMO$ ${\displaystyle t_{H}(G)={\frac {h_{H}(G)}{|G|^{|V(H)|))))$ $H$ $GRAMO$

Hipótesis Sidorenko

Si es un gráfico de aristas bipartito , entonces para cualquier gráfico es cierto que $H$ $metro$ $GRAMO$ $t_{H}(G)\geq t_{K_{2}}(G)^{m}$

Usualmente, una hipótesis se considera como un conjunto de enunciados para diferentes y se habla de su solución precisamente para uno u otro y arbitrario . $H$ $H$ $GRAMO$

Sidorenko originalmente formuló la declaración en una forma más general, para una medida en gráficos continuos ponderados (los llamados graphons ). [3]

Interpretación a través del azar

Para un gráfico aleatorio en el modelo, el número esperado de aristas y el número esperado de ocurrencias del gráfico igual a corresponden exactamente a la igualdad en la conjetura de Sidorenko. ${\ estilo de visualización G (n, p)}$ ${\mathbb {E} }\ {t_{K_{2}}(G)}=np$ $H$ ${\displaystyle {\mathbb {E} }\ t_{H}(G)=n^{|V(H)|}p^{|E(H)|))$

A primera vista, el juicio de que una cierta cantidad (aquí, el número de ocurrencias ) es "nunca menor que el promedio" puede parecer paradójico, porque esto significaría que todos los valores de la cantidad son iguales al promedio. Esto sería así si la interpretación por aleatoriedad considerara el modelo de grafos aleatorios de Erdős-Rényi con un número fijo de aristas, ya que la estimación en la conjetura de Sidorenko depende del número real de aristas en el gráfico. Y en el modelo, solo el número esperado de aristas será igual a él. es decir, el promedio se realiza no solo sobre gráficos del mismo tamaño que el dado, sino también sobre gráficos para los que la hipótesis de Sidorenko da estimaciones muy diferentes para el número de ocurrencias . $H$ ${\ estilo de visualización G (n, m)}$ ${\ estilo de visualización G (n, p)}$ $H$

Algunos resultados

La hipótesis ha sido probada para:

caminos [4] ;
ciclos de longitud uniforme [5] ;
árboles [6] ;
gráficos de hipercubo [7] ;
grafos bipartitos completos [8] ;
para gráficos bipartitos con el tamaño de una de las partes no superior a 4 [9] ;
para gráficos que tienen al menos un vértice adyacente a todos los vértices de la parte opuesta [10] .

Muchos de los resultados se han combinado en un solo concepto de prueba mediante el uso de las propiedades de la entropía de la teoría de la información . [11] [12]

También hay resultados conocidos sobre la construcción de grafos: para cualquier grafo bipartito existe un número tal que si duplicamos los vértices de una de las partes (junto con las aristas salientes) veces, entonces el grafo resultante satisfará la conjetura de Sidorenko [13 ] . $pags$ $pags$

Sin embargo, la conjetura permanece abierta para muchos gráficos. Por ejemplo, para (un gráfico bipartito completo sin un ciclo hamiltoniano ). ${\displaystyle K_{5,5}\setminus C_{10))$

Notas

↑ Ver mención de esto en Sidorenko, 1993 antes de la hipótesis 1
↑ Mulholland, Smith, 1959 .
↑ Sidorenko, 1993 .
↑ Mulholland, Smith, 1959 , véase la declaración al principio de la p. 674 en ${\ estilo de visualización v = (1, \ puntos, 1)}$
↑ Sidorenko, 1991 , ejemplo 1
↑ Sidorenko, 1991 , consecuencia 1
↑ Hatami, 2010 .
↑ Sidorenko, 1991 , véase el Teorema 5 y el comentario posterior
↑ Sidorenko, 1991 , véase el Teorema 1 y el comentario posterior
↑ Conlon, Sudakov, Fox, 2010 , Teorema 1.2
↑ Szegedy, 2015 .
↑ Entropy and Sidorenko's conjecture - after Szegedy Archivado el 26 de septiembre de 2020 en Wayback Machine , revisado en el blog de Gowers
↑ Conlon, Lee, 2018 , corolario 1.2

Literatura

HP Mulholland, CAB Smith. Una desigualdad que surge en la teoría genética // The American Mathematical Monthly. - 1959. - Vol. 66 , edición. 8 _ — pág. 673–683 .

A. Sidorenko. Una desigualdad de correlación para gráficos bipartitos // Gráficos y combinatoria. - 1993. - vol. 9 _ — pág. 201–204 .

A. F. Sidorenko. Desigualdades para funcionales generadas por grafos bipartitos // Matemáticas Discretas. - 1991. - Vol. 3 , número. 3 . — S. 50–65 . (Ruso)

H. Hatami. Normas gráficas y conjetura de Sidorenko (inglés) // Israel Journal of Mathematics. - 2010. - Vol. 175 . — págs. 125–150 . -arXiv : 0806.0047 . _

D. Conlon, J. Fox, B. Sudakov. Una versión aproximada de la conjetura de Sidorenko // Análisis geométrico y funcional. - 2010. - Vol. 20 _ - P. 1354-1366 . -arXiv : 1004.4236 . _

D. Conlon, J. Lee. La conjetura de Sidorenko para las explosiones . - 2018. - arXiv : 1809.01259 .

B. Szegedy. Una aproximación teórica de la información a la conjetura de Sidorenko (inglés) . - 2015. - arXiv : 1406.6738v3 .