Densidad de homomorfismo

Concepto en teoría matemática de grafos.

En el campo matemático de la teoría de grafos extremos , la densidad de homomorfismo respecto de un gráfico es un parámetro que se asocia a cada gráfico 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, está el conjunto de homomorfismos de grafos , o mapas que preservan la adyacencia, desde hasta . La densidad también se puede interpretar como la probabilidad de que un mapa desde los vértices de hasta los vértices de elegidos uniformemente al azar sea un homomorfismo de grafo. ^[1] Existe una conexión entre las densidades de homomorfismo y las densidades de subgrafos, que se detalla 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 está 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 está la matriz de adyacencia de . ${\displaystyle A}$ ${\displaystyle G}$
• La proporción de colorantes que utilizan colores propios 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, se pueden expresar o estimar en términos de números o densidades de homomorfismo. ^[3]

Densidades de subgrafos

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

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

Tenga en cuenta que podría ser un poco dudoso llamar a esto densidad, ya que no estamos dividiendo por el número total de subgrafos etiquetados en los vértices de , pero nuestra definición es asintóticamente equivalente y más sencilla de analizar para nuestros propósitos. Observe que cualquier copia etiquetada de in corresponde a un homomorfismo de into . Sin embargo, no todos los homomorfismos corresponden a una copia etiquetada; existen algunos casos degenerados, en los que se envían múltiples vértices de al mismo vértice de . Dicho esto, el número de homomorfismos degenerados es sólo , por lo que tenemos . Por ejemplo, vemos que para gráficos con densidad de homomorfismo constante, la densidad de subgrafo etiquetado y la densidad de homomorfismo son asintóticamente equivalentes. Para ser un gráfico completo , la densidad de homomorfismo y la densidad de subgrafo son de hecho iguales ( sin bucles automáticos), ya que los bordes de fuerza obligan a que todas las imágenes bajo un homomorfismo de gráfico 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 el que en lugar de un grafo , tenemos un grafo , ${\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}}$

Tenga en cuenta que el integrando es un producto que recorre los bordes en el subgrafo , mientras que el diferencial es un producto que recorre los vértices en . Intuitivamente, cada vértice está representado por la variable. Por ejemplo, la densidad del triángulo en un grabón viene 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 se puede ampliar aún más a todas las funciones simétricas y medibles . El siguiente ejemplo demuestra el beneficio de esta generalización adicional. En relación con la función , la densidad de in 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 gráficos que satisfacen cierta propiedad, ya que un grabón es un límite de una secuencia de gráficos.

Desigualdades

Muchos resultados en la teoría de grafos extremos pueden describirse mediante desigualdades que involucran densidades de homomorfismo asociadas a un gráfico. A continuación se muestra 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 los triángulos en términos de densidades de las 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}}$

Prueba. Es suficiente demostrar esta desigualdad para cualquier gráfica . Digamos que es un gráfico de 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 surge entonces 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 del triángulo frente a la densidad de los bordes

Razborov demostró una descripción más completa de la relación entre y . 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 factible, pares de densidad de triángulos en un grafo. ^[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 estrecho y está dado por el teorema de Kruskal-Katona. El límite inferior es el principal resultado del trabajo de Razborov para proporcionar una descripción completa. ^[4]

Herramientas útiles

Cauchy-Negro

Una desigualdad particularmente útil para analizar las densidades de homomorfismo es la desigualdad de Cauchy-Schwarz . El efecto de aplicar la desigualdad de Cauchy-Schwarz es "doblar" la gráfica sobre un eje de simetría para relacionarla con una gráfica más pequeña. Esto permite la reducción de densidades de gráficos grandes pero simétricos a la de gráficos más pequeños. Como ejemplo, demostramos que el ciclo de longitud 4 es Sidorenko . Si los vértices están etiquetados como 1,2,3,4 en ese orden, la diagonal que pasa por los vértices 1 y 3 es un eje de simetría. Doblar esta línea se relaciona con el gráfico 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 "doblar" el vértice 2 sobre el vértice 4. Se puede usar la misma técnica 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 gráficos varias veces en un solo paso. También es posible aplicar la forma más general de Cauchy-Schwarz para plegar gráficas en el caso de que ciertas aristas se encuentren en el eje de simetría.

lagrangiano

El lagrangiano puede resultar ú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 cierta o no se puede simplificar, como es el caso en el siguiente teorema.

Teorema ( 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}$

es válido para todo gráfico si y sólo si es válido para todo gráfico completo . ^[5] ${\displaystyle G}$ ${\displaystyle K_{m}}$

Sin embargo, tenemos 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 consecuencia de la semidefinición positiva de una determinada matriz infinita, o de la positividad de un gráfico cuántico ; en otras palabras, cualquier desigualdad de este tipo se derivaría de la aplicación de la desigualdad de Cauchy-Schwarz. ^[2]

Ver también

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

Referencias

1. Borgs, cristiano; Chayes, Jennifer T.; Lovász, László ; Sós, Vera T ; Vestergombi, Katalin (2008). "Secuencias convergentes de gráficos densos. I. Frecuencias de subgrafos, propiedades métricas y pruebas". Avances en Matemáticas . 219 (6): 1801–1851. arXiv : matemáticas/0702004 . doi : 10.1016/j.aim.2008.07.008 .
2. Hatami, H., Norine, S. (2011). "Indecidibilidad de desigualdades lineales en densidades de homomorfismo gráfico" (PDF) . Revista de la Sociedad Matemática Estadounidense . 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, Alejandro (2008). «Sobre la densidad mínima de triángulos en gráficas» (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: Prensa de la Universidad de Cambridge. págs. 79-84. ISBN 0-521-33059-9.
6. Freedman, M., Lovász, L., Schrijver, A. (2007). "Positividad de reflexión, conectividad de rango y homomorfismo de gráficos" (PDF) . Revista de la Sociedad Matemática Estadounidense . 20 (1): 1.{{cite journal}}: CS1 maint: multiple names: authors list (link)