Homomorphism density

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

Una extensión del teorema de Mantel proporciona una cota inferior explícita 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).}$

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

Demostración. Basta con demostrar esta desigualdad para cualquier grafo.${\displaystyle G}$. Decir${\displaystyle G}$es un gráfico en${\displaystyle n}$vértices y${\displaystyle \{\lambda _{i}\}_{i=1}^{n}}$son los valores propios de su matriz de adyacencia${\displaystyle A_{G}}$. Mediante la teoría espectral de grafos , sabemos

${\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 se deriva 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}}$.

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

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

El límite superior de la región es ajustado y viene dado por el teorema de Kruskal-Katona. El límite inferior es el resultado principal del trabajo de Razborov, que proporciona una descripción completa. ^{[ 4 ]}

Una desigualdad particularmente útil para analizar las 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 reducir las densidades de grafos grandes pero simétricos a las de grafos más pequeños. Como ejemplo, demostramos que el ciclo de longitud 4 es Sidorenko . Si los vértices se etiquetan 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. Al plegar sobre esta línea se relaciona${\displaystyle C_{4}}$al grafo bipartito completo${\displaystyle K_{1,2}}$Matemáticamente, esto se formaliza como

${\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${\displaystyle t(K_{1,2},G)\geq t(K_{2},G)^{2}}$, lo cual, combinado con lo anterior, verifica que${\displaystyle C_{4}}$es un grafo de Sidorenko.

La desigualdad de Hölder generalizada también puede utilizarse de forma similar para plegar grafos varias veces con un solo paso. Asimismo, es posible aplicar la forma más general de la desigualdad de Cauchy-Schwarz para plegar grafos cuando ciertas aristas se encuentran sobre el eje de simetría.

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 dato útil es que un vector maximizador${\displaystyle x}$se apoya igualmente en los vértices de una camarilla en${\displaystyle H}$A continuación se presenta una aplicación del análisis de esta magnitud.

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

Teorema ( Bollobás ). Sea${\displaystyle a_{1},\cdots ,a_{n}}$sean constantes reales. Entonces, la desigualdad

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

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

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 grafos.${\displaystyle H_{i}}$:

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

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

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

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