Homomorphism density

Short description: Concept in mathematical graph theory

In the mathematical field of extremal graph theory, homomorphism density with respect to a graph [math]\displaystyle{ H }[/math] is a parameter [math]\displaystyle{ t(H,-) }[/math] that is associated to each graph [math]\displaystyle{ G }[/math] in the following manner:

[math]\displaystyle{ t(H,G):=\frac{\left|\operatorname{hom}(H,G)\right|}{|V(G)|^{|V(H)|}} }[/math].

Above, [math]\displaystyle{ \operatorname{hom}(H,G) }[/math] is the set of graph homomorphisms, or adjacency preserving maps, from [math]\displaystyle{ H }[/math] to [math]\displaystyle{ G }[/math]. Density can also be interpreted as the probability that a map from the vertices of [math]\displaystyle{ H }[/math] to the vertices of [math]\displaystyle{ G }[/math] chosen uniformly at random is a graph homomorphism. There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.

Examples

• The edge density of a graph [math]\displaystyle{ G }[/math] is given by [math]\displaystyle{ t(K_{2},G) }[/math].
• The number of walks with [math]\displaystyle{ k-1 }[/math] steps is given by [math]\displaystyle{ \operatorname{hom}(P_k, G) }[/math].
• [math]\displaystyle{ \operatorname{hom}(C_k, G) = \operatorname{Tr}(A^k) }[/math] where [math]\displaystyle{ A }[/math] is the adjacency matrix of [math]\displaystyle{ G }[/math].
• The proportion of colorings using [math]\displaystyle{ k }[/math] colors that are proper is given by [math]\displaystyle{ t(G, K_k) }[/math].

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 [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math] to be

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

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 [math]\displaystyle{ |V(H)| }[/math] vertices of [math]\displaystyle{ G }[/math], but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math] corresponds to a homomorphism of [math]\displaystyle{ H }[/math] into [math]\displaystyle{ G }[/math]. However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of [math]\displaystyle{ H }[/math] are sent to the same vertex of [math]\displaystyle{ G }[/math]. That said, the number of such degenerate homomorphisms is only [math]\displaystyle{ O(n^{|V(H)|-1}) }[/math], so we have [math]\displaystyle{ t(H,G)=d(H,G)+O(1/n) }[/math]. For instance, we see that for graphs with constant homomorphism density, the labeled subgraph density and homomorphism density are asymptotically equivalent. For [math]\displaystyle{ H }[/math] being a complete graph [math]\displaystyle{ K_m }[/math], the homomorphism density and subgraph density are in fact equal (for [math]\displaystyle{ G }[/math] without self-loops), as the edges of [math]\displaystyle{ K_m }[/math] 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 [math]\displaystyle{ G }[/math], we have a graphon [math]\displaystyle{ W }[/math],

[math]\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} }[/math]

Note that the integrand is a product that runs over the edges in the subgraph [math]\displaystyle{ H }[/math], whereas the differential is a product running over the vertices in [math]\displaystyle{ H }[/math]. Intuitively, each vertex [math]\displaystyle{ i }[/math] in [math]\displaystyle{ H }[/math] is represented by the variable [math]\displaystyle{ x_{i}. }[/math] For example, the triangle density in a graphon is given by

[math]\displaystyle{ t(K_3, W) = \int\limits_{[0,1]^3} W(x,y)W(y,z)W(z,x) dx dy dz }[/math].

This definition of homomorphism density is indeed a generalization, because for every graph [math]\displaystyle{ G }[/math] and its associated step graphon [math]\displaystyle{ W_{G} }[/math], [math]\displaystyle{ t(H,G)=t(H,W_{G}) }[/math].

The definition can be further extended to all symmetric, measurable functions [math]\displaystyle{ W }[/math]. The following example demonstrates the benefit of this further generalization. Relative to the function [math]\displaystyle{ W(x,y) = 2\cos(2\pi(x-y)) }[/math], the density of [math]\displaystyle{ H }[/math] in [math]\displaystyle{ W }[/math] is the number of Eulerian cycles in [math]\displaystyle{ H }[/math].

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 [math]\displaystyle{ t(K_{r},W)=0 }[/math], then [math]\displaystyle{ t(K_{2},W) \leq \left(1-\frac{1}{r-1}\right) }[/math]. A special case of this is Mantel's Theorem, which states that if [math]\displaystyle{ t(K_{3},W)=0 }[/math], then [math]\displaystyle{ t(K_{2},W)\leq 1/2 }[/math].

Goodman's Theorem

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

Theorem (Goodman). [math]\displaystyle{ t(K_3, G) \geq t(K_2, G)(2t(K_2, G) - 1). }[/math]

Kruskal-Katona Theorem

A converse inequality to Goodman's Theorem is a special case of Kruskal–Katona theorem, which states that [math]\displaystyle{ t(K_3, G) \leq t(K_2, G)^{3/2} }[/math]. 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 [math]\displaystyle{ G }[/math]. Say [math]\displaystyle{ G }[/math] is a graph on [math]\displaystyle{ n }[/math] vertices, and [math]\displaystyle{ \{\lambda_{i}\}_{i=1}^{n} }[/math] are the eigenvalues of its adjacency matrix [math]\displaystyle{ A_{G} }[/math]. By spectral graph theory, we know

[math]\displaystyle{ \operatorname{hom}(K_{2},G)=t(K_{2},G)|V(G)|^{2}=\sum_{i=1}^{n}\lambda_{i}^{2} }[/math], and [math]\displaystyle{ \operatorname{hom}(K_{3},G)=t(K_{3},G)|V(G)|^{3}=\sum_{i=1}^{n}\lambda_{i}^{3} }[/math].

The conclusion then comes from the following inequality:

[math]\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} }[/math].

Description of triangle vs edge density

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

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

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 [math]\displaystyle{ C_4 }[/math] to the complete bipartite graph [math]\displaystyle{ K_{1,2} }[/math]. Mathematically, this is formalized as

[math]\displaystyle{ \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} }[/math]

where we applied Cauchy-Schwarz to "fold" vertex 2 onto vertex 4. The same technique can be used to show [math]\displaystyle{ t(K_{1,2}, G) \geq t(K_2, G)^2 }[/math], which combined with the above verifies that [math]\displaystyle{ C_4 }[/math] 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

[math]\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 }[/math].

One useful fact is that a maximizing vector [math]\displaystyle{ x }[/math] is equally supported on the vertices of a clique in [math]\displaystyle{ H }[/math]. 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. 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 [math]\displaystyle{ a_{1},\cdots,a_{n} }[/math] be real constants. Then, the inequality

[math]\displaystyle{ \sum_{i=1}^{n}a_{i}t(K_{i},G)\geq 0 }[/math]

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

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 [math]\displaystyle{ H_{i} }[/math]:

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

[math]\displaystyle{ \sum_{i=1}^{n}a_{r}t(H_{i},G)\geq 0 }[/math]

holds for every graph [math]\displaystyle{ G }[/math].

A recent observation 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

• Common graph
• Sidorenko's conjecture