Homomorphism density

A classic example is Turán's Theorem, which states that if ${\displaystyle t(K_{r},W)=0}$, then ${\displaystyle t(K_{2},W)\leq \left(1-{\frac {1}{r-1}}\right)}$. A special case of this is Mantel's Theorem, which states that if ${\displaystyle t(K_{3},W)=0}$, then ${\displaystyle t(K_{2},W)\leq 1/2}$.

An extension of Mantel's Theorem provides an explicit lower bound on triangle densities in terms of edge densities.[3]

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

A converse inequality to Goodman's Theorem is a special case of Kruskal–Katona theorem, which states that ${\displaystyle t(K_{3},G)\leq t(K_{2},G)^{3/2}}$. It turns out that both of these inequalities are tight for specific edge densities.

Proof. It is sufficient to prove this inequality for any graph ${\displaystyle G}$. Say ${\displaystyle G}$ is a graph on ${\displaystyle n}$ vertices, and ${\displaystyle \{\lambda _{i}\}_{i=1}^{n}}$ are the eigenvalues of its adjacency matrix ${\displaystyle A_{G}}$. By spectral graph theory, we know

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

The conclusion then comes from the following inequality:

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

A more complete description of the relationship between ${\displaystyle t(K_{3},G)}$ and ${\displaystyle t(K_{2},G)}$ was proven by Razborov. His work from 2008 completes the understanding of a homomorphism inequality problem, the description of ${\displaystyle D_{2,3}}$, which is the region of feasible edge density, triangle density pairs in a graphon.[4]

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

The upper boundary of the region is tight and given by the Kruskal-Katona Theorem. The lower boundary is main result of work by Razborov in providing a complete description.[4]

One particularly useful inequality to analyze homomorphism densities is the Cauchy–Schwarz inequality. The effect of applying the Cauchy-Schwarz inequality is "folding" the graph over a line of symmetry to relate it to a smaller graph. This allows for the reduction of densities of large but symmetric graphs to that of smaller graphs. As an example, we prove that the cycle of length 4 is Sidorenko. If the vertices are labelled 1,2,3,4 in that order, the diagonal through vertices 1 and 3 is a line of symmetry. Folding over this line relates ${\displaystyle C_{4}}$ to the complete bipartite graph ${\displaystyle K_{1,2}}$. Mathematically, this is formalized as

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

where we applied Cauchy-Schwarz to "fold" vertex 2 onto vertex 4. The same technique can be used to show ${\displaystyle t(K_{1,2},G)\geq t(K_{2},G)^{2}}$, which combined with the above verifies that ${\displaystyle C_{4}}$ is a Sidorenko graph.

The generalization Hölder's inequality can also be used in a similar manner to fold graphs multiple times with a single step. It is also possible to apply the more general form of Cauchy-Schwarz to fold graphs in the case that certain edges lie on the line of symmetry.

The Lagrangian can be useful in analyzing extremal problems. The quantity is defined to be

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

One useful fact is that a maximizing vector ${\displaystyle x}$ is equally supported on the vertices of a clique in ${\displaystyle H}$. The following is an application of analyzing this quantity.

According to Hamed Hatami and Sergei Norine, one can convert any algebraic inequality between homomorphism densities to a linear inequality.[2] In some situations, deciding whether such an inequality is true or not can be simplified, such as it is the case in the following theorem.

Theorem (Bollobás). Let ${\displaystyle a_{1},\cdots ,a_{n}}$ be real constants. Then, the inequality

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

holds for every graph ${\displaystyle G}$ if and only if it holds for every complete graph ${\displaystyle K_{m}}$.[5]

However, we get a much harder problem, in fact an undecidable one, when we have a homomorphism inequalities on a more general set of graphs ${\displaystyle H_{i}}$:

Theorem (Hatami, Norine). Let ${\displaystyle a_{1},\cdots ,a_{n}}$ be real constants, and ${\displaystyle \{H_{i}\}_{i=1}^{n}}$ graphs. Then, it is an undecidable problem to determine whether the homomorphism density inequality

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

holds for every graph ${\displaystyle G}$. [2]

A recent observation[6] proves that any linear homomorphism density inequality is a consequence of the positive semi-definiteness of a certain infinite matrix, or to the positivity of a quantum graph; in other words, any such inequality would follow from applications of the Cauchy-Schwarz Inequality. [2]