Jump to content

Counting lemma

From Wikipedia, the free encyclopedia

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)