The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from -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 in . 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 .

Graph embedding version of counting lemma edit

Whenever we have an  -regular pair of subsets of vertices   in a graph  , we can interpret this in the following way: the bipartite graph,  , which has density  , is close to being a random bipartite graph in which every edge appears with probability  , with some   error.

In a setting where we have several clusters of vertices, some of the pairs between these clusters being  -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   in  , or more specifically, the number of copies of   in   formed by taking one vertex in each vertex cluster.

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  , the cluster sizes are at least   , and  . Being more careful of these details, the statement of the graph counting lemma is as follows:

Statement of the theorem edit

If   is a graph with vertices   and   edges, and   is a graph with (not necessarily disjoint) vertex subsets  , such that   for all   and for every edge   of   the pair   is  -regular with density   and  , then   contains at least   many copies of   with the copy of vertex   in  .

This theorem is a generalization of the triangle counting lemma, which states the above but with  :

Triangle counting Lemma edit

Let   be a graph on   vertices, and let   be subsets of   which are pairwise  -regular, and suppose the edge densities   are all at least  . Then the number of triples   such that   form a triangle in   is at least

 

Proof of triangle counting lemma: edit

Since   is a regular pair, less than   of the vertices in   have fewer than   neighbors in  ; otherwise, this set of vertices from   along with its neighbors in   would witness irregularity of  , a contradiction. Intuitively, we are saying that not too many vertices in   can have a small degree in  .

By an analogous argument in the pair  , less than   of the vertices in   have fewer than   neighbors in  . Combining these two subsets of   and taking their complement, we obtain a subset   of size at least   such that every vertex   has at least   neighbors in   and at least   neighbors in  .

We also know that  , and that   is an  -regular pair; therefore, the density between the neighborhood of   in   and the neighborhood of   in   is at least  , because by regularity it is  -close to the actual density between   and  .

Summing up, for each of these at least   vertices  , there are at least   choices of edges between the neighborhood of   in   and the neighborhood of   in  . From there we can conclude this proof.

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.[1]

Graphon version of counting lemma edit

The space   of graphons is given the structure of a metric space where the metric is the cut distance  . The following lemma is an important step in order to prove that   is a compact metric space. Intuitively, it says that for a graph  , 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.

Definition (cut norm). edit

The cut norm of   is defined as  , where   and   are measurable sets.

Definition (cut distance). edit

The cut distance is defined as  , where   represents   for a measure-preserving bijection  .

Graphon Counting Lemma edit

For graphons   and graph  , we have  , where   denotes the number of edges of graph  .

Proof of the graphon counting lemma: edit

It suffices to prove

 
Indeed, by considering the above, with the right hand side expression having a factor   instead of  , and taking the infimum of the over all measure-preserving bijections  , we obtain the desired result.

Step 1: Reformulation. 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   and  :

 

Here's the reason for the above to hold: By taking   and  , 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  , and by the fact that the extrema are attained for   taking values at   or  .

Step 2: Proof for  . In the case that  , we observe that

 

By Step 1, we have that for a fixed   that

 

Therefore, when integrating over all   we get that

 

Using this bound on each of the three summands, we get that the whole sum is bounded by  . Step 3: General case. For a general graph  , we need the following lemma to make everything more convenient:

Lemma. edit

The following expression holds:

 

The above lemma follows from a straightforward expansion of the right hand side. Then, by the triangle inequality of norm, we have the following

 

Here, each absolute value term in the sum is bounded by the cut norm   if we fix all the variables except for   and   for each  -th term, altogether implying that  . This finishes the proof.

See also edit

References edit

  1. ^ Conlon, Fox, David, Jacob. "Graph Removal Lemmas" (PDF). David Conlon's webpage. Archived (PDF) from the original on 2013-10-01.{{cite web}}: CS1 maint: multiple names: authors list (link)