is the set of graph homomorphisms, or adjacency preserving maps, from
Density can also be interpreted as the probability that a map from the vertices of
chosen uniformly at random is a graph homomorphism.
[2] 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.
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
, but our definition is asymptotically equivalent and simpler to analyze for our purposes.
However, not every homomorphism corresponds to a labeled copy − there are some degenerate cases, in which multiple vertices of
force all images under a graph homomorphism to be distinct.
The notion of homomorphism density can be generalized to the case where instead of a graph
, Note that the integrand is a product that runs over the edges in the subgraph
[1] The definition can be further extended to all symmetric, measurable functions
The following example demonstrates the benefit of this further generalization.
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.
A classic example is Turán's Theorem, which states that if
A special case of this is Mantel's Theorem, which states that if
An extension of Mantel's Theorem provides an explicit lower bound on triangle densities in terms of edge densities.
It turns out that both of these inequalities are tight for specific edge densities.
By spectral graph theory, we know The conclusion then comes from the following inequality:
His work from 2008 completes the understanding of a homomorphism inequality problem, the description of
.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.
As an example, we prove that the cycle of length 4 is Sidorenko.
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 quantity is defined to be One useful fact is that a maximizing vector
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).
[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
Then, it is an undecidable problem to determine whether the homomorphism density inequality
[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.