Gráfico común

Concepto en la teoría de grafos extremales

En teoría de grafos , un área de las matemáticas, los grafos comunes pertenecen a una rama de la teoría de grafos extremos que se ocupa de las desigualdades en densidades de homomorfismos . En términos generales, es un grafo común si aparece "comúnmente" como un subgrafo, en el sentido de que el número total de copias de en cualquier grafo y su complemento es una fracción grande de todas las copias posibles de en los mismos vértices. Intuitivamente, si contiene pocas copias de , entonces su complemento debe contener muchas copias de para compensarlo. ${\displaystyle F}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle {\overline {G}}}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle F}$ ${\displaystyle {\overline {G}}}$ ${\displaystyle F}$

Los grafos comunes están estrechamente relacionados con otras nociones de grafos que tratan desigualdades de densidad de homomorfismo. Por ejemplo, los grafos comunes son un caso más general de grafos de Sidorenko .

Definición

Un gráfico es común si la desigualdad: ${\displaystyle F}$

${\displaystyle t(F,W)+t(F,1-W)\geq 2^{-e(F)+1}}$

se cumple para cualquier grafón , donde es el número de aristas de y es la densidad de homomorfismo . ^[1] ${\displaystyle W}$ ${\displaystyle e(F)}$ ${\displaystyle F}$ ${\displaystyle t(F,W)}$

La desigualdad es estricta porque el límite inferior siempre se alcanza cuando es el grafón constante . ${\displaystyle W}$ ${\displaystyle W\equiv 1/2}$

Interpretaciones de la definición

Para un grafo , tenemos y para el grafón asociado , ya que el grafón asociado al complemento es . Por lo tanto, esta fórmula nos proporciona la intuición muy informal de tomar una aproximación lo suficientemente cercana, sea lo que sea que eso signifique, ^[2] a , y ver como aproximadamente la fracción de copias etiquetadas de grafo en grafo "aproximado" . Luego, podemos suponer que la cantidad es aproximadamente e interpretar esto último como el número combinado de copias de en y . Por lo tanto, vemos que se cumple. Esto, a su vez, significa que el grafo común aparece comúnmente como subgrafo. ${\displaystyle G}$ ${\displaystyle t(F,G)=t(F,W_{G})}$ ${\displaystyle t(F,{\overline {G}})=t(F,1-W_{G})}$ ${\displaystyle W_{G}}$ ${\displaystyle {\overline {G}}}$ ${\displaystyle W_{\overline {G}}=1-W_{G}}$ ${\displaystyle W}$ ${\displaystyle W_{G}}$ ${\displaystyle t(F,W)}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle t(F,W)+t(F,1-W)}$ ${\displaystyle t(F,G)+t(F,{\overline {G}})}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle {\overline {G}}}$ ${\displaystyle t(F,G)+t(F,{\overline {G}})\gtrsim 2^{-e(F)+1}}$ ${\displaystyle F}$

En otras palabras, si pensamos en las aristas y no aristas como 2-coloraciones de las aristas de un grafo completo en los mismos vértices, entonces al menos una fracción de todas las copias posibles de son monocromáticas. Nótese que en un grafo aleatorio de Erdős–Rényi con cada arista dibujada con probabilidad , cada homomorfismo de grafo de a tiene probabilidad de ser monocromático. Por lo tanto, un grafo común es un grafo en el que alcanza su número mínimo de apariciones como un subgrafo monocromático de grafo en el grafo con ${\displaystyle 2^{-e(F)+1}}$ ${\displaystyle F}$ ${\displaystyle G=G(n,p)}$ ${\displaystyle p=1/2}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle 2\cdot 2^{-e(F)}=2^{-e(F)+1}}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle G=G(n,p)}$ ${\displaystyle p=1/2}$

${\displaystyle p=1/2}$La definición anterior que utiliza la densidad de homomorfismo generalizado se puede entender de esta manera.

Ejemplos

• Como se indicó anteriormente, todos los grafos de Sidorenko son grafos comunes. ^[3] Por lo tanto, cualquier grafo de Sidorenko conocido es un ejemplo de grafo común y, más notablemente, los ciclos de longitud uniforme son comunes. ^[4] Sin embargo, estos son ejemplos limitados ya que todos los grafos de Sidorenko son grafos bipartitos mientras que existen grafos comunes no bipartitos, como se demuestra a continuación.
• El gráfico triangular es un ejemplo simple de gráfico común no bipartito. ^[5] ${\displaystyle K_{3}}$
• ${\displaystyle K_{4}^{-}}$, el gráfico obtenido al eliminar una arista del gráfico completo en 4 vértices , es común. ^[6] ${\displaystyle K_{4}}$
• No es un ejemplo: Durante un tiempo se creyó que todos los grafos eran comunes. Sin embargo, resulta que no es común para . ^[7] En particular, no es común aunque sí lo es. ${\displaystyle K_{t}}$ ${\displaystyle t\geq 4}$ ${\displaystyle K_{4}}$ ${\displaystyle K_{4}^{-}}$

Pruebas

Los gráficos de Sidorenko son comunes

Un grafo es un grafo de Sidorenko si satisface para todos los grafones . ${\displaystyle F}$ ${\displaystyle t(F,W)\geq t(K_{2},W)^{e(F)}}$ ${\displaystyle W}$

En ese caso, . Además, , lo que se desprende de la definición de densidad de homomorfismo. Combinando esto con la desigualdad de Jensen para la función : ${\displaystyle t(F,1-W)\geq t(K_{2},1-W)^{e(F)}}$ ${\displaystyle t(K_{2},W)+t(K_{2},1-W)=1}$ ${\displaystyle f(x)=x^{e(F)}}$

${\displaystyle t(F,W)+t(F,1-W)\geq t(K_{2},W)^{e(F)}+t(K_{2},1-W)^{e(F)}\geq 2{\bigg (}{\frac {t(K_{2},W)+t(K_{2},1-W)}{2}}{\bigg )}^{e(F)}=2^{-e(F)+1}}$

Por tanto, se cumplen las condiciones para un gráfico común. ^[8]

El gráfico triangular es común

Desarrollar la expresión integral para y tener en cuenta la simetría entre las variables: ${\displaystyle t(K_{3},1-W)}$

${\displaystyle \int _{[0,1]^{3}}(1-W(x,y))(1-W(y,z))(1-W(z,x))dxdydz=1-3\int _{[0,1]^{2}}W(x,y)+3\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz-\int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz}$

Cada término de la expresión puede escribirse en términos de densidades de homomorfismo de grafos más pequeños. Según la definición de densidades de homomorfismo:

${\displaystyle \int _{[0,1]^{2}}W(x,y)dxdy=t(K_{2},W)}$

${\displaystyle \int {[0,1]^{3}}W(x,y)W(x,z)dxdydz=t(K_{1,2},W)}$

${\displaystyle \int _{[0,1]^{3}}W(x,y)W(y,z)W(z,x)dxdydz=t(K_{3},W)}$

donde denota el grafo bipartito completo con vértices en una parte y vértices en la otra. De esto se deduce: ${\displaystyle K_{1,2}}$ ${\displaystyle 1}$ ${\displaystyle 2}$

${\displaystyle t(K_{3},W)+t(K_{3},1-W)=1-3t(K_{2},W)+3t(K_{1,2},W)}$.

${\displaystyle t(K_{1,2},W)}$se puede relacionar gracias a la simetría entre las variables y : ${\displaystyle t(K_{2},W)}$ ${\displaystyle y}$ ${\displaystyle z}$ $${\displaystyle {\begin{alignedat}{4}t(K_{1,2},W)&=\int _{[0,1]^{3}}W(x,y)W(x,z)dxdydz&&\\&=\int _{x\in [0,1]}{\bigg (}\int _{y\in [0,1]}W(x,y){\bigg )}{\bigg (}\int _{z\in [0,1]}W(x,z){\bigg )}&&\\&=\int _{x\in [0,1]}{\bigg (}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}&&\\&\geq {\bigg (}\int _{x\in [0,1]}\int _{y\in [0,1]}W(x,y){\bigg )}^{2}=t(K_{2},W)^{2}\end{alignedat}}}$$

donde el último paso se desprende de la desigualdad integral de Cauchy-Schwarz . Finalmente:

${\displaystyle t(K_{3},W)+t(K_{3},1-W)\geq 1-3t(K_{2},W)+3t(K_{2},W)^{2}=1/4+3{\big (}t(K_{2},W)-1/2{\big )}^{2}\geq 1/4}$.

Esta prueba se puede obtener tomando el análogo continuo del Teorema 1 en "Sobre conjuntos de conocidos y desconocidos en cualquier fiesta" ^[9]

Véase también

• La conjetura de Sidorenko

Referencias

1. Grandes redes y límites de grafos. American Mathematical Society. pág. 297. Consultado el 13 de enero de 2022 .
2. Borgs, C.; Chayes, JT; Lovász, L .; Sós, VT ; Vesztergombi, K. (2008-12-20). "Secuencias convergentes de grafos densos I: frecuencias de subgrafos, propiedades métricas y pruebas". Avances en Matemáticas . 219 (6): 1801–1851. arXiv : math/0702004 . doi : 10.1016/j.aim.2008.07.008 . ISSN  0001-8708. S2CID  5974912.
3. Grandes redes y límites de grafos. American Mathematical Society. pág. 297. Consultado el 13 de enero de 2022 .
4. Sidorenko, AF (1992). "Desigualdades para funcionales generadas por grafos bipartitos". Matemáticas discretas y aplicaciones . 2 (5). doi :10.1515/dma.1992.2.5.489. ISSN  0924-9265. S2CID  117471984.
5. Grandes redes y límites de grafos. American Mathematical Society. pág. 299. Consultado el 13 de enero de 2022 .
6. Grandes redes y límites de grafos. American Mathematical Society. pág. 298. Consultado el 13 de enero de 2022 .
7. Thomason, Andrew (1989). "Una refutación de una conjetura de Erdős en la teoría de Ramsey". Revista de la Sociedad Matemática de Londres . s2-39 (2): 246–255. doi :10.1112/jlms/s2-39.2.246. ISSN  1469-7750.
8. Lovász, László (2012). Grandes redes y límites de grafos . Estados Unidos: Publicaciones del Colloquium de la American Mathematical Society. pp. 297–298. ISBN 978-0821890851.
9. Goodman, AW (1959). "Sobre grupos de conocidos y desconocidos en cualquier fiesta". The American Mathematical Monthly . 66 (9): 778–783. doi :10.2307/2310464. ISSN  0002-9890. JSTOR  2310464.