Counting lemma

The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from [math]\displaystyle{ \epsilon }[/math]-regular pairs of subsets of vertices in a graph [math]\displaystyle{ G }[/math], in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math]. 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 [math]\displaystyle{ H }[/math].

Graph embedding version of counting lemma

Whenever we have an [math]\displaystyle{ \epsilon }[/math]-regular pair of subsets of vertices [math]\displaystyle{ U,V }[/math] in a graph [math]\displaystyle{ G }[/math], we can interpret this in the following way: the bipartite graph, [math]\displaystyle{ (U,V) }[/math], which has density [math]\displaystyle{ d(U,V) }[/math], is close to being a random bipartite graph in which every edge appears with probability [math]\displaystyle{ d(U,V) }[/math], with some [math]\displaystyle{ \epsilon }[/math] error.

In a setting where we have several clusters of vertices, some of the pairs between these clusters being [math]\displaystyle{ \gamma }[/math]-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 [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math], or more specifically, the number of copies of [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math] 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 [math]\displaystyle{ \varepsilon }[/math], the cluster sizes are at least [math]\displaystyle{ \gamma^{-1} }[/math] , and [math]\displaystyle{ \gamma\leq \varepsilon^{h}/4h }[/math]. Being more careful of these details, the statement of the graph counting lemma is as follows:

Statement of the theorem

If [math]\displaystyle{ H }[/math] is a graph with vertices [math]\displaystyle{ 1,\cdots,h }[/math] and [math]\displaystyle{ m }[/math] edges, and [math]\displaystyle{ G }[/math] is a graph with (not necessarily disjoint) vertex subsets [math]\displaystyle{ W_{1},\cdots,W_{h} }[/math], such that [math]\displaystyle{ |W_{i}|\geq\gamma^{-1} }[/math] for all [math]\displaystyle{ i=1,\ldots,h }[/math] and for every edge [math]\displaystyle{ (i,j) }[/math] of [math]\displaystyle{ H }[/math] the pair [math]\displaystyle{ (W_{i},W_{j}) }[/math] is [math]\displaystyle{ \gamma }[/math]-regular with density [math]\displaystyle{ d(W_{i},W_{j})\gt \varepsilon }[/math] and [math]\displaystyle{ \gamma\leq \varepsilon^{h}/4h }[/math], then [math]\displaystyle{ G }[/math] contains at least [math]\displaystyle{ 2^{-h}\varepsilon^{m}|W_{1}|\cdot\ldots\cdot|W_{h}| }[/math] many copies of [math]\displaystyle{ H }[/math] with the copy of vertex [math]\displaystyle{ i }[/math] in [math]\displaystyle{ W_{i} }[/math].

This theorem is a generalization of the triangle counting lemma, which states the above but with [math]\displaystyle{ H=K_{3} }[/math]:

Triangle counting Lemma

Let [math]\displaystyle{ G }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices, and let [math]\displaystyle{ X, Y, Z }[/math] be subsets of [math]\displaystyle{ V(G) }[/math] which are pairwise [math]\displaystyle{ \epsilon }[/math]-regular, and suppose the edge densities [math]\displaystyle{ d_{XY}, d_{XZ}, d_{YZ} }[/math] are all at least [math]\displaystyle{ 2\epsilon }[/math]. Then the number of triples [math]\displaystyle{ (x,y,z) \in X \times Y \times Z }[/math] such that [math]\displaystyle{ x, y, z }[/math] form a triangle in [math]\displaystyle{ G }[/math] is at least[math]\displaystyle{ (1-2\epsilon)(d_{XY}-\epsilon)(d_{XZ}-\epsilon)(d_{YZ}-\epsilon)|X||Y||Z|. }[/math]

Proof of triangle counting lemma:

Since [math]\displaystyle{ (X,Y) }[/math] is a regular pair, less than [math]\displaystyle{ \varepsilon|X| }[/math] of the vertices in [math]\displaystyle{ X }[/math] have fewer than [math]\displaystyle{ (d_{XY}-\varepsilon)|Y| }[/math] neighbors in [math]\displaystyle{ Y }[/math]; otherwise, this set of vertices from [math]\displaystyle{ X }[/math] along with its neighbors in [math]\displaystyle{ Y }[/math] would witness irregularity of [math]\displaystyle{ (X,Y) }[/math], a contradiction. Intuitively, we are saying that not too many vertices in [math]\displaystyle{ X }[/math] can have a small degree in [math]\displaystyle{ Y }[/math].

By an analogous argument in the pair [math]\displaystyle{ (X,Z) }[/math], less than [math]\displaystyle{ \varepsilon|X| }[/math] of the vertices in [math]\displaystyle{ X }[/math] have fewer than [math]\displaystyle{ (d_{XZ}-\varepsilon)|Z| }[/math] neighbors in [math]\displaystyle{ Z }[/math]. Combining these two subsets of [math]\displaystyle{ X }[/math] and taking their complement, we obtain a subset [math]\displaystyle{ X'\subseteq X }[/math] of size at least [math]\displaystyle{ (1-2\varepsilon)|X| }[/math] such that every vertex [math]\displaystyle{ x\in X' }[/math] has at least [math]\displaystyle{ (d_{XY}-\varepsilon)|Y| }[/math] neighbors in [math]\displaystyle{ Y }[/math] and at least [math]\displaystyle{ (d_{XZ}-\varepsilon)|Z| }[/math] neighbors in [math]\displaystyle{ Z }[/math].

We also know that [math]\displaystyle{ d_{XY},d_{XZ}\geq 2\varepsilon }[/math], and that [math]\displaystyle{ (Y,Z) }[/math] is an [math]\displaystyle{ \varepsilon }[/math]-regular pair; therefore, the density between the neighborhood of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ Y }[/math] and the neighborhood of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ Z }[/math] is at least [math]\displaystyle{ (d_{YZ}-\varepsilon) }[/math], because by regularity it is [math]\displaystyle{ \varepsilon }[/math]-close to the actual density between [math]\displaystyle{ Y }[/math] and [math]\displaystyle{ Z }[/math].

Summing up, for each of these at least [math]\displaystyle{ (1-2\varepsilon)|X| }[/math] vertices [math]\displaystyle{ x\in X' }[/math], there are at least [math]\displaystyle{ (d_{XY}-\epsilon)(d_{XZ}-\epsilon)(d_{YZ}-\epsilon)|Y||Z| }[/math] choices of edges between the neighborhood of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ Y }[/math] and the neighborhood of [math]\displaystyle{ x }[/math] in [math]\displaystyle{ Z }[/math]. 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 [math]\displaystyle{ H }[/math] 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.

Graphon version of counting lemma

The space [math]\displaystyle{ \tilde{\mathcal{W}}_0 }[/math] of graphons is given the structure of a metric space where the metric is the cut distance [math]\displaystyle{ \delta_{\Box} }[/math]. The following lemma is an important step in order to prove that [math]\displaystyle{ (\tilde{\mathcal{W}}_0, \delta_{\Box}) }[/math] is a compact metric space. Intuitively, it says that for a graph [math]\displaystyle{ F }[/math], the homomorphism densities of two graphons with respect to this graph have to be close (this bound depending on the number of edges [math]\displaystyle{ F }[/math]) if the graphons are close in terms of cut distance.

Definition (cut norm).

The cut norm of [math]\displaystyle{ W:[0,1]^2\to \mathbb{R} }[/math] is defined as [math]\displaystyle{ \|W\|_{\square} = \sup_{S, T\subseteq[0, 1]} \left|\int_{S\times T} W\right| }[/math], where [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] are measurable sets.

Definition (cut distance).

The cut distance is defined as [math]\displaystyle{ \delta_{\square}(U, W) = \inf_{\phi} ||U - W^{\phi}||_{\square} }[/math], where [math]\displaystyle{ W^{\phi}(x, y) }[/math] represents [math]\displaystyle{ W(\phi(x), \phi(y)) }[/math] for a measure-preserving bijection [math]\displaystyle{ \phi }[/math].

Graphon Counting Lemma

For graphons [math]\displaystyle{ W,U }[/math] and graph [math]\displaystyle{ F }[/math], we have [math]\displaystyle{ |t(F,W)-t(F,U)|\le |E(F)|\delta_{\square}(W,U) }[/math], where [math]\displaystyle{ |E(F)| }[/math] denotes the number of edges of graph [math]\displaystyle{ F }[/math].

Proof of the graphon counting lemma:

It suffices to prove [math]\displaystyle{ |t(F,W)-t(F,U)|\le|E(F)|\|W-U\|_{\square}. }[/math]Indeed, by considering the above, with the right hand side expression having a factor [math]\displaystyle{ \|W-U^{\phi}\|_{\Box} }[/math] instead of [math]\displaystyle{ \|W-U\|_{\Box} }[/math], and taking the infimum of the over all measure-preserving bijections [math]\displaystyle{ \phi }[/math], 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 [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]:[math]\displaystyle{ \sup_{S,T\subseteq [0,1]}\left|\int_{S\times T}W\right|=\sup_{u,v:[0,1]\rightarrow [0,1]}\left| \int_{[0,1]^2}W(x,y)u(x)v(y)dxdy\right|. }[/math]

Here's the reason for the above to hold: By taking [math]\displaystyle{ u=\mathbb{1}_S }[/math] and [math]\displaystyle{ u=\mathbb{1}_T }[/math], 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 [math]\displaystyle{ u,v }[/math], and by the fact that the extrema are attained for [math]\displaystyle{ u,v }[/math] taking values at [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math].

Step 2: Proof for [math]\displaystyle{ F=K_3 }[/math]. In the case that [math]\displaystyle{ F=K_3 }[/math], we observe that

[math]\displaystyle{ \begin{aligned} t(K_3,W)-t(K_3,U)&=\int_{[0,1]^{3}}((W(x,y)W(x,z)W(y,z)-U(x,y)U(x,z)U(y,z))dxdydz\\&=\int_{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\\&\qquad+\int_{[0,1]^{3}} U(x,y)(W-U)(x,z)W(y,z)dxdydz\\&\qquad+\int_{[0,1]^{3}} U(x,y)U(x,z)(W-U)(y,z)dxdydz. \end{aligned} }[/math]

By Step 1, we have that for a fixed [math]\displaystyle{ z }[/math] that

[math]\displaystyle{ \left|\int_{[0,1]^{2}}(W-U)(x,y)W(x,z)W(y,z)dxdy\right|\le \|W-U\|_{\square} }[/math]

Therefore, when integrating over all [math]\displaystyle{ z\in[0,1] }[/math] we get that

[math]\displaystyle{ \left|\int_{[0,1]^{3}}(W-U)(x,y)W(x,z)W(y,z)dxdydz\right|\le \|W-U\|_{\square} }[/math]

Using this bound on each of the three summands, we get that the whole sum is bounded by [math]\displaystyle{ 3\|W-U\|_{\square} }[/math]. Step 3: General case. For a general graph [math]\displaystyle{ F }[/math], we need the following lemma to make everything more convenient:

Lemma.

The following expression holds:[math]\displaystyle{ a_1a_2\cdots a_n-b_1b_2\cdots b_n=(a_1-b_1)a_2\cdots a_n+b_1(a_2-b_2)\cdots a_n+\cdots b_1b_2\cdots (a_n-b_n). }[/math]

The above lemma follows from a straightforward expansion of the right hand side. Then, by the triangle inequality of norm, we have the following[math]\displaystyle{ \begin{aligned} \left| t(F,W)-t(F,U)\right| &=\left| \int\left(\prod_{u_iv_i\in E(F)}W(u_i,v_i)-\prod_{u_iv_i\in E(F)}U(u_i,v_i)\right)\prod_{v\in V}dv\right|\\&\le\sum_{i=1}^{|E(F)|}\left| \int \left(\ \prod_{j=1}^{i-1}U(u_j,v_j)(W(u_i,v_i)-U(u_i,v_i))\prod_{k=i+1}^{|E(F)|}W(u_k,v_k)\right)\prod_{v\in V}dv\right|.\end{aligned} }[/math]

Here, each absolute value term in the sum is bounded by the cut norm [math]\displaystyle{ \|W-U\|_{\square} }[/math] if we fix all the variables except for [math]\displaystyle{ u_i }[/math] and [math]\displaystyle{ v_i }[/math] for each [math]\displaystyle{ i }[/math]-th term, altogether implying that [math]\displaystyle{ |t(F,W)-t(F,U)|\le |E(F)|\ \delta_{\square}(W,U) }[/math]. This finishes the proof.

See also

• Graph removal lemma