Homomorphism density


In the mathematical field of extremal graph theory, homomorphism density with respect to a graph is a parameter that is associated to each graph in the following manner:
Above, is the set of graph homomorphisms, or adjacency preserving maps, from to. Density can also be interpreted as the probability that a map from the vertices of to the vertices of chosen uniformly at random is a graph homomorphism. There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.

Examples

We define the subgraph density of in to be
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 vertices of, but our definition is asymptotically equivalent and simpler to analyze for our purposes. Observe that any labeled copy of in corresponds to a homomorphism of into. However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of are sent to the same vertex of. That said, the number of such degenerate homomorphisms is only, so we have. For instance, we see that for graphs with constant homomorphism density, the labeled subgraph density and homomorphism density are asymptotically equivalent. For being a complete graph, the homomorphism density and subgraph density are in fact equal, as the edges of 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, we have a graphon,
Note that the integrand is a product that runs over the edges in the subgraph, whereas the differential is a product running over the vertices in. Intuitively, each vertex in is represented by the variable.
For example, the triangle density in a graphon is given by
.
This definition of homomorphism density is indeed a generalization, because for every graph and its associated step graphon,.
This notion is helpful in understanding assymptotical behavior of homomorphism densities of graphs which satisfy certain property, since a graphon is a limit of a sequence of graphs.

Important results: inequalities

Many results in extremal graph theory can be described by inequalities involving homomorphism densities associated to a graph. For instance, Mantel's Theorem states, in the context of graphons, that if, then. Another example is Turán's Theorem, which states that if, then.
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. Let be real constants. Then, the inequality
holds for every graph if and only if it holds for every complete graph.

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 :
Theorem. Let be real constants, and graphs. Then, it is an undecidable problem to determine whether the homomorphism density inequality
holds for every graph.
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.

Description of D_{2,3}

Another recent development consists in the completion of the understanding of a homomorphism inequality problem, the description of, which is the region of feasible edge density, triangle density pairs in a graphon:
Observation 1. This region is closed, since the limit of a sequence o graphs is a graphon.
Observation 2. For every, the set is a vertical line segment, with no gaps.
Proof: Consider two graphons, with the same edge density; then, the family of graphons of the following form, as varies from 0 to 1
achieves every possible triangle density between the values and, by continuity of this map.
Observation 3. For every, graphon, we have the upper bound
Proof: It is sufficient to prove this inequality for any graph. Say is a graph on vertices, and are the eigenvalues of its adjacency matrix. By spectral graph theory, we know
,
The conclusion then comes from the following inequality:
Observation 3. The extremal points of the convex hull of
are given by for each positive integer. In particular, The extrema of are given by the following discrete set of points in the curve :
Observation 3. This is a theorem due to Razborov, which states that for a given edge density, if
for some positive integer, then the minimum feasible triangle density is attained by a unique step function graphon with node weights with sum equal to 1 and such that. More explicitly, the minimum possible is