La conjetura de Sidorenko

Conjetura en teoría de grafos

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 gráfico bipartito y gráfico 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, ya que uno esperaría que una fracción de posibles subgrafos fuera una copia si cada borde existiera con probabilidad . ${\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)|}}$ ${\displaystyle H}$ ${\displaystyle p}$

Declaración

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

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

es cierto, ¿dónde está la densidad de homomorfismo de in ? ${\displaystyle t(H,W)}$ ${\displaystyle H}$ ${\displaystyle W}$

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

Si es un gráfico , esto significa que la probabilidad de que un mapeo aleatorio uniforme de a sea un homomorfismo es al menos el producto sobre cada borde en de la probabilidad de que ese borde sea mapeado a un borde en . Esto significa aproximadamente que un gráfico elegido al azar con un número fijo de vértices y un 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 mapeo de aristas es independiente. Por lo tanto, uno debería esperar que las dos partes sean al menos del mismo orden. La extensión natural a los grafones se derivaría del hecho de que cada grabón es el punto límite de alguna secuencia de grafos. ${\displaystyle W}$ ${\displaystyle G}$ ${\displaystyle V(H)}$ ${\displaystyle V(G)}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$

El requisito de que sea bipartito para tener la propiedad de Sidorenko es necesario: si es un gráfico bipartito, entonces no tiene triángulos. Pero es el doble de aristas en , por lo que la propiedad de Sidorenko no se cumple para . Un argumento similar muestra que ningún gráfico con un ciclo impar tiene la propiedad de Sidorenko. Dado que una gráfica es bipartita si y sólo si no tiene ciclos impares, esto implica que las únicas gráficas posibles que pueden tener la propiedad de Sidorenko son las gráficas bipartitas. ${\displaystyle H}$ ${\displaystyle W}$ ${\displaystyle t(K_{3},W)=0}$ ${\displaystyle W}$ ${\displaystyle t(K_{2},W)}$ ${\displaystyle W}$ ${\displaystyle K_{3}}$

Formulación equivalente

La propiedad de Sidorenko equivale a la siguiente reformulación:

Para todos los gráficos , si tiene vértices y un grado promedio de , entonces . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle pn}$ ${\displaystyle t(H,G)\geq p^{|E(H)|}}$

Esto es equivalente porque el número de homomorfismos de a es el doble del número de aristas en , y la desigualdad solo necesita verificarse cuando es una gráfica como se mencionó anteriormente. ${\displaystyle K_{2}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle W}$

En esta formulación, dado que el número de homomorfismos no inyectivos de a es como máximo un número constante de veces , la propiedad de Sidorenko implicaría que hay al menos copias etiquetadas de in . ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle n^{|V(H)|-1}}$ ${\displaystyle (p^{|E(H)|}-o(1))n^{|V(H)|}}$ ${\displaystyle H}$ ${\displaystyle G}$

Ejemplos

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

Las pruebas elementales de la propiedad de Sidorenko para algunos gráficos se derivan de la desigualdad de Cauchy-Schwarz o la desigualdad de Hölder . Se pueden hacer otros usando la teoría de grafos espectrales , especialmente observando la observación de que el número de caminos cerrados de longitud de vértice a vértice es el componente en la ésima fila y la ésima columna de la matriz , donde es la matriz de adyacencia de . ${\displaystyle \ell }$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle G}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle A^{\ell }}$ ${\displaystyle A}$ ${\displaystyle G}$

Cauchy-Schwarz: el C 4 de 4 ciclos

Al fijar dos vértices y de , cada copia de have y en extremos opuestos puede identificarse eligiendo dos vecinos comunes (no necesariamente distintos) de y . Denotando el código de y (es decir, el número de vecinos comunes), esto implica: ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle C_{4}}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle \operatorname {codeg} (u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$

${\displaystyle \operatorname {hom} (C_{4},G)=\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)^{2}\geq {\frac {1}{n^{2}}}\left(\sum _{u,v\in V(G)}\operatorname {codeg} (u,v)\right)^{2}}$

por la desigualdad de Cauchy-Schwarz. La suma ahora se ha convertido en un recuento de todos los pares de vértices y sus vecinos comunes, que es lo mismo que el recuento de todos los vértices y pares de sus vecinos. Entonces:

${\displaystyle \operatorname {hom} (C_{4},G)\geq {\frac {1}{n^{2}}}\left(\sum _{x\in V(G)}\deg(x)^{2}\right)^{2}\geq {\frac {1}{n^{2}}}\left({\frac {1}{n}}\left(\sum _{x\in V(G)}\deg(x)\right)^{2}\right)^{2}={\frac {1}{n^{2}}}\left({\frac {1}{n}}(n\cdot pn)^{2}\right)^{2}=p^{4}n^{4}}$

por Cauchy-Schwarz nuevamente. Entonces:

${\displaystyle t(C_{4},G)={\frac {\operatorname {hom} (C_{4},G)}{n^{4}}}\geq p^{4}}$

como se desee.

Teoría de grafos espectrales: el ciclo de 2 k C 2 k

Aunque el enfoque de Cauchy-Schwarz es elegante y elemental, no se generaliza inmediatamente a todos los ciclos pares. Sin embargo, se puede aplicar la teoría de grafos espectrales para demostrar que todos los ciclos pares tienen la propiedad de Sidorenko. Tenga en cuenta que los ciclos impares no se tienen en cuenta en la conjetura de Sidorenko porque no son bipartitos. ${\displaystyle C_{4}}$

Usando la observación sobre caminos cerrados, se deduce que es la suma de las entradas diagonales en . Esto es igual a la traza de , que a su vez es igual a la suma de las potencias enésimas de los valores propios de . Si son los valores propios de , entonces el teorema mínimo-máximo implica que: ${\displaystyle \operatorname {hom} (C_{2k},G)}$ ${\displaystyle A^{2k}}$ ${\displaystyle A^{2k}}$ ${\displaystyle 2k}$ ${\displaystyle A}$ ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \dots \geq \lambda _{n}}$ ${\displaystyle A}$

${\displaystyle \lambda _{1}\geq {\frac {\mathbf {1} ^{\intercal }A\mathbf {1} }{\mathbf {1} ^{\intercal }\mathbf {1} }}={\frac {1}{n}}\sum _{x\in V(G)}\deg(x)=pn,}$

¿Dónde está el vector con componentes, todos los cuales son ? Pero entonces: ${\displaystyle \mathbf {1} }$ ${\displaystyle n}$ ${\displaystyle 1}$

${\displaystyle \operatorname {hom} (C_{2k},G)=\sum _{i=1}^{n}\lambda _{i}^{2k}\geq \lambda _{1}^{2k}\geq p^{2k}n^{2k}}$

porque los valores propios de una matriz simétrica real son reales. Entonces:

${\displaystyle t(C_{2k},G)={\frac {\operatorname {hom} (C_{2k},G)}{n^{2k}}}\geq p^{2k}}$

como se desee.

Entropía: caminos de longitud 3

JL Xiang Li y Balázs Szegedy (2011) introdujeron la idea de utilizar la entropía para probar algunos casos de la conjetura de Sidorenko. Szegedy (2015) luego aplicó las ideas para demostrar que una clase aún más amplia de gráficos bipartitos tiene la propiedad de Sidorenko. ^[2] Si bien la prueba de Szegedy terminó siendo abstracta y técnica, Tim Gowers y Jason Long redujeron el argumento a uno más simple para casos específicos como caminos de longitud . ^[3] En esencia, la prueba elige una buena distribución de probabilidad de elegir los vértices en el camino y aplica la desigualdad de Jensen (es decir, la convexidad) para deducir la desigualdad. ${\displaystyle 3}$

Resultados parciales

Aquí hay una lista de algunos gráficos bipartitos que se ha demostrado que tienen propiedad de Sidorenko. Tengamos bipartición . ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle A\sqcup B}$

• Los caminos tienen la propiedad de Sidorenko, como lo demostraron Mulholland y Smith en 1959 (antes de que Sidorenko formulara la conjetura). ^[4]
• Los árboles tienen la propiedad de Sidorenko, generalizando caminos. Así lo demostró Sidorenko en un artículo de 1991. ^[5]
• Los ciclos de longitud uniforme tienen la propiedad de Sidorenko como se mostró anteriormente. Sidorenko también lo demostró en su artículo de 1991.
• Los gráficos bipartitos completos tienen la propiedad de Sidorenko. Esto también se demostró en el artículo de Sidorenko de 1991.
• Los gráficos bipartitos tienen la propiedad de Sidorenko. Esto también se demostró en el artículo de Sidorenko de 1991. ${\displaystyle \min\{|A|,|B|\}\leq 4}$
• Los gráficos de hipercubo (generalizaciones de ) tienen la propiedad de Sidorenko, como lo demostró Hatami en 2008. ^[6] ${\displaystyle Q_{3}}$
  • De manera más general, los gráficos normativos (como los introdujo Hatami) tienen la propiedad de Sidorenko.
• Si hay un vértice que es vecino de cada vértice (o viceversa), entonces tiene la propiedad de Sidorenko como lo mostraron Conlon, Fox y Sudakov en 2010. ^[7] Esta prueba utilizó el método de elección aleatoria dependiente . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle H}$
• Para todos los gráficos bipartitos , existe algún número entero positivo tal que la explosión de tiene la propiedad de Sidorenko. Aquí, la ampliación de se forma reemplazando cada vértice con copias de sí mismo, cada una conectada con sus vecinos originales en . Esto fue demostrado por Conlon y Lee en 2018. ^[8] ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle B}$ ${\displaystyle p}$ ${\displaystyle H}$ ${\displaystyle B}$ ${\displaystyle p}$ ${\displaystyle A}$
• Se han intentado algunos enfoques recursivos, que toman una colección de gráficos que tienen la propiedad de Sidorenko para crear un nuevo gráfico que tiene la propiedad de Sidorenko. El principal avance en este sentido lo realizaron 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 de una clase de gráficos llamados "árboles de reflexión".
  • El artículo de Kim, Lee y Lee extendió esta idea a una clase de gráficos con una subestructura en forma de árbol llamados "gráficos organizables en árbol".

Sin embargo, hay gráficos para los cuales la conjetura de Sidorenko aún está abierta. Un ejemplo es el gráfico de la "tira de Möbius" , formado eliminando un ciclo del gráfico bipartito completo con partes de tamaño . ${\displaystyle K_{5,5}\setminus C_{10}}$ ${\displaystyle 10}$ ${\displaystyle 5}$

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

Forzando conjetura

Una secuencia de gráficas se llama cuasi aleatoria con densidad para alguna densidad si para cada gráfica : ${\displaystyle \{G_{n}\}_{n=1}^{\infty }}$ ${\displaystyle p}$ ${\displaystyle 0<p<1}$ ${\displaystyle H}$

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

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

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

Del artículo de Chung, Graham y Wilson de 1989 sobre gráficos cuasi aleatorios, basta con que el recuento coincida con lo que se esperaría de un gráfico aleatorio (es decir, la condición se cumple para ). ^[12] El artículo también pregunta qué gráficos tienen esta propiedad además . Estos gráficos se denominan gráficos forzados porque su recuento controla la cuasi aleatoriedad de una secuencia de gráficos. ${\displaystyle C_{4}}$ ${\displaystyle H=C_{4}}$ ${\displaystyle H}$ ${\displaystyle C_{4}}$

La conjetura forzada establece lo siguiente:

Un grafo es forzado si y sólo si es bipartito y no un árbol. ${\displaystyle H}$

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

La conjetura de Sidorenko para las gráficas de densidad se deriva de la conjetura forzada. Además, la conjetura forzada mostraría que las gráficas cercanas a la igualdad en la propiedad de Sidorenko deben satisfacer condiciones de cuasi-aleatoriedad. ^[14] ${\displaystyle p}$

Ver también

• gráfico común

Referencias

1. Sidorenko, Alexander (1993), "Una desigualdad de correlación para gráficos bipartitos", Gráficos y combinatoria , 9 (2–4): 201–204, doi :10.1007/BF02988307, S2CID  12233056
2. Szegedy, Balázs (2015), Un enfoque teórico de la información a la conjetura de Sidorenko , arXiv : 1406.6738
3. Gowers, Tim. "La entropía y la conjetura de Sidorenko - después de Szegedy". Blog de Gowers . Consultado el 1 de diciembre de 2019 .
4. Mulholland, HP; Smith, Cedric (1959), "Una desigualdad que surge en la teoría genética", American Mathematical Monthly , 66 (8): 673–683, doi :10.1080/00029890.1959.11989387
5. Sidorenko, Alexander (1991), "Desigualdades de funcionales generadas por gráficos bipartitos", Diskretnaya Matematika , 2 (3): 50–65, doi :10.1515/dma.1992.2.5.489, S2CID  117471984
6. Hatami, Hamed (2010), "Normas gráficas y conjetura de Sidorenko", Israel Journal of Mathematics , 175 : 125–150, arXiv : 0806.0047 , doi : 10.1007/s11856-010-0005-1
7. Conlón, David ; Zorro, Jacob ; Sudakov, Benny (2010), "Una versión aproximada de la conjetura de Sidorenko", Análisis geométrico y funcional , 20 (6): 1354–1366, arXiv : 1004.4236 , doi :10.1007/s00039-010-0097-0, S2CID  1872674
8. Conlón, David ; Lee, Joonkyung (2018), Conjetura de Sidorenko para las explosiones , arXiv : 1809.01259
9. Li, JL Xiang; Szegedy, Balázs (2011), Sobre el cálculo logarítimo y la conjetura de Sidorenko , arXiv : 1107.1153
10. Kim, Jeong Han ; Lee, Choongbum; Lee, Joonkyung (2016), "Dos enfoques de la conjetura de Sidorenko", Transacciones de la Sociedad Matemática Estadounidense , 368 (7): 5057–5074, arXiv : 1310.4383 , doi : 10.1090/tran/6487
11. Lovász, László (2010), Densidades de subgrafos en grafones firmados y la conjetura local de Sidorenko , arXiv : 1004.3026
12. Chung, ventilador ; Graham, Ronald ; Wilson, Richard (1989), "Gráficos cuasi aleatorios", Combinatorica , 9 (4): 345–362, doi :10.1007/BF02125347
13. Skokan, Jozef; Thoma, Lubos (2004), "Subgrafos bipartitos y cuasi aleatoriedad", Gráficos y combinatoria , 20 (2): 255–262, doi :10.1007/s00373-004-0556-1, S2CID  2154492
14. Conlón, David ; Zorro, Jacob ; Sudakov, Benny (2010), "Una versión aproximada de la conjetura de Sidorenko", Análisis geométrico y funcional , 20 (6): 1354–1366, arXiv : 1004.4236 , doi :10.1007/s00039-010-0097-0, S2CID  1872674