---
tag: WXB05RHWTY
kind: statement
role: proposition
name: Counting lemma
sources:
  - wikipedia: en:62471938@r1315423087
    locator: Counting lemma
    note: adopted
    mention: wikipedia://en/62471938
    sections: [Statement]
same_as:
  wikidata: Q111950818
  wikipedia: Counting lemma
inventory: [6MSDBYDB6V]
---

## Statement

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