The counting lemmas this article discusses are statements in combinatorics and graph theory.
-regular pairs of subsets of vertices in a graph
, in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph
The second counting lemma provides a similar yet more general notion on the space of graphons, in which a scalar of the cut distance between two graphs is correlated to the homomorphism density between them and
, we can interpret this in the following way: the bipartite graph,
, is close to being a random bipartite graph in which every edge appears with probability
-regular, we would expect the count of small, or local patterns, to be roughly equal to the count of such patterns in a random graph.
These small patterns can be, for instance, the number of graph embeddings of some
The above intuition works, yet there are several important conditions that must be satisfied in order to have a complete statement of the theorem; for instance, the pairwise densities are at least
Being more careful of these details, the statement of the graph counting lemma is as follows: If
is a graph with (not necessarily disjoint) vertex subsets
This theorem is a generalization of the triangle counting lemma, which states the above but with
-regular, and suppose the edge densities
and taking their complement, we obtain a subset
Idea of proof of graph counting lemma:The general proof of the graph counting lemma extends this argument through a greedy embedding strategy; namely, vertices of
are embedded in the graph one by one, by using the regularity condition so as to be able to keep a sufficiently large set of vertices in which we could embed the next vertex.
The following lemma is an important step in order to prove that
, the homomorphism densities of two graphons with respect to this graph have to be close (this bound depending on the number of edges
) if the graphons are close in terms of cut distance.
denotes the number of edges of graph
Indeed, by considering the above, with the right hand side expression having a factor
, and taking the infimum of the over all measure-preserving bijections
We prove a reformulation of the cut norm, which is by definition the left hand side of the following equality.
The supremum in the right hand side is taken among measurable functions
, we note that the left hand side is less than or equal than the right hand side.
The right hand side is less than or equal than the left hand side by bilinearity of the integrand in
Step 3: General case.
, we need the following lemma to make everything more convenient: The following expression holds:
The above lemma follows from a straightforward expansion of the right hand side.
Here, each absolute value term in the sum is bounded by the cut norm