Counting lemma
The counting lemmas this article discusses are statements in combinatorics and graph theory. The first one extracts information from formula_1-regular pairs of subsets of vertices in a graph formula_2, in order to guarantee patterns in the entire graph; more explicitly, these patterns correspond to the count of copies of a certain graph formula_3 in formula_2. 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 Graph embedding version of counting lemma. Whenever we have an formula_1-regular pair of subsets  of vertices formula_6 in a graph formula_2, we can interpret this in the following way: the bipartite graph, formula_8, which has density formula_9, is "close" "to being" a random bipartite graph in which every edge appears with probability formula_9, with some formula_1 error. In a setting where we have several clusters of vertices, some of the pairs between these clusters being formula_12-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 formula_3 in formula_2, or more specifically, the number of copies of formula_3 in formula_2 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 and veridic statement of the theorem; for instance, the pairwise densities are at least formula_17, the cluster sizes are at least formula_18 , and formula_19. Being more careful of these details, the statement of the graph counting lemma is as follows: Statement of the theorem. If formula_3 is a graph with vertices formula_21 and formula_22 edges, and  formula_2 is a graph with (not necessarily disjoint) vertex subsets formula_24, such that formula_25 for all formula_26 and for every edge formula_27 of formula_3 the pair formula_29 is formula_12-regular with density formula_31 and formula_19, then formula_2 contains at least formula_34 many copies of formula_3 with the copy of vertex formula_36 in formula_37. This theorem is a generalization of the triangle counting lemma, which states the above but with formula_38: Triangle counting Lemma. Let formula_2 be a graph on formula_40 vertices, and let formula_41 be subsets of formula_42 which are pairwise formula_1-regular, and suppose the edge densities formula_44 are  all at least formula_45. Then the number of triples formula_46 such that formula_47 form a triangle in formula_2 is at leastformula_49 Section::::"Proof of triangle counting lemma:". Since formula_50 is a regular pair, less than formula_51 of the vertices in formula_52 have fewer than formula_53 neighbors in formula_54; otherwise, this set of vertices from formula_52 along with its neighbors in formula_54 would witness irregularity of formula_50, a contradiction. Intuitively, we are saying that not too many vertices in formula_52 can have a small degree in formula_54. By an analogous argument in the pair formula_60, less than formula_51 of the vertices in  formula_52 have fewer than formula_63 neighbors in formula_64. Combining these two subsets of formula_52 and taking their complement, we obtain a subset formula_66 of size at least formula_67 such that every vertex formula_68 has at least formula_53 neighbors in formula_54 and at least formula_63 neighbors in formula_64. We also know that formula_73, and that formula_74 is an formula_17-regular pair; therefore, the density between the neighborhood of formula_76 in formula_54 and the neighborhood of formula_76 in formula_64 is at least formula_80, because by regularity it is formula_17-close to the actual density between formula_54 and formula_64. Summing up, for each  of these at least formula_67 vertices formula_68, there are at least formula_86 choices of edges between the neighborhood of formula_76 in formula_54 and the neighborhood of formula_76 in formula_64. 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 formula_91 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 formula_92 of graphons is given the structure of a metric space where the metric is the cut distance formula_93. The following lemma is an important step in order to prove that formula_94 is a compact metric space. Intuitively, it says that for a graph formula_95, the homomorphism densities of two graphons with respect to this graph have to be close (this bound depending on the number of edges formula_95) if the graphons are close in terms of cut distance. Definition (cut norm).. The cut norm of formula_97 is defined as formula_98, where formula_99 and formula_100 are measurable  sets. Definition (cut distance).. The cut distance is defined as formula_101, where formula_102 represents formula_103 for a measure-preserving bijection formula_104. Graphon Counting Lemma. For graphons formula_105 and graph formula_95, we have formula_107, where formula_108 denotes the number of edges of graph formula_95. Section::::"Proof of the graphon counting lemma:". It suffices to prove formula_110Indeed, by considering the above, with the right hand side expression having a factor formula_111 instead of formula_112, and taking the infimum of the over all measure-preserving bijections formula_113, 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 formula_114 and formula_115:formula_116 Here's the reason for the above to hold: By taking formula_117 and formula_118, 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 formula_119, and by the fact that the extrema are attained for formula_119 taking values at formula_121 or formula_122. "Step 2: Proof for  formula_123." In the case that formula_123, we observe that formula_125 By Step 1, we have that for a fixed formula_126 thatformula_127Therefore, when integrating over all formula_128 we get that formula_129Using this bound on each of the three summands, we get that the whole sum is bounded by formula_130. "Step 3: General case." For a general graph formula_95, we need the following lemma to make everything more convenient: Lemma.. The following expression holds:formula_132 The above lemma follows from a straightforward expansion of the right hand side. Then, by the triangle inequality of norm, we have the followingformula_133 Here, each absolute  value term in the sum is bounded by the cut norm formula_134 if we fix all the variables except for formula_135 and formula_136 for each formula_36-th term, altogether implying that formula_138. This finishes the proof.