La conjetura de Sidorenko

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

Sea un gráfico. Entonces se dice que tiene la propiedad de Sidorenko si, para todos los grafones , la desigualdad ${\ Displaystyle H}$ ${\ Displaystyle H}$ ${\ Displaystyle W}$

es cierto, ¿dónde está la densidad de homomorfismo de en . ${\ Displaystyle t (H, W)}$ ${\ Displaystyle H}$ ${\ Displaystyle W}$

Si es un gráfico , esto significa que la probabilidad de un mapeo aleatorio uniforme de a homomorfismo es al menos el producto sobre cada borde de la probabilidad de que ese borde se mapee a un borde en . Esto significa aproximadamente que un gráfico elegido al azar con un número fijo de vértices y grado promedio tiene el número mínimo de copias etiquetadas de . Esta no es una conjetura sorprendente porque el lado derecho de la desigualdad es la probabilidad de que el mapeo sea un homomorfismo si cada mapa de borde es independiente. Por lo tanto, se debe esperar que los dos lados sean al menos del mismo orden. La extensión natural de los grafones se seguiría del hecho de que cada grafón es el punto límite de alguna secuencia de gráficos. ${\ Displaystyle W}$ ${\ Displaystyle G}$ ${\ Displaystyle V (H)}$ ${\ Displaystyle V (G)}$ ${\ Displaystyle H}$ ${\ Displaystyle G}$ ${\ Displaystyle H}$