Homomorphism density

• The edge density of a graph G is given by t(K_{2},G). • The number of walks with k-1 steps is given by \operatorname{hom}(P_k, G). • \operatorname{hom}(C_k, G) = \operatorname{Tr}(A^k) where A is the adjacency matrix of G. • The proportion of colorings using k colors that are proper is given by t(G, K_k). Other important properties such as the number of stable sets or the maximum cut can be expressed or estimated in terms of homomorphism numbers or densities. == Subgraph densities ==

We define the (labeled) subgraph density of H in G to be : d(H,G):=\frac{\# \text{ labeled copies of } H \text{ in } G}}. Note that it might be slightly dubious to call this a density, as we are not quite dividing through by the total number of labeled subgraphs on |V(H)| vertices of G, but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of H in G corresponds to a homomorphism of H into G. However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of H are sent to the same vertex of G. That said, the number of such degenerate homomorphisms is only O(n^{|V(H)|-1}), so we have t(H,G)=d(H,G)+O(1/n). For instance, we see that for graphs with constant homomorphism density, the labeled subgraph density and homomorphism density are asymptotically equivalent. For H being a complete graph K_m, the homomorphism density and subgraph density are in fact equal (for G without self-loops), as the edges of K_m force all images under a graph homomorphism to be distinct. == Generalization to graphons ==

The notion of homomorphism density can be generalized to the case where instead of a graph G, we have a graphon W, : t(H,W)=\int_{[0,1]^}\prod_{ij\in E(H)}W(x_{i},x_{j})\prod_{i\in V(H)}dx_{i} Note that the integrand is a product that runs over the edges in the subgraph H, whereas the differential is a product running over the vertices in H. Intuitively, each vertex i in H is represented by the variable x_{i}. For example, the triangle density in a graphon is given by : t(K_3, W) = \int\limits_{[0,1]^3} W(x,y)W(y,z)W(z,x) dx dy dz. This definition of homomorphism density is indeed a generalization, because for every graph G and its associated step graphon W_{G}, t(H,G)=t(H,W_{G}). The definition can be further extended to all symmetric, measurable functions W. The following example demonstrates the benefit of this further generalization. Relative to the function W(x,y) = 2\cos(2\pi(x-y)), the density of H in W is the number of Eulerian cycles in H. This notion is helpful in understanding asymptotic behavior of homomorphism densities of graphs which satisfy certain property, since a graphon is a limit of a sequence of graphs. == Inequalities ==

Many results in extremal graph theory can be described by inequalities involving homomorphism densities associated to a graph. The following are a sequence of examples relating the density of triangles to the density of edges. Turan's Theorem A classic example is Turán's Theorem, which states that if t(K_{r},W)=0, then 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 t(K_{3},W)=0, then t(K_{2},W)\leq 1/2. Goodman's Theorem An extension of Mantel's Theorem provides an explicit lower bound on triangle densities in terms of edge densities.Theorem (Goodman). t(K_3, G) \geq t(K_2, G)(2t(K_2, G) - 1). Kruskal-Katona Theorem A converse inequality to Goodman's Theorem is a special case of Kruskal–Katona theorem, which states that 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 G. Say G is a graph on n vertices, and \{\lambda_{i}\}_{i=1}^{n} are the eigenvalues of its adjacency matrix A_{G}. By spectral graph theory, we know : \operatorname{hom}(K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum_{i=1}^{n}\lambda_{i}^{2}, and \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: : \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}. Description of triangle vs edge density A more complete description of the relationship between t(K_3, G) and t(K_2, G) was proven by Razborov. His work from 2008 completes the understanding of a homomorphism inequality problem, the description of D_{2,3}, which is the region of feasible edge density, triangle density pairs in a graphon.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. == Useful tools ==

Cauchy-Schwarz 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 C_4 to the complete bipartite graph K_{1,2}. Mathematically, this is formalized as : \begin{align} 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{align} where we applied Cauchy-Schwarz to "fold" vertex 2 onto vertex 4. The same technique can be used to show t(K_{1,2}, G) \geq t(K_2, G)^2, which combined with the above verifies that 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. Lagrangian The Lagrangian can be useful in analyzing extremal problems. The quantity is defined to be : 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 x is equally supported on the vertices of a clique in 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. 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 H_{i}:Theorem (Hatami, Norine). Let a_{1},\cdots,a_{n} be real constants, and \{H_{i}\}_{i=1}^{n} graphs. Then, it is an undecidable problem to determine whether the homomorphism density inequality : \sum_{i=1}^{n}a_{r}t(H_{i},G)\geq 0 holds for every graph G. 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. == See also ==