Densidad de homomorfismo

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

.

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

Arriba, $\operatorname {hom} (H,G)$ es el conjunto de homomorfismos de grafo, o mapas que preservan adyacencia, de $H$ a $G$ . La densidad también puede ser interpretada como la probabilidad que un mapa de los vértices de $H$ hacia los vértices de $G$ escogido uniformemente al azar sea un homomorfismo de grafo.^[1] Hay una conexión entre densidades de homomorfismo y densidades de subgrafos, la cual está descrita abajo.^[2]

Ejemplos

La densidad de arista de un grafo $G$ está dada por $t(K_{2},G)$ .
El número de paseos con $k-1$ pasos está dado por $\operatorname {hom} (P_{k},G)$ .
$\operatorname {hom} (C_{k},G)=\operatorname {Tr} (A^{k})$ , donde $A$ es la matriz de adyacencia de $G$ .
La proporción de coloraciones que utilizan $k$ colores y que son propias está dada por $t(G,K_{k})$ .

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

Densidades de subgrafo

Definimos la densidad de un subgrafo (con etiquetas) $H$ en $G$ como

.

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

Notemos que podría ser ligeramente sospechoso llamar a lo de arriba densidad, ya que no estamos dividiendo entre el número total de subgrafos etiquetados en $|V(H)|$ vértices de $G$ ; sin embargo, nuestra definición es asintóticamente equivalente y más sencilla de analizar para nuestros propósitos. Observa que cualquier copia etiquetada de $H$ en $G$ corresponde a un homomorfismo de $H$ a $G$ . Sin embargo, no todo homomorfismo corresponde a una copia etiquetada − existen algunos casos degenerados, en los cuales múltiples vértices de $H$ son enviados al mismo vértice de $G$ . Dicho esto, la cantidad de tales homorfismos degenerados es tan sólo $O(n^{|V(H)|-1})$ , así que tenemos $t(H,G)=d(H,G)+O(1/n)$ . Por ejemplo, para grafos con densidad de homomorfismo constante, la densidad de subgrafo y la densidad de homomorfismo son asintóticamente equivalentes. Para que $H$ sea un grafo completo $K_{m}$ , la densidad de homomorfismo y subgraph y la densidad de subgrafo son de hecho iguales (para $G$ sin bucles, o vértices conectados con sí mismos), ya que las aristas de $K_{m}$ forzarían que todas las imágenes bajo un homomorfismo de grafo sean distintas.

Generalización para grafones

La noción de densidad de homomorfismo puede ser generalizada al caso en el que, en vez de un grafo $G$ , tenemos un grafón $W$ ,

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}

Nota que el integrando es un producto que abarca las aristas del subgrafo $H$ , mientras que el diferencial es un producto que visita los vértices en $H$ . Intuitivamente, cada vértice $i$ en $H$ está representado por la variable $x_{i}.$ Por ejemplo, la densidad de triángulo en un graphon está dado por

.

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 grafo $G$ y su grafón retícula asociado $W_{G}$ , $t(H,G)=t(H,W_{G})$ .^[1]

La definición puede ser extendida para todas las funciones $W$ simétricas y medibles. El ejemplo siguiente muestra el beneficio que nos da considerar esta generalización. Relativo a la función $W(x,y)=2\cos(2\pi (x-y))$ , la densidad de $H$ en $W$ es el número de ciclos Eulerianos en $H$ .

Esta idea es útil para entender el comportamiento asintótico de 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 en teoría de grafos extremales pueden ser descritos por desigualdades que implican densidades de homomorfismo asociadas a un grafo. Lo siguiente es una secuencia de ejemplos que relacionan la densidad de triángulos a la densidad de aristas.

Turan Teorema

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

El Teorema de Goodman

Una generalización del teorema de Mantel proviene de una cuota inferior explícita para la densidad de triángulos en un grafo, en términos de la densidad de aristas en el mismo grafo.^[3]

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

Teorema de Kruskal-Katona

Un desigualdad conversa a la establecida por el teorema de Goodman es un caso especial del teorema de Kruskal–Katona, el cual declara que $t(K_{3},G)\leq t(K_{2},G)^{3/2}$ . Resulta que ambas desigualdades son rígidas para densidades de arista específicas.

Prueba. Es suficiente de probar esta desigualdad para cualquier grafo $G$ . Digamos que $G$ es un grafo con $n$ vértices, y $\{\lambda _{i}\}_{i=1}^{n}$ son los eigenvalores de su matriz de adyacencia $A_{G}$ . Por teoría de grafos espectral, sabemos que

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

, y

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

.

La conclusión entonces sigue de la desigualdad siguiente:

.

\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 densidad de triángulo vs densidad de arista

Una descripción más completa de la relación entre $t(K_{3},G)$ y $t(K_{2},G)$ fue encontrada por Razborov. Su trabajo de 2008 completa el entendimiento de un problema de desigualdades de homomorfismos, la descripción de $D_{2,3}$ , la cual es la región de tuplas de densidades de arista y densidades de triángulo factibles en un grafón.^[4]

. $D_{2,3}=\{(t(K_{2},W),t(K_{3},W))\;:\;W{\text{ es un grafon }}\}\subseteq [0,1]^{2}$

La frontera superior de la región es rígida y dada por el Teorema de Kruskal-Katona. La frontera más baja es el resultado principal de trabajo por Razborov^[4] en dar una descripción completa.

Herramientas útiles

Cauchy-Schwarz

Una desigualdad particularmente útil para analizar densidades de homomorfismo es la de Cauchy–Schwarz. El efecto de aplicar la desigualdad de Cauchy-Schwarz es aquél de "plegado" de un 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 densidades de grafos más pequeños. Por ejemplo, probamos que el ciclo de longitud 4 es Sidorenko. Si los vértices están etiquetados con 1,2,3,4 en aquél orden, la diagonal a través de vértices 1 y 3 es una línea de simetría. Plegando sobre esta línea, obtenemos una relación entre $C_{4}$ y el grafo bipartito completo $K_{1,2}$ . Matemáticamente, esto se formaliza con

{\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" al vértice 2 con el vértice 4. La misma técnica puede ser usada para mostrar que $t(K_{1,2},G)\geq t(K_{2},G)^{2}$ , lo cual combinado con lo de arriba verifica que $C_{4}$ es un grafo Sidorenko.

La generalización dada por la desigualdad de Hölder también puede ser utilizada de una manera similar para plegar grafor múltiples veces en un solo paso. Es también posible aplicar la forma más general de Cauchy-Schwarz para plegar grafos en el caso de que ciertas aristas estén sobre la línea de simetría.

Lagrangiano

El lagrangiano puede ser útil en analizar problemas extremales. Dicha cantidad está definida como

.

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}

Uno el hecho útil acerca del lagrangiano es que un vector maximal $x$ tiene soporte equidistribuido en los vértices de una clique en $H$ . Lo siguiente es una aplicación que procede de de analizar esta cantidad.

Según Hamed Hatami y Sergei Norine, uno puede convertir cualquier desigualdad algebraica entre densidades de homomorfismo en una desigualdad lineal.^[2] En algunas situaciones, el problema de decidir si tal desigualdad es cierta o no puede ser simplificado, como es el caso en el siguiente teorema.

Teorema (Bollobás). Sean $a_{1},\cdots ,a_{n}$ constantes reales. Entonces, la desigualdad
$\sum _{i=1}^{n}a_{i}t(K_{i},G)\geq 0$
Ccumple para todo grafo $G$ si y sólo si cumple para todo grafo completo $K_{m}$ .^[5]

Aun así, conseguimos un problema mucho más difícil, de hecho uno indecidible, cuando tenemos desigualdades de homomorfismo en un conjunto más general de grafos $H_{i}$ :

Teorema (Hatami, Norine). Sean $a_{1},\cdots ,a_{n}$ constantes reales, y $\{H_{i}\}_{i=1}^{n}$ grafos. Entonces, es un problema no decidible el de determinar si la desigualdad de densidad de homomorfismos
$\sum _{i=1}^{n}a_{r}t(H_{i},G)\geq 0$
cumple para todo grafo $G$ .^[2]

Una observación reciente^[6] prueba que cualquier desigualdad de densidad de homomorfismo lineal es una consecuencia de la propiedad de cierta matriz infinita de ser positivo semi-definida, o a la positividad de un grafo cuántico; en otras palabras, cualquier desigualdad sería una consecuencia de aplicaciones de la desigualdad de Cauchy-Schwarz.^[2]

Véase también

Conjetura de Sidorenko

Referencias

↑ ^a ^b Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T; Vestergombi, Katalin (2008). «Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing». Advances in Mathematics 219 (6): 1801-1851. doi:10.1016/j.aim.2008.07.008.
↑ ^a ^b ^c ^d Hatami, H., Norine, S. (2011). «Undecidability of linear inequalities in graph homomorphism densities.». Journal of the American Mathematical Society 24 (2): 553. arXiv:1005.2382. doi:10.1090/S0894-0347-2010-00687-X.
↑ ^a ^b Lovász, László (2012). Large networks and graph limits. Providence, Rhode Island. ISBN 978-0-8218-9085-1. OCLC 812530987.
↑ ^a ^b Razborov, Alexander (2008). «On the minimal density of triangles in graphs.». Combinatorics, Probability and Computing 17 (4): 603-618. doi:10.1017/S0963548308009085.
↑ Bollobás, Bela (1986). Combinatorics: Set systems, hypergraphs, families of vectors and combinatorial probability.. Cambridge: Cambridge University Press. pp. 79-84. ISBN 0-521-33059-9.
↑ Freedman, M., Lovász, L., Schrijver, A. (2007). «Reflection Positivity, Rank connectivity, and Homomorphism of Graphs». Journal of the American Mathematical Society 20 (1): 1.

[:0-1] Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T; Vestergombi, Katalin (2008). «Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing». Advances in Mathematics 219 (6): 1801-1851. doi:10.1016/j.aim.2008.07.008.

[:1-2] Hatami, H., Norine, S. (2011). «Undecidability of linear inequalities in graph homomorphism densities.». Journal of the American Mathematical Society 24 (2): 553. arXiv:1005.2382. doi:10.1090/S0894-0347-2010-00687-X.

[:2-3] Lovász, László (2012). Large networks and graph limits. Providence, Rhode Island. ISBN 978-0-8218-9085-1. OCLC 812530987.

[:3-4] Razborov, Alexander (2008). «On the minimal density of triangles in graphs.». Combinatorics, Probability and Computing 17 (4): 603-618. doi:10.1017/S0963548308009085.

[5] Bollobás, Bela (1986). Combinatorics: Set systems, hypergraphs, families of vectors and combinatorial probability.. Cambridge: Cambridge University Press. pp. 79-84. ISBN 0-521-33059-9.

[6] Freedman, M., Lovász, L., Schrijver, A. (2007). «Reflection Positivity, Rank connectivity, and Homomorphism of Graphs». Journal of the American Mathematical Society 20 (1): 1.

[1]

[2]

[3]

[4]

[5]

[6]