In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities.
is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of
is a large fraction of all possible copies of
Common graphs are closely related to other graph notions dealing with homomorphism density inequalities.
For example, common graphs are a more general case of Sidorenko graphs.
[1] The inequality is tight because the lower bound is always reached when
Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,[2]
as roughly the fraction of labeled copies of graph
in "approximate" graph
and interpret the latter as the combined number of copies of
This, in turn, means that common graph
commonly appears as subgraph.
In other words, if we think of edges and non-edges as 2-coloring of edges of complete graph on the same vertices, then at least
Note that in a Erdős–Rényi random graph
with each edge drawn with probability
, each graph homomorphism from
So, common graph
is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph
The above definition using the generalized homomorphism density can be understood in this way.
is a Sidorenko graph if it satisfies
, which follows from the definition of homomorphism density.
Combining this with Jensen's inequality for the function
Thus, the conditions for common graph is met.
[8] Expand the integral expression for
and take into account the symmetry between the variables:
Each term in the expression can be written in terms of homomorphism densities of smaller graphs.
By the definition of homomorphism densities: where
denotes the complete bipartite graph on
where the last step follows from the integral Cauchy–Schwarz inequality.
This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"[9]