Gráfico común

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

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

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

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

se aplica a cualquier grafón${\displaystyle W}$, dónde${\displaystyle e(F)}$es el número de aristas de${\displaystyle F}$y${\displaystyle t(F,W)}$es la densidad de homomorfismos . ^{[ 1 ]}

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

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

En otras palabras, si pensamos en aristas y no aristas como 2-coloración de aristas de un grafo completo en los mismos vértices, entonces al menos${\displaystyle 2^{-e(F)+1}}$fracción de todas las copias posibles de${\displaystyle F}$son monocromáticos. Tenga en cuenta que en un gráfico aleatorio de Erdős-Rényi${\displaystyle G=G(n,p)}$con cada borde dibujado con probabilidad${\displaystyle p=1/2}$, cada homomorfismo de grafos de${\displaystyle F}$a${\displaystyle G}$tener probabilidad${\displaystyle 2\cdot 2^{-e(F)}=2^{-e(F)+1}}$de ser monocromático. Entonces, gráfico común${\displaystyle F}$es un grafo donde alcanza su número mínimo de apariciones como un subgrafo monocromático del grafo${\displaystyle G}$en el gráfico${\displaystyle G=G(n,p)}$con${\displaystyle p=1/2}$

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

• 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, en particular, los ciclos de longitud par 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${\displaystyle K_{3}}$es un ejemplo sencillo de grafo común no bipartito. ^{[ 5 ]}
• ${\displaystyle K_{4}^{-}}$, el grafo obtenido al eliminar una arista del grafo completo en 4 vértices${\displaystyle K_{4}}$, es común. ^{[ 6 ]}
• No-ejemplo: Durante un tiempo se creyó que todos los gráficos son comunes. Sin embargo, resulta que${\displaystyle K_{t}}$no es común para${\displaystyle t\geq 4}$. ^{[ 7 ]} En particular,${\displaystyle K_{4}}$no es común aunque${\displaystyle K_{4}^{-}}$es común.

• La conjetura de Sidorenko