Densidad de homomorfismo

Concepto en la teoría de grafos matemáticos

En el campo matemático de la teoría de grafos extremales , la densidad de homomorfismo con respecto a un grafo es un parámetro que se asocia a cada grafo de la siguiente manera: ${\displaystyle H}$ ${\displaystyle t(H,-)}$ ${\displaystyle G}$

${\displaystyle t(H,G):={\frac {\left|\operatorname {hom} (H,G)\right|}{|V(G)|^{|V(H)|}}}}$.

Arriba, se encuentra el conjunto de homomorfismos de grafos , o aplicaciones que preservan la adyacencia, de a . La densidad también se puede interpretar como la probabilidad de que una aplicación de los vértices de a los vértices de elegida uniformemente al azar sea un homomorfismo de grafos. ^[1] Existe una conexión entre las densidades de homomorfismo y las densidades de subgrafos, que se explica a continuación. ^[2] ${\displaystyle \operatorname {hom} (H,G)}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$

Ejemplos

• La densidad de aristas de un gráfico viene dada por . ${\displaystyle G}$ ${\displaystyle t(K_{2},G)}$
• El número de paseos con pasos viene dado por . ${\displaystyle k-1}$ ${\displaystyle \operatorname {hom} (P_{k},G)}$
• ${\displaystyle \operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})}$donde es la matriz de adyacencia de . ${\displaystyle A}$ ${\displaystyle G}$
• La proporción de coloraciones utilizando colores adecuados viene dada por . ${\displaystyle k}$ ${\displaystyle t(G,K_{k})}$

Otras propiedades importantes, como el número de conjuntos estables o el corte máximo, pueden expresarse o estimarse en términos de números o densidades de homomorfismo. ^[3]

Densidades de subgrafos

Definimos la densidad del subgrafo (etiquetado) de in como ${\displaystyle H}$ ${\displaystyle G}$

${\displaystyle d(H,G):={\frac {\#{\text{ labeled copies of }}H{\text{ in }}G}{|V(G)|^{|V(H)|}}}}$.

Nótese que puede ser un poco dudoso llamar a esto una densidad, ya que no estamos dividiendo exactamente por el número total de subgrafos etiquetados en vértices de , pero nuestra definición es asintóticamente equivalente y más simple de analizar para nuestros propósitos. Observe que cualquier copia etiquetada de en corresponde a un homomorfismo de en . Sin embargo, no todo homomorfismo corresponde a una copia etiquetada − hay algunos casos degenerados, en los que múltiples vértices de se envían al mismo vértice de . Dicho esto, el número de tales homomorfismos degenerados es solo , por lo que tenemos . Por ejemplo, vemos que para grafos con densidad de homomorfismo constante, la densidad de subgrafos etiquetados y la densidad de homomorfismo son asintóticamente equivalentes. Para ser un grafo completo , la densidad de homomorfismo y la densidad de subgrafos son de hecho iguales (para sin bucles propios), ya que las aristas de fuerzan a que todas las imágenes bajo un homomorfismo de grafo sean distintas. ${\displaystyle |V(H)|}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle O(n^{|V(H)|-1})}$ ${\displaystyle t(H,G)=d(H,G)+O(1/n)}$ ${\displaystyle H}$ ${\displaystyle K_{m}}$ ${\displaystyle G}$ ${\displaystyle K_{m}}$

Generalización a grafones

La noción de densidad de homomorfismo se puede generalizar al caso en que en lugar de un grafo , tenemos un grafón , ${\displaystyle G}$ ${\displaystyle W}$

${\displaystyle t(H,W)=\int _{[0,1]^{|V(H)|}}\prod _{ij\in E(H)}W(x_{i},x_{j})\prod _{i\in V(H)}dx_{i}}$

Nótese que el integrando es un producto que recorre las aristas del subgrafo , mientras que el diferencial es un producto que recorre los vértices de . Intuitivamente, cada vértice de está representado por la variable Por ejemplo, la densidad de triángulos en un grafón está dada por ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle i}$ ${\displaystyle H}$ ${\displaystyle x_{i}.}$

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

Esta definición de densidad de homomorfismo es de hecho una generalización, porque para cada gráfico y su grafo escalonado asociado , . ^[1] ${\displaystyle G}$ ${\displaystyle W_{G}}$ ${\displaystyle t(H,G)=t(H,W_{G})}$

La definición puede extenderse a todas las funciones simétricas y mensurables . El siguiente ejemplo demuestra el beneficio de esta generalización adicional. En relación con la función , la densidad de en es el número de ciclos eulerianos en . ${\displaystyle W}$ ${\displaystyle W(x,y)=2\cos(2\pi (x-y))}$ ${\displaystyle H}$ ${\displaystyle W}$ ${\displaystyle H}$

Esta noción es útil para comprender el comportamiento asintótico de las densidades de homomorfismo de grafos que satisfacen cierta propiedad, ya que un grafón es un límite de una secuencia de grafos.

Desigualdades

Muchos resultados de la teoría de grafos extremos se pueden describir mediante desigualdades que involucran densidades de homomorfismos asociadas a un grafo. A continuación se presenta una secuencia de ejemplos que relacionan la densidad de triángulos con la densidad de aristas.

Teorema de Turan

Un ejemplo clásico es el teorema de Turán , que establece que si , entonces . Un caso especial de esto es el teorema de Mantel , que establece que si , entonces . ${\displaystyle t(K_{r},W)=0}$ ${\displaystyle t(K_{2},W)\leq \left(1-{\frac {1}{r-1}}\right)}$ ${\displaystyle t(K_{3},W)=0}$ ${\displaystyle t(K_{2},W)\leq 1/2}$

Teorema de Goodman

Una extensión del Teorema de Mantel proporciona un límite inferior explícito para las densidades de triángulos en términos de densidades de aristas. ^[3]

Teorema (Goodman). ${\displaystyle t(K_{3},G)\geq t(K_{2},G)(2t(K_{2},G)-1).}$

Teorema de Kruskal-Katona

Una desigualdad inversa al teorema de Goodman es un caso especial del teorema de Kruskal-Katona , que establece que . Resulta que ambas desigualdades son estrictas para densidades de aristas específicas. ${\displaystyle t(K_{3},G)\leq t(K_{2},G)^{3/2}}$

Demostración. Es suficiente demostrar esta desigualdad para cualquier grafo . Digamos que es un grafo sobre vértices, y son los valores propios de su matriz de adyacencia . Por la teoría de grafos espectrales , sabemos ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \{\lambda _{i}\}_{i=1}^{n}}$ ${\displaystyle A_{G}}$

${\displaystyle \operatorname {hom} (K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum _{i=1}^{n}\lambda _{i}^{2}}$, y . ${\displaystyle \operatorname {hom} (K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum _{i=1}^{n}\lambda _{i}^{3}}$

La conclusión entonces proviene de la siguiente desigualdad:

${\displaystyle \operatorname {hom} (K_{3},G)=\sum _{i=1}^{n}\lambda _{i}^{3}\leq \left(\sum _{i=1}^{n}\lambda _{i}^{2}\right)^{3/2}=\operatorname {hom} (K_{2},G)^{3/2}}$.

Descripción de triángulos vs densidad de aristas

Una descripción más completa de la relación entre y fue demostrada por Razborov . Su trabajo de 2008 completa la comprensión de un problema de desigualdad de homomorfismo, la descripción de , que es la región de densidad de aristas factibles, pares de densidad de triángulos en un grafón. ^[4] ${\displaystyle t(K_{3},G)}$ ${\displaystyle t(K_{2},G)}$ ${\displaystyle D_{2,3}}$

${\displaystyle D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ is a graphon}}\}\subseteq [0,1]^{2}}$.

El límite superior de la región es estricto y está dado por el teorema de Kruskal-Katona. El límite inferior es el resultado principal del trabajo de Razborov al proporcionar una descripción completa. ^[4]

Herramientas útiles

Cauchy-Schwarz

Una desigualdad particularmente útil para analizar densidades de homomorfismos es la desigualdad de Cauchy-Schwarz . El efecto de aplicar la desigualdad de Cauchy-Schwarz es "plegar" el grafo sobre una línea de simetría para relacionarlo con un grafo más pequeño. Esto permite la reducción de densidades de grafos grandes pero simétricos a la de grafos más pequeños. Como ejemplo, demostramos que el ciclo de longitud 4 es Sidorenko . Si los vértices están etiquetados 1,2,3,4 en ese orden, la diagonal que pasa por los vértices 1 y 3 es una línea de simetría. Plegar sobre esta línea se relaciona con el grafo bipartito completo . Matemáticamente, esto se formaliza como ${\displaystyle C_{4}}$ ${\displaystyle K_{1,2}}$

${\displaystyle {\begin{aligned}t(C_{4},G)&=\int _{1,2,3,4}W(1,2)W(2,3)W(3,4)W(1,4)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)\left(\int _{4}W(1,4)W(4,3)\right)=\int _{1,3}\left(\int _{2}W(1,2)W(2,3)\right)^{2}\\&\geq \left(\int _{1,2,3}W(1,2)W(2,3)\right)^{2}=t(K_{1,2},G)^{2}\end{aligned}}}$

donde aplicamos Cauchy-Schwarz para "plegar" el vértice 2 sobre el vértice 4. La misma técnica se puede utilizar para mostrar , que combinado con lo anterior verifica que es un gráfico de Sidorenko. ${\displaystyle t(K_{1,2},G)\geq t(K_{2},G)^{2}}$ ${\displaystyle C_{4}}$

La generalización de la desigualdad de Hölder también se puede utilizar de manera similar para plegar grafos varias veces en un solo paso. También es posible aplicar la forma más general de Cauchy-Schwarz para plegar grafos en el caso de que ciertas aristas se encuentren en la línea de simetría.

Lagrangiano

El lagrangiano puede ser útil para analizar problemas extremos. La cantidad se define como

${\displaystyle L(H)=\max _{\begin{matrix}x_{1},\ldots ,x_{n}\geq 0\\x_{1}+\cdots x_{n}=1\end{matrix}}\sum _{e\in E(H)}\prod _{v\in e}x_{v}}$.

Un hecho útil es que un vector maximizador se apoya igualmente en los vértices de una camarilla en . La siguiente es una aplicación del análisis de esta cantidad. ${\displaystyle x}$ ${\displaystyle H}$

Según Hamed Hatami y Sergei Norine, se puede convertir cualquier desigualdad algebraica entre densidades de homomorfismo en una desigualdad lineal. ^[2] En algunas situaciones, decidir si dicha desigualdad es verdadera o no se puede simplificar, como es el caso del siguiente teorema.

Teorema de Bollobás . Sean constantes reales. Entonces, la desigualdad ${\displaystyle a_{1},\cdots ,a_{n}}$

${\displaystyle \sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0}$

se cumple para cada gráfico si y sólo si se cumple para cada gráfico completo . ^[5] ${\displaystyle G}$ ${\displaystyle K_{m}}$

Sin embargo, nos encontramos con un problema mucho más difícil, de hecho indecidible , cuando tenemos desigualdades de homomorfismo en un conjunto más general de gráficos : ${\displaystyle H_{i}}$

Teorema (Hatami, Norine). Sean constantes reales y gráficas. Entonces, es un problema indecidible determinar si la desigualdad de densidad del homomorfismo ${\displaystyle a_{1},\cdots ,a_{n}}$ ${\displaystyle \{H_{i}\}_{i=1}^{n}}$

${\displaystyle \sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0}$

se cumple para cada gráfico . ^[2] ${\displaystyle G}$

Una observación reciente ^[6] demuestra que cualquier desigualdad de densidad de homomorfismo lineal es una consecuencia de la semidefinición positiva de una cierta matriz infinita, o de la positividad de un gráfico cuántico ; en otras palabras, cualquier desigualdad de este tipo se seguiría de aplicaciones de la desigualdad de Cauchy-Schwarz. ^[2]

Véase también

• Gráfico común
• La conjetura de Sidorenko

Referencias

1. Borgs, Christian; Chayes, Jennifer T.; Lovász, László ; Sós, Vera T ; Vestergombi, Katalin (2008). "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 .
2. Hatami, H., Norine, S. (2011). "Indecidibilidad de desigualdades lineales en densidades de homomorfismo de grafos" (PDF) . Journal of the American Mathematical Society . 24 (2): 553. arXiv : 1005.2382 . doi :10.1090/S0894-0347-2010-00687-X. S2CID  3363894 – vía MathSciNet.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. Lovász, László (2012). Grandes redes y límites de gráficos. Providencia, Rhode Island. ISBN 978-0-8218-9085-1.OCLC 812530987  .{{cite book}}: CS1 maint: location missing publisher (link)
4. Razborov, Alexander (2008). "Sobre la densidad mínima de triángulos en grafos" (PDF) . Combinatoria, probabilidad y computación . 17 (4): 603–618. doi :10.1017/S0963548308009085. S2CID  26524353 – vía MathSciNet (AMS).
5. Bollobás, Bela (1986). Combinatoria: sistemas de conjuntos, hipergrafos, familias de vectores y probabilidad combinatoria. Cambridge: Cambridge University Press. pp. 79-84. ISBN 0-521-33059-9.
6. Freedman, M., Lovász, L., Schrijver, A. (2007). "Positividad de reflexión, conectividad de rangos y homomorfismo de grafos" (PDF) . Revista de la Sociedad Matemática Americana . 20 (1): 1.{{cite journal}}: CS1 maint: multiple names: authors list (link)