Graph removal lemma#Proof of the graph removal lemma

Let $H$ be a graph with $h$ vertices. The graph removal lemma states that for any $\backslash epsilon\; >\; 0$, there exists a constant $\backslash delta\; =\; \backslash delta(\backslash epsilon,\; H)\; >\; 0$ such that for any $n$-vertex graph $G$ with fewer than $\backslash delta\; n^h$ subgraphs isomorphic to $H$, it is possible to eliminate all copies of $H$ by removing at most $\backslash epsilon\; n^2$ edges from $G$.{{r|f11}}

File:Triangle removal lemma.svg to $H$ in this instance, and it is possible to eliminate all copies of $H$ by removing $\backslash epsilon\; n^2$ edges from $G$. This is only one of the many 6-vertex graphs $G$, so this only serves as an elementary upper bound.]]

An alternative way to state this is to say that for any $n$-vertex graph $G$ with $o(n^h)$ subgraphs isomorphic to $H$, it is possible to eliminate all copies of $H$ by removing $o(n^2)$ edges from $G$. Here, the $o$ indicates the use of little o notation.

In the case when $H$ is a triangle, resulting lemma is called triangle removal lemma.

The original motivation for the study of triangle removal lemma was the Ruzsa–Szemerédi problem. Its initial formulation due to Imre Z. Ruzsa and Szemerédi from 1978 was slightly weaker than the triangle removal lemma used nowadays and can be roughly stated as follows: every locally linear graph on $n$ vertices contains $o(n^2)$ edges.{{r|rs78}} This statement can be quickly deduced from a modern triangle removal lemma. Ruzsa and Szemerédi provided also an alternative proof of Roth's theorem on arithmetic progressions as a simple corollary.{{r|rs78}}

In 1986, during their work on generalizations of the Ruzsa–Szemerédi problem to arbitrary $r$-uniform graphs, Erdős, Frankl, and Rödl provided a statement for general graphs very close to the modern graph removal lemma: if graph $H\_2$ is a homomorphic image of $H\_2$, then any $H\_1$-free graph $G$ on $n$ vertices can be made $H\_2$-free by removing $o(n^2)$ edges.{{r|efr}}

The modern formulation of the graph removal lemma was first stated by Füredi in 1994.{{r|furedi94}} The proof generalized earlier approaches by Ruzsa and Szemerédi and Erdős, Frankl, and Rödl, also using the Szemerédi regularity lemma.

A key component of the proof of the graph removal lemma is the graph counting lemma about counting subgraphs in systems of regular pairs. The graph counting lemma is also very useful on its own. According to Füredi, it is used "in most applications of regularity lemma".{{r|furedi94}}

Let $H$ be a graph on $h$ vertices, whose vertex set is $V=\backslash \{1,2,\backslash ldots,h\backslash \}$ and edge set is $E$. Let $X\_1,X\_2,\backslash ldots,X\_h$ be sets of vertices of some graph $G$ such that, for all $ij\backslash in\; E$, the pair $(X\_i,X\_j)$ is $\backslash epsilon$-regular (in the sense of the regularity lemma). Let also $d\_\{ij\}$ be the density between the sets $X\_i$ and $X\_j$. Intuitively, a regular pair $(X,Y)$ with density $d$ should behave like a random Erdős–Rényi-like graph, where every pair of vertices $(x,y)\backslash in\; (X\backslash times\; Y)$ is selected to be an edge independently with probability $d$. This suggests that the number of copies of $H$ on vertices $x\_1,x\_2,\backslash ldots,x\_h$ such that $x\_i\backslash in\; X\_i$ should be close to the expected number from the Erdős–Rényi model,$$\backslash prod\_\{ij\backslash in\; E(H)\}d\_\{ij\}\backslash prod\_\{i\backslash in\; V(H)\}|X\_i|,$$where $E(H)$ and $V(H)$ are the edge set and the vertex set of $H$.

The straightforward formalization of the above heuristic claim is as follows. Let $H$ be a graph on $h$ vertices, whose vertex set is $V=\backslash \{1,2,\backslash ldots,h\backslash \}$ and whose edge set is $E$. Let $\backslash delta>0$ be arbitrary. Then there exists $\backslash epsilon>0$ such that for any $X\_1,X\_2,\backslash ldots,X\_h$ as above, satisfying $d\_\{ij\}>\backslash delta$ for all $ij\backslash in\; E$, the number of graph homomorphisms from $H$ to $G$ such that vertex $i\backslash in\; V(H)$ is mapped to $X\_i$ is not smaller than$$$$

(1-\delta)\prod_{ij\in E}(d_{ij}-\delta)\prod_{i\in V}|X_i|.

One can even find bounded-degree subgraphs of blow-ups of $H$ in a similar setting. The following claim appears in the literature under name of the blow-up lemma and was first proven by Komlós, Sárközy, and Szemerédi.{{r|kss97}} The precise statement here is a slightly simplified version due to Komlós, who referred to it also as the key lemma, as it is used in numerous regularity-based proofs.{{r|komlos99}}

Let $H\_1$ be an arbitrary graph and let $t\backslash in\backslash mathbb\{Z\}\_+$. Construct $H(t)$ by replacing each vertex $i$ of $H$ by an independent set $V\_i$ of size $t$ and replacing every edge $ij$ of $H$ by the complete bipartite graph on $(V\_i,V\_j)$. Let $\backslash epsilon,\backslash delta>0$ be arbitrary reals, let $N$ be a positive integer, and let $H\_2$ be a subgraph of $H(t)$ with $h$ vertices and maximum degree $\backslash Delta$. Define $\backslash epsilon\_0=\backslash delta^\backslash Delta/(2+\backslash Delta)$. Finally, let $G$ be a graph and $X\_1,X\_2,\backslash ldots,X\_h$ be disjoint sets of vertices of $G$ such that, whenever $ij\backslash in\; E(H\_2)$, then $(X\_i,X\_j)$ is a $\backslash epsilon$-regular pair with density at least $\backslash epsilon+\backslash delta$. Then if $\backslash epsilon\backslash leq\backslash epsilon\_0$ and $1-t\backslash leq\; N\backslash epsilon\_0$, then the number of injective graph homomorphisms from $H\_2$ to $G$ is at least $(\backslash epsilon\_0N)^h$.

In fact, one can restrict to counting only those homomorphisms such that any vertex $k\backslash in\; [h]$ of $H\_2$ with $k\backslash in\; V\_i$ is mapped to a vertex in $X\_i$.

We will provide a proof of the counting lemma in the case when $H$ is a triangle (triangle counting lemma). The proof of the general case, as well as the proof of the blow-up lemma, are very similar and do not require different techniques.

Take $\backslash epsilon=\backslash delta/2$. Let $X\_1\text{'}\backslash subset\; X\_1$ be the set of those vertices in $X\_1$ which have at least $(d\_\{12\}-\backslash epsilon)|X\_2|$ neighbors in $X\_2$ and at least $(d\_\{13\}-\backslash epsilon)|X\_3|$ neighbors in $X\_3$. Note that if there were more than $\backslash epsilon|X\_1|$ vertices in $X\_1$ with less than $(d\_\{12\}-\backslash epsilon)|X\_2|$ neighbors in $X\_2$, then these vertices together with the whole $X\_2$ would witness $\backslash epsilon$-irregularity of the pair $(X\_1,X\_2)$. Repeating this argument for $X\_3$ shows that we must have $|X\_1\text{'}|>(1-2\backslash epsilon)|X\_1|$. Now take an arbitrary $x\backslash in\; X\_1\text{'}$ and define $X\_2\text{'}$ and $X\_3\text{'}$ as neighbors of $x$ in $X\_2$ and $X\_3$, respectively. By definition, $|X\_2\text{'}|\backslash geq\; (d\_\{12\}-\backslash epsilon)|X\_2|\backslash geq\; \backslash epsilon|X\_2|$ and $|X\_3\text{'}|\backslash geq\; \backslash epsilon|X\_3|$, so by the regularity of $(X\_2,X\_3)$ we obtain existence of at least$$$$

(d_{23}-\epsilon)|X_2'||X_3'|\geq (d_{12}-\epsilon)(d_{23}-\epsilon)(d_{13}-\epsilon)|X_2||X_3|

triangles containing $x$. Since $x$ was chosen arbitrarily from the set $X\_1\text{'}$ of size at least $(1-2\backslash epsilon)|X\_1|$, we obtain a total of at least$$$$

(1-2\epsilon)|X_1| (d_{23}-\epsilon)|X_2'||X_3'|\geq (1-2\epsilon)(d_{12}-\epsilon)(d_{23}-\epsilon)(d_{13}-\epsilon)|X_1||X_2||X_3|,

which finishes the proof as $\backslash epsilon=\backslash delta/2$.

To prove the triangle removal lemma, consider an $\backslash epsilon/4$-regular partition $V\_1\; \backslash cup\; \backslash cdots\; \backslash cup\; V\_M$ of the vertex set of $G$. This exists by the Szemerédi regularity lemma. The idea is to remove all edges between irregular pairs, low-density pairs, and small parts, and prove that if at least one triangle still remains, then many triangles remain. Specifically, remove all edges between parts $V\_i$ and $V\_j$ if

{{bulleted list |$(V\_i,\; V\_j)$ is not $\backslash epsilon/4$-regular,|the density $d(V\_i,V\_j)$ is less than $\backslash epsilon/2$, or |either $V\_i$ or $V\_j$ has at most $(\backslash epsilon/4M)n$ vertices. |}}

This procedure removes at most $\backslash epsilon\; n^2$ edges. If there exists a triangle with vertices in $V\_i,\; V\_j,\; V\_k$ after these edges are removed, then the triangle counting lemma tells us there are at least$$\backslash left(1-\backslash frac\{\backslash epsilon\}\{2\}\backslash right)\backslash left(\backslash frac\{\backslash epsilon\}\{4\}\backslash right)^3\backslash left(\backslash frac\{\backslash epsilon\}\{4M\}\backslash right)^3\backslash cdot\; n^3$$triples in $V\_i\; \backslash times\; V\_j\; \backslash times\; V\_k$ which form a triangle. Thus, we may take

The proof of the case of general $H$ is analogous to the triangle case, and uses the graph counting lemma instead of the triangle counting lemma.

A natural generalization of the graph removal lemma is to consider induced subgraphs. In property testing, it is often useful to consider how far a graph is from being induced {{Mvar|H}}-free.{{r|removalsurvey}} A graph $G$ is considered to contain an induced subgraph $H$ if there is an injective map $f:\; V(H)\; \backslash rightarrow\; V(G)$ such that $(f(u),f(v))$ is an edge of $G$ if and only if $(u,v)$ is an edge of $H$. Notice that non-edges are considered as well. $G$ is induced $H$-free if there is no induced subgraph $G$. We define $G$ as $\backslash epsilon$-far from being induced $H$-free if we cannot add or delete $\backslash epsilon\; n^2$ edges to make $G$ induced $H$-free.

A version of the graph removal lemma for induced subgraphs was proved by Alon, Fischer, Krivelevich, and Szegedy in 2000.{{r|afk}} It states that for any graph $H$ with $h$ vertices and $\backslash epsilon\; >\; 0$, there exists a constant $\backslash delta\; >\; 0$ such that, if an $n$-vertex graph $G$ has fewer than $\backslash delta\; n^h$ induced subgraphs isomorphic to $H$, then it is possible to eliminate all induced copies of $H$ by adding or removing fewer than $\backslash epsilon\; n^2$ edges.

The problem can be reformulated as follows: Given a red-blue coloring $H\text{'}$ of the complete graph $K\_h$ (analogous to the graph $H$ on the same $h$ vertices where non-edges are blue and edges are red), and a constant $\backslash epsilon\; >\; 0$, then there exists a constant $\backslash delta\; >\; 0$ such that for any red-blue colorings of $K\_n$ has fewer than $\backslash delta\; n^h$ subgraphs isomorphic to $H\text{'}$, then it is possible to eliminate all copies of $H$ by changing the colors of fewer than $\backslash epsilon\; n^2$ edges. Notice that our previous "cleaning" process, where we remove all edges between irregular pairs, low-density pairs, and small parts, only involves removing edges. Removing edges only corresponds to changing edge colors from red to blue. However, there are situations in the induced case where the optimal edit distance involves changing edge colors from blue to red as well. Thus, the regularity lemma is insufficient to prove the induced graph removal lemma. The proof of the induced graph removal lemma must take advantage of the strong regularity lemma.{{r|afk}}

The strong regularity lemma{{r|afk}} is a strengthened version of Szemerédi's regularity lemma. For any infinite sequence of constants $\backslash epsilon\_0\backslash ge\; \backslash epsilon\_1\; \backslash ge\; ...>0$, there exists an integer $M$ such that for any graph $G$, we can obtain two (equitable) partitions $\backslash mathcal\{P\}$ and $\backslash mathcal\{Q\}$ such that the following properties are satisfied:

• $\backslash mathcal\{Q\}$ refines $\backslash mathcal\{P\}$; that is, every part of $\backslash mathcal\{P\}$ is the union of some collection of parts in $\backslash mathcal\{Q\}$.
• $\backslash mathcal\{P\}$ is $\backslash epsilon\_0$-regular and $\backslash mathcal\{Q\}$ is $\backslash epsilon\_$

  \mathcal{P}

  -regular.
• $|\backslash mathcal\{Q\}|\backslash le\; M$

The function $q$ is defined to be the energy function defined in Szemerédi regularity lemma. Essentially, we can find a pair of partitions $\backslash mathcal\{P\},\; \backslash mathcal\{Q\}$ where $\backslash mathcal\{Q\}$ is {{em|extremely}} regular compared to $\backslash mathcal\{P\}$, and at the same time $\backslash mathcal\{P\},\; \backslash mathcal\{Q\}$ are close to each other. This property is captured in the third condition.

The following corollary of the strong regularity lemma is used in the proof of the induced graph removal lemma.{{r|afk}} For any infinite sequence of constants $\backslash epsilon\_0\backslash ge\; \backslash epsilon\_1\; \backslash ge\; ...>0$, there exists $\backslash delta>0$ such that there exists a partition $\backslash mathcal\{P\}=\{V\_1,...,V\_k\}$ and subsets $W\_i\; \backslash subset\; V\_i$ for each $i$ where the following properties are satisfied:

• $|W\_i|>\backslash delta\; n$
• $(W\_i,W\_j)$ is $\backslash epsilon\_$

  \mathcal{P}

  -regular for each pair $i,j$
• $|d(W\_i,W\_j)-d(V\_i,V\_j)|\backslash le\; \backslash epsilon\_0$ for all but $\backslash epsilon\_0\; |\backslash mathcal\{P\}|^2$ pairs $i,j$

The main idea of the proof of this corollary is to start with two partitions $\backslash mathcal\{P\}$ and $\backslash mathcal\{Q\}$ that satisfy the Strong Regularity Lemma where

The important aspect of this corollary is that {{em|every}} pair of $W\_i,W\_j$ is $\backslash epsilon\_$

With these results, we are able to prove the induced graph removal lemma. Take any graph $G$ with $n$ vertices that has less than $\backslash delta\; n^\{v(H)\}$ copies of $H$. The idea is to start with a collection of vertex sets $W\_i$ which satisfy the conditions of the Corollary of the Strong Regularity Lemma.{{r|afk}} We then can perform a "cleaning" process where we remove all edges between pairs of parts $(W\_i,W\_j)$ with low density, and we can add all edges between pairs of parts $(W\_i,W\_j)$ with high density. We choose the density requirements such that we added/deleted at most $\backslash epsilon\; n^2$ edges.

If the new graph has no copies of $H$, then we are done. Suppose the new graph has a copy of $H$. Suppose the vertex $v\_i\; \backslash in\; v(H)$ is embedded in $W\_\{f(i)\}$. Then if there is an edge connecting $v\_i,v\_j$ in $H$, then $W\_i,W\_j$ does not have low density. (Edges between $W\_i,W\_j$ were not removed in the cleaning process.) Similarly, if there is not an edge connecting $v\_i,v\_j$ in $H$, then $W\_i,W\_j$ does not have high density. (Edges between $W\_i,W\_j$ were not added in the cleaning process.)

Thus, by a similar counting argument to the proof of the triangle counting lemma (that is, the graph counting lemma), we can show that $G$ has more than $\backslash delta\; n^\{v(H)\}$ copies of $H$.

The graph removal lemma was later extended to directed graphs{{r|as}} and to hypergraphs.{{r|tao}}

The usage of the regularity lemma in the proof of the graph removal lemma forces $\backslash delta$ to be extremely small, bounded by a tower function whose height is polynomial in $\backslash epsilon^\{-1\}$; that is, $\backslash delta=1/\backslash text\{tower\}(\backslash epsilon^\{-O(1)\})$ (here $\backslash text\{tower\}(k)$ is the tower of twos of height $k$). A tower function of height $\backslash epsilon^\{-O(1)\}$ is necessary in all regularity proofs, as is implied by results of Gowers on lower bounds in the regularity lemma.{{r|gowers97}} However, in 2011, Fox provided a new proof of the graph removal lemma which does not use the regularity lemma, improving the bound to $\backslash delta=1/\backslash text\{tower\}(5h^2\backslash log\backslash epsilon^\{-1\})$ (here $h$ is the number of vertices of the removed graph $H$).{{r|f11}} His proof, however, uses regularity-related ideas such as energy increment, but with a different notion of energy, related to entropy. This proof can be also rephrased using the Frieze-Kannan weak regularity lemma as noted by Conlon and Fox.{{r|removalsurvey}} In the special case of bipartite $H$, it was shown that $\backslash delta=\backslash epsilon^\{O(1)\}$ is sufficient.

There is a large gap between the available upper and lower bounds for $\backslash delta$ in the general case. The current best result true for all graphs $H$ is due to Alon and states that, for each nonbipartite $H$, there exists a constant $c>0$ such that is necessary for the graph removal lemma to hold, while for bipartite $H$, the optimal $\backslash delta$ has polynomial dependence on $\backslash epsilon$, which matches the lower bound. The construction for the nonbipartite case is a consequence of Behrend construction of large Salem-Spencer sets. Indeed, as the triangle removal lemma implies Roth's theorem, existence of large Salem-Spencer sets may be translated to an upper bound for $\backslash delta$ in the triangle removal lemma. This method can be leveraged for arbitrary nonbipartite $H$ to give the aforementioned bound.

{{bulleted list |Ruzsa and Szemerédi formulated the triangle removal lemma to provide subquadratic upper bounds on the Ruzsa–Szemerédi problem on the size of graphs in which every edge belongs to a unique triangle. This leads to a proof of Roth's theorem.{{r|roth}} |The triangle removal lemma can also be used to prove the corners theorem, which states that any subset of $[n]^2$ which contains no axis-aligned isosceles right triangle has size $o(n^2)$.{{r|s03}}| The hypergraph removal lemma can be used to prove Szemerédi's theorem on the existence of long arithmetic progressions in dense subsets of integers.{{r|tao}}|}}

{{bulleted list |The graph counting/removal lemma can be used to provide a quick and transparent proof of the Erdős–Stone theorem starting from Turán's theorem and to extend the result to Simonovits stability: for any graph $H$ and any $\backslash epsilon>0$, there exists $\backslash delta$ such that any $H$-free graph on $n$ vertices with at least $\backslash left(1-\backslash frac\{1\}\{\backslash chi(H)-1\}\backslash right)\backslash binom\{n\}\{2\}-\backslash delta\; n^2$ edges can be transformed into a complete $(\backslash chi(H)-1)$-partite Turán graph $T\_\{n,\backslash chi(H)-1\}$ by adding or deleting at most $\backslash epsilon\; n^2$ edges (here $\backslash chi(H)$ is the chromatic number of $H$).{{r|alon01}} Although both results had been proven earlier using more elementary techniques (the Erdős–Stone theorem was proved in 1966{{r|es66}} by Erdős and Stone while Simonovits stability was shown in the same year by various authors{{r|es66}}{{r|erdos66}}{{r|erdos66_2}}{{r|ek66}}), the regularity proof provides a different viewpoint and elucidates connection with other modern proofs.|The graph removal lemma together with the Erdős–Stone theorem may be used to show that the number of non-isomorphic $H$-free graphs on $n$ vertices is equal to

$$2^\{(\backslash pi(H)+o(1))\backslash binom\{n\}\{2\}\},$$

where $\backslash pi(H)=1-\backslash frac\{1\}\{\backslash chi(H)-1\}$ is the Turán density of $H$.{{r|efr}}|}}

{{bulleted list |The graph removal lemma has applications for property testing, because it implies that for every graph, either the graph is near an $H$-free graph, or random sampling will easily find a copy of $H$ in the graph.{{r|as}} One result is that for any fixed $\backslash epsilon\; >\; 0$, there is a constant-time algorithm that determines with high probability whether or not a given $n$-vertex graph $G$ is $\backslash epsilon$-far from being $H$-free.{{r|as08}} Here, $\backslash epsilon$-far from being $H$-free means that at least $\backslash epsilon\; n^2$ edges must be removed to eliminate all copies of $H$ in $G$. |The induced graph removal lemma was formulated by Alon, Fischer, Krivelevich, and Szegedy to characterize testable graph properties.{{r|afk}}|}}

• Counting lemma
• Tuza's conjecture
• Graph edit distance

{{reflist|refs=

{{citation

| last1 = Alon | first1 = Noga | author1-link = Noga Alon

| last2 = Fischer | first2 = Eldar

| last3 = Krivelevich | first3 = Michael | author3-link = Michael Krivelevich

| last4 = Szegedy | first4 = Mario | author4-link = Mario Szegedy

| doi = 10.1007/s004930070001

| issue = 4

| journal = Combinatorica

| mr = 1804820

| pages = 451–476

| title = Efficient testing of large graphs

| volume = 20

| year = 2000

| s2cid = 44645628 }}

{{citation

| last1 = Alon | first1 = Noga | author1-link = Noga Alon

| last2 = Shapira | first2 = Asaf

| doi = 10.1016/j.jcss.2004.04.008

| issue = 3

| journal = Journal of Computer and System Sciences

| mr = 2087940

| pages = 353–382

| title = Testing subgraphs in directed graphs

| volume = 69

| year = 2004| doi-access = free

}}

{{citation

| last1 = Alon | first1 = Noga | author1-link = Noga Alon

| last2 = Shapira | first2 = Asaf

| doi = 10.1137/06064888X

| issue = 6

| journal = SIAM Journal on Computing

| mr = 2386211

| pages = 1703–1727

| title = A characterization of the (natural) graph properties testable with one-sided error

| volume = 37

| year = 2008}}

{{citation

| last1 = Erdős | first1 = P. | author1-link = Paul Erdős

| last2 = Frankl | first2 = P. | author2-link = Peter Frankl

| last3 = Rödl | first3 = V. | author3-link = Vojtěch Rödl

| doi = 10.1007/BF01788085

| issue = 2

| journal = Graphs and Combinatorics

| mr = 932119

| pages = 113–121

| title = The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent

| volume = 2

| year = 1986| s2cid = 16839886 }}

{{citation

| last = Fox | first = Jacob | authorlink = Jacob Fox

| doi = 10.4007/annals.2011.174.1.17

| issue = 1

| journal = Annals of Mathematics

| mr = 2811609

| pages = 561–579

| series = Second Series

| title = A new proof of the graph removal lemma

| volume = 174

| year = 2011| arxiv = 1006.1300

| s2cid = 8250133 }}

{{citation

| last = Roth | first = K. F. | authorlink = Klaus Roth

| doi = 10.1112/jlms/s1-28.1.104

| issue = 1

| journal = Journal of the London Mathematical Society

| mr = 51853

| pages = 104–109

| volume = 28

| title = On certain sets of integers

| year = 1953

}}

{{citation

| last1 = Ruzsa | first1 = I. Z. | author1-link = Imre Z. Ruzsa

| last2 = Szemerédi | first2 = E. | author2-link = Endre Szemerédi

| contribution = Triple systems with no six points carrying three triangles

| mr = 519318

| pages = 939–945

| publisher = North-Holland | location = Amsterdam and New York

| series = Colloq. Math. Soc. János Bolyai

| title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II

| volume = 18

| year = 1978}}

{{citation

| last = Solymosi | first = J. | author-link = József Solymosi

| s2cid = 53973423

| doi = 10.1007/978-3-642-55566-4_39

| journal = Discrete and Computational Geometry

| mr = 2038505

| pages = 825–827

| title = Note on a generalization of Roth's theorem

| volume = 25

| year = 2003

| series = Algorithms and Combinatorics

| isbn = 978-3-642-62442-1

}}

{{citation

| last = Tao | first = Terence | authorlink = Terence Tao

| doi = 10.1016/j.jcta.2005.11.006

| issue = 7

| journal = Journal of Combinatorial Theory

| mr = 2259060

| pages = 1257–1280

| series = Series A

| title = A variant of the hypergraph removal lemma

| volume = 113

| year = 2006| arxiv = math/0503572

| s2cid = 14337591 }}

{{citation|url=https://lucatrevisan.wordpress.com/2009/05/13/the-triangle-removal-lemma/|title=The Triangle Removal Lemma|work=in theory|first=Luca|last=Trevisan|authorlink=Luca Trevisan|date=May 13, 2009}}

{{citation

| last1 = Conlon | first1 = David | author1-link = David Conlon

| last2 = Fox | first2 = Jacob | author2-link = Jacob Fox

| editor1-last = Blackburn | editor1-first = Simon R.

| editor2-last = Gerke | editor2-first = Stefanie

| editor3-last = Wildon | editor3-first = Mark

| arxiv = 1211.3487

| contribution = Graph removal lemmas

| doi = 10.1017/CBO9781139506748.002

| mr = 3156927

| pages = 1–49

| publisher = Cambridge University Press | location = Cambridge, UK

| series = London Mathematical Society Lecture Note Series

| title = Surveys in Combinatorics 2013

| volume = 409

| year = 2013| isbn = 978-1-107-65195-1 | s2cid = 2658118 }}

{{Cite book|last=Füredi|first=Zoltán|chapter=Extremal Hypergraphs and Combinatorial Geometry |date=1995|editor-last=Chatterji|editor-first=S. D.|title=Proceedings of the International Congress of Mathematicians|chapter-url=https://link.springer.com/chapter/10.1007/978-3-0348-9078-6_129|language=en|location=Basel|publisher=Birkhäuser|pages=1343–1352|doi=10.1007/978-3-0348-9078-6_129|isbn=978-3-0348-9078-6}}

{{Cite journal|last=Komlós|first=János|date=1999|title=The Blow-up Lemma|url=https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/blowup-lemma/1F094FCD0A272B5FBE5B1E5D0583E8D3|journal=Combinatorics, Probability and Computing|language=en|volume=8|issue=1–2|pages=161–176|doi=10.1017/S0963548398003502|s2cid=6720143 |issn=1469-2163}}

{{Cite journal|last1=Komlós|first1=János|last2=Sárközy|first2=Gábor N.|last3=Szemerédi|first3=Endre|date=1997-03-01|title=Blow-up Lemma|url=https://doi.org/10.1007/BF01196135|journal=Combinatorica|language=en|volume=17|issue=1|pages=109–123|doi=10.1007/BF01196135|s2cid=6720143|issn=1439-6912}}

{{Cite journal|last=Gowers|first=W. T.|date=1997|title=Lower bounds of tower type for Szemerédi's uniformity lemma|journal=Geometric and Functional Analysis|volume=7|issue=2|pages=322–337|doi=10.1007/PL00001621|s2cid=115242956}}

{{Cite book|last=Alon|first=N.|title=Proceedings 42nd IEEE Symposium on Foundations of Computer Science |chapter=Testing subgraphs in large graphs |date=2001-10-14|chapter-url=https://dl.acm.org/doi/10.5555/874063.875540|series=FOCS '01|location=USA|publisher=IEEE Computer Society|pages=434–441|doi=10.1109/SFCS.2001.959918|isbn=978-0-7695-1390-4|s2cid=12484006}}

{{Cite journal

| last1 = Erdős | first1 = P. | author1-link = Paul Erdős

| last2 = Simonovits | first2 = M. | author2-link = Miklós Simonovits

| year = 1966

| title = A limit theorem in graph theory

| pages = 51–57

| volume = 1

| journal = Studia Sci. Math. Hung.

}}

{{Cite journal

| last = Erdős | first = P. | author-link = Paul Erdős

| year = 1966

| title = Some recent results on extremal problems in graph theory

| pages = 118–123

| journal = Theory of Graphs, International Symp. Rome

}}

{{Cite journal

| last = Erdős | first = P. | author-link = Paul Erdős

| year = 1966

| title = On some new inequalities concerning extremal properties of graphs

| pages = 77–81

| journal = Theory of Graphs, Proc. Coll. Tihany, Hungary

}}

{{Cite journal

| last1 = Erdős | first1 = P. | author1-link = Paul Erdős

| last2 = Katona | first2 = G. | author2-link = Gyula O. H. Katona

| year = 1966

| title = A method for solving extremal problems in graph theory

| pages = 279–319

| journal = Theory of Graphs, Proc. Coll. Tihany

}}

}}

Category:Theorems in graph theory