Removal lemmas in sparse graphs
Abstract
In this work we explain and prove the graph removal lemma, both in its dense and sparse cases, and show how these can be applied to finite groups to obtain arithmetic removal lemmas. We show how the concept of regularity plays a crucial role in the proof of the removal lemma. We explain the motivation behind the sparse case, and the importance of pseudorandom graphs in sparse versions of the removal lemma. Finally, we show how the removal lemma, both in its graph and arithmetic versions, can be used to prove Roth's theorem, that is, the existence of 3-term arithmetic progressions in any dense subset of the natural numbers.
Full text
Title: Removal lemmas in sparse graphs Author: Ander Lamaison Vidarte Advisors: Oriol Serra Albo, Lluís Vena Cros Department: Applied Mathematics IV Academic year: 2014/2015 Degree in Mathematics
Universitat Politècnica de Catalunya Facultat de Matemàtiques i Estadística Bachelor’s Degree Thesis Removal lemmas in sparse graphs Ander Lamaison Vidarte Advisors: Oriol Serra Albo Lluís Vena Cros Departament de Matemàtica Aplicada IV
This work is dedicated to my family, for providing me with unconditional support all these years, and to everyone who has helped me in the path through university.
v Abstract Key words: Pseudorandom, regularity lemma, removal lemma, sparse graphs MSC2010: 05C35, 05C80 The aim of this work is to explain and prove the graph removal lemma, in both the dense and the sparse cases, and show how these can be applied to finite groups to obtain arithmetic removal lemmas. The graph removal lemma, in its most basic form, states that for any fixed graph H, if a graph Gon nvertices contains o(nv(H)) copies of H, then all copies can be deleted from Gby deleting o(n2)edges. We will show how the concept of regularity, and the regularity and counting lemmas, are crucial in the proof of the removal lemmas. We will explain the motivation behind the development of the sparse case, and the role of pseudorandom graphs in sparse versions of the removal lemma. Finally, we will see how the removal lemma, both in its graph and its arithmetic versions, can be used to prove Roth’s theorem, that is, the existence of non-trivial 3-term arithmetic progressions in any subset of the natural numbers with positive density.
vi Removal lemmas in sparse graphs
Notation [n]{1, 2, ..., n} E(G)Set of edges of graph G V(G)Set of vertices of graph G e(G)Number of edges of graph G v(G)Number of vertices of graph G
Contents Chapter 1. Introduction 1 Chapter 2. Removal lemma in dense graphs 3 2.1. The regularity lemma 4 2.2. The counting lemma 11 2.3. The removal lemma 13 2.4. Applications 16 Chapter 3. Sparse pseudorandom graphs 21 3.1. Motivation 21 3.2. Pseudorandom graphs 23 3.3. The regularity lemma 25 3.4. The counting lemma 34 3.5. The removal lemma 56 3.6. Application: The sparse arithmetic removal lemma 58 3.7. Concluding remarks 60 References 61 i
ii Removal lemmas in sparse graphs
Chapter 1 Introduction The origins of the removal lemma can be traced back to a conjecture proposed by Erd˝os and Turán in 1936 [ErdTur]. This conjecture asked whether any subset of Nin which the sum of the reciprocals of the elements is divergent necessarily contains a non-trivial k-term arithmetic progression for all positive integers k. An interesting particular case of this conjecture is whether this holds for subsets of Nof positive density. This is a result known today as Szemerédi’s Theorem on arithmetic progressions: for any density e>0, subsets of [n]with density at least e, for nlarge enough, always contain k-term arithmetic progressions. The first answer for the dense case came in 1953, when Roth [Rot] proved the case k=3 using Fourier analysis. In the seventies, Szemerédi proved the result for general kusing combinatorial methods [Sze2]. This proof introduced a tool that would be of great relevance in extremal combinatorics: regularity in graphs, and in particular the regularity lemma. The concept of regularity is one of equidistribution of edges. We say that a graph is regular when the density of edges between any two large enough sets of vertices is approximately the same as the density of the entire graph. A partition of the vertex set of the graph is said to be regular if almost all of the pairs of parts are regular, and the parts are of the same size. From the many results involving regularity that have been proven since it was introduced, the two that we will use are the regularity lemma and the counting lemma. The regularity lemma states that any graph admits a regular partition, and there is an upper bound on the number of parts required [Sze3]. Meanwhile, the counting lemma gives a lower bound on the number of embeddings of a graph Hinto a regular partition, under certain conditions [KomSim]. The combination of both lemmas produces the central result of this thesis: the graph removal lemma [RuzSze,Fur]: Theorem 2.1 (Removal lemma). Let e>0 be a constant and Hbe a graph on hvertices. Then there exists δ>0 for which the following property holds: any graph Gon nvertices, which contains at most δnhcopies of H, can be made H-free (not containing any copies of H) by removing at most en2edges. This lemma has many applications, one of which is that it allows for a straightforward proof of Roth’s theorem (the case k=3 of Szemerédi’s theorem) [Rot,RuzSze]. In fact, a generalization of 1
8 Removal lemmas in sparse graphs Proof. By expanding the formulas for q(A,B)and q(A0,B0), we obtain q(A0,B0) = ∑ A0∈˜ A0 ∑ B0∈˜ B0 q(A0,B0) =∑ A∈˜ A ∑ B∈˜ B ∑ A0∈˜ A0 A0⊂A ∑ B0∈˜ B0 B0⊂B q(A0,B0) =∑ A∈˜ A ∑ B∈˜ B ∑ A0∈˜ A0 A0⊂A ∑ B0∈˜ B0 B0⊂B |A0||B0| n2d2(A0,B0) (2) ≥∑ A∈˜ A ∑ B∈˜ B ∑ A0∈˜ A0 A0⊂A ∑ B0∈˜ B0 B0⊂B |A0||B0| n2d2(A,B) =∑ A∈˜ A ∑ B∈˜ B |A||B| n2d2(A,B) =∑ A∈˜ A ∑ B∈˜ B q(A,B) =q(A,B) ut Corollary 2.8. If Pand P0are two partitions of V such that P0refines P, then q(P0)≥q(P) Proof. q(P0) = q(P0,P0)≥q(P,P) = q(P)ut This shows that, if we take a sequence of partitions, each of which refines the previous ones, then q(P)is non-decreasing. The second step, which is the key step, consists of showing that, if a partition is equitable but not e-regular, then we can increase q(P)by a constant depending only on e. Lemma 2.9. Let 0<e<1 2and let P={Xi}k i=0be an equitable partition of V with exceptional set V0and k non-exceptional sets. If |X0|<e|V|and the partition is not e-regular, then there is another partition P0, not necessarily equitable, with at most k4knon-exceptional parts, the same exceptional set X0 and q(P0)≥q(P) + e5 4. Proof. Let S={(i,j)∈[k]2:(Xi,Xj)is not e-regular}. If Pis not e-regular, then ek2≤ |S| ≤ k2. For every pair (i,j)that is not e-regular, by definition of regularity, there are sets Xj i⊂Xiand X[i] j⊂Xjsuch that |Xj i| ≥ e|Xi|,|X[i] j| ≥ e|Xj|and |d(Xj i,X[i] j)−d(Xi,Xj)| ≥ e. Now take P0to be the coarsest partition that refines all the sets Xj iand X[i] j. Within each set Xi there are at most ksets Xj iand ksets X[j] i, which means that the coarsest partition of Xithat refines all those sets has at most 22k=4ksets, so the partition P0requires no more than k4knonexceptional sets. Denote by ˜ P0(X)the partition of X∈˜ Pin ˜ P0, and by Pi(X)the partition of Xi into two sets induced by X⊂Xi.
9 q(P0)−q(P) = ∑ A0∈˜ P0 ∑ B0∈˜ P0 q(A0,B0)−∑ A∈˜ P ∑ B∈˜ P q(A,B) =∑ A∈˜ P ∑ B∈˜ P q(˜ P0(A),˜ P0(B)) −∑ A∈˜ P ∑ B∈˜ P q(A,B) Only taking the irregular pairs: 2.7 ≥∑ (i,j)∈Sq(˜ P0(Xi),˜ P0(Xj)) −q(Xi,Xj) 2.7 ≥∑ (i,j)∈SqPi(Xj i),PjX[i] j−q(Xi,Xj) (∗) ≥∑ (i,j)∈Se 2k2e2 ≥(ek2)e 2k2e2 =e5 4 where inequality (*) is detailed here: qPi(Xj i),PjX[i] j−q(Xi,Xj) =∑ A∈Pi(Xj i) ∑ B∈PjX[i] j q(A,B)−q(Xi,Xj) =∑ A∈Pi(Xj i) ∑ B∈PjX[i] j |A||B| n2d2(A,B)−|Xi||Xj| n2d2(Xi,Xj) =∑ A∈Pi(Xj i) ∑ B∈PjX[i] j |A||B| n2d2(A,B)−d2(Xi,Xj) (1) =∑ A∈Pi(Xj i) ∑ B∈PjX[i] j |A||B| n2d2(A,B)−d2(Xi,Xj)−2d(A,B)d(Xi,Xj) + 2d2(Xi,Xj) =∑ A∈Pi(Xj i) ∑ B∈PjX[i] j |A||B| n2d(A,B)−d(Xi,Xj)2 ≥|Xj i||X[i] j| n2d(Xj i,X[i] j)−d(Xi,Xj)2 ≥e 2k2e2ut
10 Removal lemmas in sparse graphs This completes the second step. The number of parts could be reduced to k2k+1because we can make Xj i=X[j] iwhenever i6=j, but here we are not trying to optimize our bounds, we just want to show that they exist. The third step concerns equitable refinements of partitions. Lemma 2.10. Let P={Xi}k i=0be a (not necessarily equitable) partition of V with exceptional set X0, and let δ>0. Then there exists an equitable partition P0={X0 i}k0 i=0with exceptional set X0 0which refines P, with k0≤δ−1k and |X0 0|≤|X0|+δ|V|. Proof. Let m=δk−1|V|. To construct P0, partition each set Xiwith 1 ≤i≤kinto sets of size m, and if |Xi|is not divisible by m, add the remaining vertices to the exceptional set X0 0. Once we have done this, every non-exceptional set has size m, so the partition is equitable. If k0>δ−1k, then k0 S i=1 X0 i =mk0>mδ−1k=|V|, which is impossible, hence k0≤δ−1k. Finally, at most m elements from each Xiwith 1 ≤i≤kgo to X0 0, so |X0 0|≤|X0|+km =|X0|+δ|V|.ut We are now ready to prove the regularity lemma, using the previous three lemmas: Proof of Lemma 2.4. Without loss of generality, assume that e≤1 2(indeed, if e>1 2, then any 1 2-regular partition is also e-regular, so finding a 1 2-regular partition is enough). Take a partition P0into exactly mparts, with empty exceptional set, that refines P. Let δ=4e−5. Now do the following: •If Pihas kinon-exceptional sets, then construct an equitable partition Qiwith at most (δ+ 1)e−1kinon-exceptional parts in which the exceptional set increases by at most (δ+1)−1e|V|. The existence of such a partition is guaranteed by Lemma 2.10, by setting δ0= (δ+1)−1e. •If Qiis equitable, has k0 inon-exceptional sets and its exceptional set has size at most e|V|, but it is not e-regular, then construct Pi+1such that it has at most k0 i4k0 inon-exceptional parts, its exceptional set is the same as in Qi, refines Qiand q(Pi+1)≥q(Qi) + δ−1. The existence of such a partition is guaranteed by Lemma 2.9. We claim that the procedure produces a partition Qithat is e-regular for some 0 ≤i≤ bδc. Assume the opposite, and we will reach a contradiction. First we will show that, if Qiis not eregular for any of those values of i, then Qiexists for 1 ≤i≤ bδc+1. If Qiexists but Qi+1does not, it is because Qiis not equitable, or its exceptional set is bigger than e|V|. But Qiis equitable by construction, so the first option is impossible. The exceptional set of Qiis the exceptional set of Piwith the addition of at most (δ+1)−1e|V| vertices, and the exceptional set of Piis the same as the one of Qi−1. Since P0has an empty exceptional set, then Qihas an exceptional set of size at most (i+1)(δ+1)−1e|V|, which for i≤δis less than or equal to e|V|. This implies that Qiexists for 0 ≤i≤ bδc+1. By Lemma 2.7, q(Qi)≥q(Pi)≥q(Qi−1) + δ−1. Remember that q(Q)is bounded between 0 and 1. Since q(Q0)≥0, by induction we obtain q(Qi)≥iδ−1. But this means that qQbδc+1≥ (bδc+1)δ−1>1. This is a contradiction, so the partition Qiis e-regular for some 0 ≤i≤ bδc.
11 Qirefines Pi, which in turn refines Qi−1. Since P0refines P, then the e-regular partition constructed refines P. Let f(x) = (δ+1)e−1xand g(x) = x4x. Then the partition Qihas at most M=f(g(f(g(f(. . . f(m). . . ))))) non-exceptional parts, where fappears bδc+1 times, and gappears bδctimes. Monly depends on eand m, so this value satisfies the conditions of the statement of lemma 2.4, and we are done. ut Observation: Ideally, once we fix mwe would want Mto grow as slowly as possible as etends to 0, but as we can see, this is not the case. The relation between Mand eis tower-like, that is, M(e) = 44··4 , where the tower contains O(e−5)layers. Using Knuth’s arrow notation, this would be written as M(e) = 4↑↑ O(e−5). This dependence is worse than what would be useful in most practical applications, so eis usually treated as constant for this theorem. Conlon and Fox [ConFox2] showed, by finding a graph that whose smallest regular partition has that size, that it is impossible to obtain a lower bound less than tower type, in which the number of layers is at least Ω(e−1). 2.2. The counting lemma The second part of the proof of the removal lemma consists of the proof of the counting lemma [AloFisKriSze]. The purpose of this lemma is to estimate the number of copies of a graph Hin a graph G, which consists of several sets of vertices connected by fairly dense e-regular bipartite graphs. The theorem says that, if each of the vertex sets of Gcontains mvertices, then the number of embedded copies of Hin Ggrows like mV(H). We will first start with some notation: Definition 2.11. Let Rbe a graph and tbe a positive integer. We denote by R(t)the graph formed by replacing each vertex of Rwith an independent set of size t, and each edge with a complete bipartite graph Kt,t. Definition 2.12. Let Hand Gbe two graphs. Denote by ||H→G|| the number of embeddings3 of Hin G. The proof will use this lemma: Lemma 2.13. Let G be a bipartite e-regular graph on vertex sets X and Y. Let d ≤d(X,Y). Let Y0⊂Y with |Y0|>e|Y|. If d >e, then there are at most e|X|vertices x ∈X such that |N(x)∩Y0|< (d−e)|Y0|. Proof. Let X0be the set of vertices in Xsatisfying |N(x)∩Y0|<(d−e)|Y0|. Each vertex of X0has less than (d−e)|Y0|neighbours in Y0, which means that e(X0,Y0)<(d−e)|X0||Y0|and 3A morphism from Hto Gis an application f:V(H)→V(G)in which f(vi)f(vj)∈E(G)for all vivj∈V(H). An embedding is an injective morphism.
12 Removal lemmas in sparse graphs d(X0,Y0)<d−e. If |X0| ≥ e|X|, then by definition of regularity e<|d(X0,Y0)−d|≤|d(X0,Y0)− d(X,Y)| ≤ e, contradiction. This means that |X0| ≤ e|X|.ut Now we are ready to state and prove the counting lemma. The proof follows the one found in [KomSim]: Lemma 2.14 (Counting lemma). Let d >e>0be two constants, let R be a graph and m be a positive integer. Let G be a graph produced by replacing each vertex of R with an independent set of size m, and each edge with an e-regular bipartite graph with density at least d. Let H be a subgraph of R(t)with h vertices and maximum degree ∆>0. Let δ=d−eand e0=δ∆ 2+∆. If e≤e0and t −1≤e0m, then ||H→G|| ≥ (e0m)h Observation: If we fix R,H,dand eand let mgrow, the number of vertices of Gis v(R)m, and hence the maximum number of embeddings of Hin Gis (v(R)m)h. This gives us the growth of ||H→G|| up to a constant: ||H→G|| =Θ(mh). Proof. The proof will be constructive. We begin by labelling the vertices of Gas u1,u2, ..., uh. To prove the result, we will embed the vertices uione by one in such a way that in every step there are at least e0mchoices for the embedding of the corresponding vertex, implying that the total number of embeddings is at least (e0m)h. Actually, the bound on the number of choices that we obtain from the calculations is (δ∆−∆e)m−(t−1), so the first step would be to prove that, under the hypothesis of the statement, this number is at least e0m. The following inequality implies this claim: t−1+e0m≤2e0m= (δ∆−∆e0)m≤(δ∆−∆e)m The procedure will go as follows: His a subgraph of R(t), so we denote by v[i]the vertex of R which produces uiin R(t), and by V[i]the set of vertices of Gproduced by v[i]. During our procedure, for 0 ≤j<i, we will call Vi,jthe set of vertices of V[i]that are neighbours of vkfor all k≤jsuch that ukui∈E(H). The first sets are Vi,0 =V[i]. Note that |Vi,0|=m. The procedure goes like this: in the i-th step we choose as uiany vertex from Vi,i−1that has not been chosen before and which is adjacent to at least δ|Vk,i−1|vertices from every Vk,i−1such that uiuk∈E(H)and k>i. We now want to show that the number of choices on each step is at least e0m. Consider vertex ui. The value of |Vi,j| |Vi,j−1|is 1 if vivj/∈E(H)(because the set does not change, so Vi,j=Vi,j−1) and at least δotherwise (by the choice of uj). Since uihas at most ∆neighbours, we obtain |Vi,i−1| ≥ δ∆|Vi,0|=δ∆m. Now let us see how many vertices from Vi,i−1cannot be chosen as ui. From the hypothesis of the statement, δ∆m>e0m≥em, which means that |Vk,i−1|>emfor any k>isuch that uiuk∈E(H). By Lemma 2.13, the number of vertices of Vi,i−1that do not have at least δ|Vk,i−1|neighbours in Vk,i−1is at most em. Since uiis adjacent to at most ∆vertices in H, then the number of discarded
13 vertices for this reason is at most ∆em. In addition, at most t−1 vertices from V[i]have been chosen before, and hence at most t−1 from Vi,i−1. The number of choices for uiis at least |Vi,i−1|−∆em−(t−1)≥(δ∆−em)−(t−1)≥e0m which brings the number of embeddings to at least (e0m)hut 2.3. The removal lemma We now have all the necessary tools to prove the removal lemma. We remember the statement: Theorem 2.1 (Removal lemma). Let e>0 be a constant and Hbe a graph on hvertices. Then there exists δ(e,H)>0 for which the following property holds: any graph Gon nvertices, with at most δnhcopies of H, can be made H-free by removing at most en2edges. A sketch of the proof, as given in [ConFox1], would go as follows: start by using the regularity lemma to find a µ-regular partition of the vertices of G, for an appropriate value of µ. Create a graph G∗by deleting from Gthe edges within pairs, the edges between non-regular pairs of parts and the edges in regular parts with density less than d. Observe that this only leaves edges between different and regular pairs of parts, each of which with density at least d. These are precisely the hypotheses to apply the counting lemma. For adequate values of µand d, the number of removed edges is less than en2. Now, if G∗still has an embedding of H, we can use the counting lemma for mlarge enough (which is equivalent to nlarge enough once µis fixed) to find a constant e0=2Mδsuch that G∗has at least (δn)v(H)copies of H. Tweak the value of δto account for small values of nand the result follows. This is the proof with the details filled in: Proof of theorem 2.1. Assume that e≤1/2, as otherwise the number of edges in Gis less than en2. Also, assume that Hcontains at least one edge, and hence, two vertices. Let µ=(e/4)∆(H) 2+∆(H)<e 4. Then, on account of Lemma 2.4, there exists an integer Msuch that any graph Gon at least 4e−1 vertices admits a µregular partition Pon knon-exceptional parts, with 2e−1≤k≤M. Let m be the size of the non-exceptional parts, which satisfies n 2k≤n−|V0| k≤m≤n k. Construct G∗from Gas follows: •Remove all edges having one or both of its ends in the exceptional set. •Remove all edges with both endpoints in the same set •Remove all edges between irregular pairs •Remove all edges between regular pairs of density less than d=e/2. We count the number of removed edges to see that the total is less than en2: •The number of edges with at least one endpoint in the exceptional set is at most |V0||V| ≤ µn2<en2 4.
14 Removal lemmas in sparse graphs •The edges contained in the exceptional set were removed in the previous step. The number of edges contained inside the rest of the sets is at most k(m 2)≤km2 2≤n2 2k≤en2 4. •There are at most µk2≤ek2 4irregular pairs, each one containing at most m2edges. The total number of edges is therefore at most ek2m2 4≤en2 4 •We only consider pairs of different parts, as the pairs within the same part were already considered in the previous step. There are (k 2)≤k2 2pairs of different parts. A pair with density less than e/2 has at most em2 2edges, so the number of edges that we remove in this step is at most em2k2 4≤en2 4 The number of edges removed in all four steps altogether is at most en2. Now assume that His a subgraph of G∗. Consider the graph R, where the vertices are the nonexceptional pairs of Pand two vertices are connected if they are connected in G∗(in which case they are connected by a µ-regular bipartite graph of density at least d). Note that G∗is constructed from Rfollowing the procedure detailed in Lemma 2.14, and it is a subgraph of R(m). If His a subgraph of G∗, then it is also a subgraph of R(v(H)). We will check that the hypotheses from the removal lemma are satisfied for mlarge enough. d− µ≥e 2−e 4=e 4. If µ0=(d−µ)∆ 2+∆, then µ0≥(e/4)∆(H) 2+∆(H)≥µ(this is the condition e0≥efrom the counting lemma). If m≥v(H)−1 µ0, then the other condition (t−1≤e0m) is also satisfied. In this case, from the removal lemma, ||H→G|| ≥ ||H→G∗|| ≥ (µ0m)v(H)≥µ0n 2Mv(H) To take care of the case m<v(H)−1 µ0, which means n≤2M(v(H)−1) µ0, notice that in this case µ0n 2M(v(H)−1)v(H)<1, so if δ≤µ0n 2M(v(H)−1)v(H), then any graph with ||H→G|| ≤ δnv(H) is H-free, so the removal lemma holds trivially in this case. Also, δ≤µ0 2Mv(H), so it also works for the case of large m. To wrap up the whole proof, δis a parameter that only depends on eand H. If m<2M(v(H)−1) µ0, then δnv(H)<1, so any graph with less than that many copies of His H-free. If m≥2M(v(H)−1) µ0, then we find a µ-regular partition of Gand construct G∗accordingly. G∗consists of removing at most en2edges from G. If G, and therefore G∗, has less than δnv(H)copies of H, then it is H-free. This completes the proof of the removal lemma. ut The removal lemma admits many generalizations and variants. One possibility is the extension to sparse graphs (Lemma 3.34), which will be discussed in the next chapter, and requires a completely different approach. Another possible generalization is a removal lemma in which not any embedding of Hin Gcounts, but only those embeddings satisfying some property. In this case, we can remove a bounded number of edges in such a way that it removes all the embeddings satisfying that property. For example, we can restrict the embedding of each vertex of Hto a certain subset of V(G):
15 Theorem 2.15 (Removal lemma on restricted sets). Let H be a graph on h vertices, and e>0. Let the vertices of H be v1,v2, ..., vh. Then there exists δ>0such that the following property holds: for any graph G on n vertices and any subsets X1,X2, ..., Xh⊆V(G), denote by ||H→G||Xthe number of embeddings of H in G with vi∈Xifor all 1≤i≤h. If ||H→G||X≤δnh, then it is possible to remove at most en2edges from G to make ||H→G||X=0. The proof in this case is not too different to the proof in the previous case, it only requires a modification when taking P: Proof. It is enough to show this result for e<22−h, as making esmaller only makes the statement stronger. Take the coarsest partition P0that refines all Xi(as the sets Xineed not be disjoint). The number of parts of P0is at most 2h<4e−1. This means that we can find the µ-regular partition P∗refining P0. Construct G∗in the same way as in the proof of 2.1. Now observe that if there is still a copy of Hin G∗with its vertices in the corresponding Xi, then all copies generated by the counting lemma are also in the same sets (because Prefines all sets Xi). Hence, the same bound (µ0m)happlies in this case, and also the same δ.ut This theorem will be useful in the proof of the removal lemma for groups, in the next subsection. To illustrate a case in which theorem 2.15 can be applied but theorem 2.1 cannot, consider the following graph, for H=C4. FIG. 2. Example of application of the removal lemma on restricted subsets In the graph from Figure 2, only the cycles containing one vertex on each set are counted in ||H→ G||X. The number of copies of C4grows like Θ(n4), but most of the copies have their vertices in two or three of the sets Xi. However, every cycle with each vertex in one set Ximust include a green edge, and since the number of green edges is o(n2), the number of cycles with vertices on all sets is o(n4). This means that the removal lemma can be applied here (the o(n2)edges that must be removed are the green edges).
16 Removal lemmas in sparse graphs 2.4. Applications We will now show some applications of the removal lemma. The two most important results from this section are Roth’s theorem and the arithmetic removal lemma, but other results are included, either because they are used in the proof of those results or because they provide some insight into the possibilites that the removal lemma opens. We begin with a result that can be obtained from the proof of the removal lemma: Theorem 2.16. Let H be a bipartite graph on h vertices, and e>0. Then there exist N and δsuch that the following holds: If G is a graph on n vertices, n >N, and e(G)≥en2, then ||H→G|| ≥ δnh. Proof. Follow the proof of the remova lemma for e0=e/2. When we construct G∗, we remove at most e 2n2edges, so G∗has at least one edge. The graph His a subgraph of R(h), as this graph contains a copy of Kh,hand H⊂Kh,h. For m>h−1 µ0, we obtain ||H→G|| ≥ ||H→G∗|| ≥ (µ0m)h≥µ0n 2Mh Taking N=2M(h−1) µ0and δ=µ0 2Mhcompletes the proof. ut This result is an improvement over the Erd˝os-Stone thorem in the bipartite case [ErdSto], which asserts that, under the same hypotheses as in this theorem, ||H→G|| >0. On the other hand, Sidorenko’s conjecture claims that such an Nexists for all δ<(2e)e(H), which would be an improvement over this theorem. In a random Erd˝os-Rényi graph Gn,pwith constant probability p=2e, the expected number of edges is en2+o(n2), and the expected number of copies of Hin G is (2e)e(H)nh+o(nh), so Sidorenko’s conjecture says that the lowest possible asymptotic growth of ||H→G|| is precisely the expected value for random graphs. This conjecture has been proven for a wide family of bipartite graphs, including trees, hypercubes, grids, graphs with at most 4 vertices on one side of the partition [ConFoxSud] and graphs in which one vertex is adjacent to all the vertices in the other side of the partition [Sze1]. The next result, by Ruzsa ans Szemerédi [Sol,RuzSze], concerns induced matchings. In a graph G, a set of edges {e1, ..., ek}forms an induced matching if the 2kendpoints of those edges are different, and the induced subgraph of Gon those 2kvertices has only those kedges. Lemma 2.17. For any e>0there is N >0with the following property: if a graph G on n >N vertices is the union of n induced matchings, then e(G)≤en2. Proof. Let v1,v2, ..., vnbe the vertices of G, and let M1,M2, ..., Mnbe the matchings that form G. Suppose that each edge is contained in exactly one matching, otherwise remove it from every matching except one. Construct a graph G0as follows: take three sets of nvertices ai,biand ci. If vivjis an edge in Mk, then join ai,bjand ck. The number of vertices is n0=3n. Now consider the triangles in this graph. There are some triangles of the form aibjck, where vivj∈Mk. In fact, there are exactly 2e(G)such triangles, two for each edge of G. Let us show that the edges of these triangles are disjoint. The edges aibjare all different because the edge vivj
17 is in exactly one Mk. Also, the edges aickare disjoint because, if one such edge appeared in two triangles aibj1ckand aibj2ck, then vivj1and vivj2would both be in Mk, and then Mkwould not be an induced matching. The same holds for the edges bjck. It is also true that those are the only triangles in G0. Indeed, any triangle in G0must contain one vertex from A, another from Band another from C, as otherwise it would be contained in a bipartite graph. If aibjckis a triangle in G0and vivj/∈Mk, then Mkcannot be an induced matching, as Mkwould contain an edge from viand an edge from vjbut not vivj. The conclusion is that the only triangles are the ones described above. There are less than n2=n02/9 triangles. Apply the removal lemma to e0=2e/9 and H=K3. This gives us a δsuch that, if the number of triangles is less than δn03, then they can all be removed by removing e0n02=2en02 9=2en2edges. But since the triangles are edge disjoint, at least an edge must be removed from each triangle. For n>δ−1, we have δn03>δn3>n2>2e(G), so the second condition must also apply, which means 2en2≥e(G)and e(G)<en2.N=δ−1satisfies the condition from the statement. ut From this result, we can prove this other result, due to Ajtai and Szemerédi [AjtSze]. The proof presented here is due to Solymosi [Sol]: Theorem 2.18 (Corners theorem). For any e>0there exists N such that, for any n >N, any subset S∈[n]2of size at least en2includes three elements of the form (a,b),(a+d,b)and (a,b+d)with d6=0. Proof. Suppose that Scontains en2elements from [n]2such that the configuration (a,b),(a+d,b) and (a,b+d)does not appear. We construct a graph Gas follows: the set of vertices will be v1,v2, ..., vn,w1,w2, ..., wn. We join viand wjiff (i,j)∈S. This graph has 2nvertices and |S| edges. Let Mkbe the set of edges viwjsuch that i+j=k, for 1 ≤k≤2n. This includes all edges of the graph. We claim that the sets Mkform an induced matching. Indeed, the endpoints of the edges of Mkare all different. Assume that vawyand vxwbare two different edges from Mkand vawb∈E(G). Then, since a+y=b+x, we also have x−a=y−b. Setting this as d, we see that d6=0 and that (a,b),(a+d,b)and (a,b+d)are elements of S. This contradicts our initial hypothesis, so the sets Mkare induced matchings. From lemma 2.17, there is Nsuch that if 2n>N, then e(G)≤e 8(2n)2=e 2n2. But since e(G) = |S| ≥ en2, the only possibility is 2n≤N.ut The d6=0 from the statement can be replaced with a d>0 using a symmetry argument. The proof goes as follows: consider the pairs of points {(p,q)|p,q∈S}. There are |S|2such pairs. The number of possible midpoints of the segment pq is (2n−1)2, as the coordinates of the midpoint are either an integer or half an integer from the interval [1, n]. By pigeonhole’s principle, there are at least |S|2 (2n−1)2≥e2n4 4n2=e2 4n2pairs of points with the same midpoint m, and every point appears in at most twice. This means that there is a set Sm⊆Swith at least e2 4n2points which is symmetric around m. By the corners theorem, there is an Nsuch that for n>Nthe set Smcontains a set of
24 Removal lemmas in sparse graphs Definition 3.2 ((p,β)-jumbledness). Let Gbe a graph, and let pand βbe positive constants. We say that Gis (p,β)-jumbled if, for any two subsets X0,Y0⊆V(G), we have e(X0,Y0)−p|X0||Y0|≤βq|X0||Y0| If Gis a bipartite graph with stable vertex sets Xand Y, we say that Gis (p,β)-jumbled if the same condition holds for any subsets X0⊆X,Y0⊆Y. For convenience, we say that a graph is (p,γ=x)-jumbled if it is (p,β)-jumbled for β= xp|X||Y|. Let us see the meaning of each parameter. pin this definition is approximately equal to the density of the graph G: the number of edges e(X0,Y0)is roughly the same as p|X0||Y0|, so d(X,Y)≈p. This role is the same as in the random graph Gn,p. The parameter βis a measurement of how jumbled our graph is: a smaller βmeans that the error allowed in the number of edges is smaller, and consequently the edges are more evenly distributed. The parameter γis similar to β, with the difference that, as we will see later, when we state our theorems the parameter γwill not depend on the size of the graph. Every non-empty (p,β)-jumbled graph has β>0. The complete graph on nvertices is (1, 1)- jumbled, because |e(X0,Y0)−|X0||Y0|| =|X0∩Y0| ≤ min{|X0|,|Y0|} ≤ p|X0||Y0|. For any fixed e>0, any family of (p,β)-jumbled graphs with p=d(V,V)≤1−esatisfies β=Ω(√pn). Let us see why. By double counting, pn is the average degree of the vertices of G, so there is a vertex x∈V(G)with |N(x)| ≥ pn. Then, by setting X0={x}and Y0=N(x)we obtain β≥|e(X0,Y0)−p|X0||Y0|| p|X0||Y0|=||N(x)|− p|N(x)|| p|N(x)|= (1−p)q|N(x)| ≥ e√np For a fixed p, the random graph Gn,pis a.a.s. (p,β)-jumbled, with β=O(√pn), which means that it is optimally jumbled. A similar concept is that of uniformity. This definition is similar to the definition of regularity, but in this chapter it will satisfy a very different role. Definition 3.3 ((p,η)-uniformity). We say that a graph Gis (p,η)-uniform if, for any two subsets X0,Y0⊆Vsatisfying |X0|,|Y0| ≥ η|V(G)|, we have |d(X0,Y0)−p| ≤ ηp If Gis a bipartite graph on vertex sets Xand Y, we say that Gis (p,η)-uniform if the same condition holds for any subsets X0⊆X,Y0⊆Ywith |X0| ≥ η|X|and |Y0| ≥ η|Y|. For β=Θ(pn)and η=Θ(1), the (p,β)-jumbledness condition is stronger than (p,η)-uniformity: Lemma 3.4. For every η>0there exists c >0such that the following holds: any (p,cpn)-jumbled graph is (p,η)-uniform. Proof. We consider c=η2. Then, for any X0,Y0⊆V(G)satisfying |X0|,|Y0| ≥ η|V(G)|we have |d(X0,Y0)−p|=|e(X0,Y0)−p|X0||Y0|| |X0||Y0|≤βp|X0||Y0| |X0||Y0|=β p|X0||Y0|≤η2pn ηn=ηp
25 ut The same result holds for bipartite graphs, for β=cpp|X||Y|. Finally, the last kind of pseudorandomness that we will introduce in this section is discrepancy: Definition 3.5 (DISC(q,p,e)). We say that a bipartite graph Gon vertex sets Xand Ysatisfies DISC(q,p,e)if, for any X0⊆Xand Y0⊆Y, we have |e(X0,Y0)−q|X0||Y0|| ≤ ep|X||Y| We say that Gsatisfies DISC≥(q,p,e)if, under the same conditions, e(X0,Y0)−q|X0||Y0|≥−ep|X||Y| The role of discrepancy will be the same as regularity satisfied in the dense case. The proof of the removal lemma will consist on finding a partition in which most pairs of parts satisfy discrepancy, and show a counting lemma for graphs satisfying discrepancy. For the counting lemma, we will only use one-sided discrepancy (DISC≥): we will impose that the graph does not have subsets too sparse, and we will allow subsets too dense. We notice that, from the discrepancy condition, if e1≤e2, then every graph satisfying (q,p,e1)- DISC also satisfies (q,p,e2)-DISC. The same happens with the parameter ein DISC≥, with β and γin jumbledness, and with ηin uniformity. Now we state the version of the removal lemma that we will prove. We consider t3=3, t4=2, t`=1+1 `−3for odd `≥5 and t`=1+1 `−4for even `≥6. Theorem 3.34 (Removal lemma for pseudorandom graphs). For every integer `≥5, and every µ>0 there are δ>0 and c>0 for which the following holds: let X1,X2, ..., X`be vertex sets, each with nvertices. Let Γbe a graph for which (Xi,Xi+1)Γis (p,γ=cpt`)-jumbled for all 1 ≤i≤`, and let Gbe a subgraph of Γ. If ||C`→G||X≤δp`n`, then it is possible to remove at most µpn2 edges from Gso that ||C`→G||X=0. 3.3. The regularity lemma This section will state and prove the sparse version of the regularity lemma. Most of the concepts and proofs are analogous to the ones from Section 2.1. In this proof we will have a graph Gwhich is subgraph of a graph of Γ. For this reason, we will need the notion of density within a graph: Definition 3.6. Let Gand Γbe two graphs such that Gis a subgraph of Γ, and let Xand Ybe two subsets of V(G). Then we define dG,Γ(X,Y) = eG(X,Y) eΓ(X,Y)= eG(X,Y) |X||Y| eΓ(X,Y) |X||Y| =dG(X,Y) dΓ(X,Y) If eΓ(X,Y) = 0 (which implies eG(X,Y) = 0) we define dG,Γ(X,Y) = 0
26 Removal lemmas in sparse graphs With this definition it is easy to see that 0 ≤dG,Γ(X,Y)≤1. In this section, both for convenience and to highlight the difference between the two, we will denote d(X,Y) = dG,Γ(X,Y)and r(X,Y) = dΓ(X,Y). We already introduced the concept of discrepancy in the previous section, so now we introduce e-discrepant partitions: Definition 3.7 (e-DISC partition). Let Gbe a graph, p∈[0, 1]be a parameter and P={V0,V1, ..., Vk} be a partition of V(G), with exceptional set V0. We say that Psatisfies e-DISC if the following holds: • |V1|=|V2|=... =|Vk| • |V0| ≤ ev(G) •All but at most ek2pairs of parts (Vi,Vj)with 1 ≤i,j≤ksatisfy DISC(qi,j,p,e)for some qi,j. We can see that now the condition that (Vi,Vj)needs to satisfy has a difference with respect to the one in regularity pairs: it depends on a parameter qi,j. However, this parameter will generally be very close to dG(Vi,Vj), which makes it somewhat similar to the regular case. Moreover, a simple calculation shows that any DISC(qi,j,p,e)pair is also (dG(Vi,Vj),p, 2e)-DISC. In this version of the regularity lemma, Γwill be a jumbled (or uniform) graph, while Gwill be a graph in which we will want to find a partition satisfying the discrepancy condition. This is the reason why, when we defined DISC, we included three parameters (q,p,e):qwill measure the density of G, while pwill measure the density of Γ.e, as in the case of regularity, will be the parameter that measures how low the discrepancy is. Now we state our sparse version of the regularity lemma: Lemma 3.8. For every e>0and every positive integer m there exist a constant c >0and a positive integer M such that, if G is a graph with at least m vertices which is a subgraph of graph Γ, if Γis a (p,c)- uniform graph, then G admits an e-DISC partition, with the same value of p, into k non-exceptional parts, with m ≤k≤M. Moreover, if Pis a fixed partition of V(G)with at most m parts, then such an e-DISC partition can be found in a way that each set Xiwith 1≤i≤k is contained in one of the sets of P. Comparing this result to Lemma 2.4, we see that, other than the fact that we now have discrepancy instead of regularity, the biggest difference is that we now impose that the graph Gis a subgraph of a graph satisfying a certain condition, which is uniformity. The identity below will have a crucial role in the proof of this version of the regularity lemma: Lemma 3.9. Let Γbe a bipartite graph on stable vertex sets X and Y, let G be a subgraph of Γ, and let X=X1∪X2∪... ∪Xaand Y=Y1∪Y2∪... ∪Ybbe partitions of X and Y. Then (3) a ∑ i=1 b ∑ j=1 eΓ(Xi,Yj)dXi,Yj= a ∑ i=1 b ∑ j=1 eΓ(Xi,Yj)d(X,Y) Recall that d(X,Y) = eG(X,Y) eΓ(X,Y).
27 Proof. The equality comes from the fact that each edge of Gis contained in exactly one graph G|XiYj, so by double counting, a ∑ i=1 b ∑ j=1 eΓ(Xi,Yj)dXi,Yj= a ∑ i=1 b ∑ j=1 eG(Xi,Yj) =eG(X,Y) =eΓ(X,Y)d(X,Y) = a ∑ i=1 b ∑ j=1 eΓ(Xi,Yj)d(X,Y) ut As in the identity (1), the identity (3) comes from double counting, this time of eG(X,Y). The terms eΓ(Xi,Yj)are non-negative, so applying Jensen’s inequality to a convex function f:[0, 1]→R with those terms as weights yields (4) a ∑ i=1 b ∑ j=1 eΓ(Xi,Yj)f(dXi,Yj)≥ a ∑ i=1 b ∑ j=1 eΓ(Xi,Yj)f(d(X,Y)) The analogous definition to quadratic mean density (Definition 2.6) is the following: Definition 3.10. Let Γbe a graph on vertex set V, with |V|=n, and Gbe a subgraph of Γ. Let X,Y⊂V. We define q(X,Y):=eΓ(X,Y) n2d2(X,Y) Let Xand Ybe partitions of sets X,Y. Then q(X,Y):=∑ Xi∈X Yj∈Y q(Xi,Yj) If Pis a partition of Vwithout exceptional set, then q(P):=q(P,P) If P=X0∪X1∪... ∪Xkis a partition of Vwith exceptional set X0, then q(P):=q(˜ P) (Remember the definition of ˜ Pfrom Definition 2.6) This function satisfies that, for any partition Pof V, then 0 ≤q(P)≤eG(V,V) n2, since the partition in which we take each vertex individually refines Pand, as we will see, refining a partition does not decrease q(P)(we do not use the inequality in the proof of the property for refinements in Lemma 3.11, so we do not run into a circular reasoning). If Γis (p,c)-uniform with c<1, then q(P)≤eG(V,V) n2≤eΓ(V,V) n2≤2p|V|2 n2=2p.
28 Removal lemmas in sparse graphs The proof of the regularity lemma will be based on that of the sparse case from [Die], using ideas from [Koh]. It will consist of the same three steps as in Section 2.1, namely: •If P0is a refinement of P, then q(P0)≥q(P) •If Pis an equitable partition in kparts with small exceptional set and it is not e-DISC, then there is a refinement in at most k4kparts which does not increase the size of the exceptional set and with q(P0)≥q(P) + e3p 32 . •If Pis a partition in kparts and δ>0, then there is a refinement of Pin at most δ−1kparts which is equitable and which increases the size of the exceptional set by at most δn. Once we have these three steps we can complete the proof in a similar fashion as in the dense case. The only step with substantial differences is the second step. For the first step, a simple calculation is enough: Lemma 3.11. Let X and Y be sets of vertices of G ⊆Γ, and let Aand A0be two partitions of X and Band B0be two partitions of Y such that A0refines Aand B0refines B. Then q(A0,B0)≥q(A,B). (Partitions may have exceptional sets) Proof. By expanding the formulas for q(A,B)and q(A0,B0), we obtain q(A0,B0) = ∑ A0∈˜ A0 ∑ B0∈˜ B0 q(A0,B0) =∑ A∈˜ A ∑ B∈˜ B ∑ A0∈˜ A0 A0⊂A ∑ B0∈˜ B0 B0⊂B q(A0,B0) =∑ A∈˜ A ∑ B∈˜ B ∑ A0∈˜ A0 A0⊂A ∑ B0∈˜ B0 B0⊂B eΓ(A0,B0) n2d2(A0,B0) (4) ≥∑ A∈˜ A ∑ B∈˜ B ∑ A0∈˜ A0 A0⊂A ∑ B0∈˜ B0 B0⊂B eΓ(A0,B0) n2d2(A,B) =∑ A∈˜ A ∑ B∈˜ B eΓ(A,B) n2d2(A,B) =∑ A∈˜ A ∑ B∈˜ B q(A,B) =q(A,B) ut The second step is where we require more work than in the previous case, and where uniformity of graph Γwill come into place: Lemma 3.12. For every 0<e<1 2and integer k, there is c >0such that the following holds: let P={Xi}k i=0be an equitable partition of V(G)with exceptional set X0and k non-exceptional sets. If G is a subset of a (p,c)-uniform graph Γ,Psatisfies |X0|<e|V|and it is not e-DISC, with the same value of p, then there is another partition P0with at most k4knon-exceptional parts, the same exceptional set X0and q(P0)≥q(P) + e3p 32 .
29 Proof. Let S={(i,j)∈[k]2:(Xi,Xj)is not (q,p,e)-DISC for any value of q}. If Pis not e-DISC, then ek2≤ |S| ≤ k2. For every pair (i,j)that is not DISC, by definition of discrepancy, there are sets Xj i⊂Xiand X[i] j⊂Xjsuch that eG(Xj i,X[i] j)−eG(Xi,Xj) |Xi||Xj||Xj i||X[i] j|≥ep|Xi||Xj|(if the DISC condition does not hold for any qi,j, in particular it does not hold for qi,j=eG(Xi,Xj) |Xi||Xj|). Now take P0to be the coarsest partition that refines all the sets Xj iand X[i] j. Within each set Xi there are at most ksets Xj iand ksets X[j] i, which means that the coarsest partition of Xithat refines all those sets has at most 22k=4ksets, so the partition P0requires no more than k4knonexceptional sets. Denote by ˜ P0(X)the partition of X∈˜ Pin ˜ P0, and by Pi(X)the partition of Xi into two sets induced by X⊂Xi. We claim that, if Γis (p,c)-uniform with c≤e 8kthen |Xj i|,|X[i] j| ≥ cn. Indeed, if two sets Yi⊂Xi and Yj⊂Xjsatisfy eG(Yi,Yj)−qi,j|Yi||Yj|≥ep|Xi||Xj|(that is, they are a counterexample to DISC), then either (1) eG(Yi,Yj)≥ep|Xi||Xj|or (2) qi,j|Yi||Yj| ≥ ep|Xi||Xj|. In the second case, qi,j=eG(Xi,Xj) |Xi||Xj|≤eΓ(Xi,Xj) |Xi||Xj| uniform ≤(1+c)p≤2p, which implies |Yi|Y⊆X ≥|Yi||Yj| |Xj| (2) ≥ep|Xi||Xj| qi,j|Xj|≥e|Xi| 2≥en 4k≥cn The same works for Yj. In the first case, assume that Yihas size less than cn, so it is contained in a set Y0 iof size cn ≤ |Y0 i| ≤ 2cn. Then eG(Yi,Yj)≤eΓ(Yi,Yj)≤eΓ(Y0 i,Xj)≤(1+c)p|Y0 i||Xj|<4cnp|Xj| ≤ e 2kpn|Xj| ≤ ep|Xi||Xj| contradiction. Hence, |Yi| ≥ cn. Suppose that Γis p,e 8k-uniform. Assume for a moment the following inequality: (5) d(Xj i,X[i] j)−d(Xi,Xj)≥ep|Xi||Xj| 2eΓ(Xj i,X[i] j) We will prove this inequality later. Then:
30 Removal lemmas in sparse graphs q(P0)−q(P)def. =∑ A0∈˜ P0 ∑ B0∈˜ P0 q(A0,B0)−∑ A∈˜ P ∑ B∈˜ P q(A,B) =∑ A∈˜ P ∑ B∈˜ P q(˜ P0(A),˜ P0(B)) −∑ A∈˜ P ∑ B∈˜ P q(A,B) restriction, 3.12 ≥∑ (i,j)∈Sq(˜ P0(Xi),˜ P0(Xj)) −q(Xi,Xj) 3.12 ≥∑ (i,j)∈SqPi(Xj i),PjX[i] j−q(Xi,Xj) (∗) ≥∑ (i,j)∈S e2p2|Xi|2|Xj|2 4n2eΓ(Xi,Xj) =∑ (i,j)∈S e2p 4 p|Xi||Xj| eΓ(Xi,Xj)|Xi||Xj| n2 Γunif. ≥∑ (i,j)∈Se2p 41 2 1 4k2 ≥(ek2)e2p 41 2 1 4k2 =e3p 32 where inequality (*) is detailed here. For ease of notation, we will denote Xj i=Yiand X[i] j=Yj:
31 qPi(Yi),PjYj−q(Xi,Xj) =∑ A∈Pi(Yi) ∑ B∈Pj(Yj) q(A,B)−q(Xi,Xj) =∑ A∈Pi(Yi) ∑ B∈Pj(Yj) eΓ(A,B) n2d2(A,B)−eΓ(Xi,Xj) n2d2(Xi,Xj) =∑ A∈Pi(Yi) ∑ B∈Pj(Yj) eΓ(A,B) n2d2(A,B)−d2(Xi,Xj) (3.9) =∑ A∈Pi(Yi) ∑ B∈Pj(Yj) eΓ(A,B) n2d2(A,B)−d2(Xi,Xj)−2d(A,B)d(Xi,Xj) + 2d2(Xi,Xj) =∑ A∈Pi(Yi) ∑ B∈Pj(Yj) eΓ(A,B) n2d(A,B)−d(Xi,Xj)2 ≥eΓ(Yi,Yj) n2d(Yi,Yj)−d(Xi,Xj)2 ≥eΓ(Yi,Yj) n2 ep|X||Yi| 2eΓ(Yi,Yj)!2 =e2p2|Xi|2|Xj|2 4n2eΓ(Xi,Xj) Now we want to prove (5). Note that, from the uniformity of Γ, both eΓ(Xi,Xj)and eΓ(Yi,Yj)are nonzero. From the definition of Yiand Yjas sets that violate the (qi,j,p,e)-DISC condition, we have eG(Yi,Yj)−eG(Xi,Xj) |Xi||Xj||Yi||Yj|≥ep|Xi||Xj| eG(Yi,Yj) eΓ(Yi,Yj)−eG(Xi,Xj) eΓ(YiYj)|Yi||Yj| |Xi||Xj|≥ep|Xi||Xj| eΓ(Yi,Yj) eG(Yi,Yj) eΓ(Yi,Yj)−eG(Xi,Xj) eΓ(Xi,Xj) eΓ(Xi,Xj) |Xi||Xj||Yi||Yj| eΓ(YiYj)≥ep|Xi||Xj| eΓ(Yi,Yj) d(Yi,Yj)−d(Xi,Xj)r(Xi,Xj) r(Yi,Yj)≥ep|Xi||Xj| eΓ(Yi,Yj) (6) Now remember that by the (p,c)-uniform condition on Γ, we have that |r(A,B)−p| ≤ cp for |A|,|B| ≥ cn. Since |Xi|,|Xj|,|Yi|,|Yj| ≥ cn, we have that
32 Removal lemmas in sparse graphs |r(Yi,Yj)−r(Xi,Xj)|≤|r(Yi,Yj)−p|+|p−r(Xi,Xj)| ≤ 2cp ≤ep 2≤ep|Xi||Xj| 2|Yi||Yj| From this we can find r(Yi,Yj)−r(Xi,Xj) r(Yi,Yj)≤ep|Xi||Xj| 2|Yi||Yj|r(Yi,Yj) d(Xi,Xj) 1−r(Xi,Xj) r(Yi,Yj)! (d≤1) ≤ep|Xi||Xj| 2eΓ(Yi,Yj) d(Xi,Xj)−d(Xi,Xj)r(Xi,Xj) r(Yi,Yj)≤ep|Xi||Xj| 2eΓ(Yi,Yj) (7) Finally, by the triangle inequality, |d(Yi,Yj)−d(Xi,Xj)| ≥ d(Yi,Yj)−d(Xi,Xj)r(Xi,Xj) r(Yi,Yj)− d(Xi,Xj)−d(Xi,Xj)r(Xi,Xj) r(Yi,Yj) (6),(7) ≥ep|Xi||Xj| eΓ(Yi,Yj)−ep|Xi||Xj| 2eΓ(Yi,Yj) =ep|Xi||Xj| 2eΓ(Yi,Yj) ut Finally, for the last step, we take a look at Lemma 2.10: Lemma 2.10. Let P={Xi}k i=0be a (not necessarily equitable) partition of Vwith exceptional set X0, and let δ>0. Then there exists an equitable partition P0={X0 i}k0 i=0with exceptional set X0 0 which refines P, with k0≤δ−1kand |X0 0|≤|X0|+δ|V|. This lemma only involves sets of vertices, and does not take in consideration the edges in between them (in fact, the lemma does not mention any graph at all). For this reason we can use the same lemma as in the dense case, without taking any special considerations. With all of this we can prove the sparse version of the regularity lemma, using the same reasoning as in the dense case: Proof of lemma 3.8. Let δ=64e−3, and suppose that c<e 8M, where we will define M=M(e,m) later. Start with any partition P0in mparts and without exceptional set. If a partition Pinto at most mparts is given, take P0into exactly mparts such that it refines P. Once we have that, do the following until we can not continue: •Assume that e≤1 2, as otherwise any 1 2-DISC partition is e-DISC (The e-DISC condition is more restrictive for smaller values of e). If Pihas kinon-exceptional sets, then construct
33 an equitable partition Qiwith at most (δ+1)e−1kinon-exceptional parts in which the exceptional set increases by at most (δ+1)−1e|V|vertices. The existence of such a partition is guaranteed by Lemma 2.10, setting δ0= (δ+1)−1e. •If Qiis equitable, has k0 inon-exceptional sets and its exceptional set has size at most e|V|, but it is not e-DISC, then construct Pi+1such that it has at most k0 i4k0 inon-exceptional parts, has the same exceptional set as Qi, refines Qiand q(Pi+1)≥q(Qi) + 2p δ. The existence of such a partition is guaranteed by Lemma 3.12 if k0 i≤M. We claim that the procedure produces a partition Qithat is e-DISC for some 0 ≤i≤ bδc. Assume the opposite, and we will reach a contradiction. First we will show that, if Qiis not e-DISC for any of those values of i, then Qiexists for 1 ≤i≤ bδc+1. If Qiexists but Qi+1does not, it is because Qiis not equitable, or its exceptional set is bigger than e|V|, or its number of parts exceeds M. But Qiis equitable by construction, so the first option is impossible. Let f(x) = (δ+1)e−1x4x. The numbers of parts kiand k0 isatify k0 i≤(δ+1)e−1ki≤(δ+ 1)e−1k0 i−14k‘i−1=f(k0 i−1). Since k0 0≤((δ+1)e−1m), then setting M=f(f(... f((δ+1)e−1m)...)), where fappears bδctimes guarantees that k0 i≤Mfor 0 ≤i≤ bδc. Qiand Pi+1have the same exceptional set. By construction of Qi, if Vi 0is the exceptional set of Qi, then |Vi+1 0|≥|Vi 0|+ (δ+1)−1e|V|. By induction, this means that |Vi 0| ≤ (i+1)(δ+1)−1e|V|. If i≤ bδc, then the size of the exceptional set of Qifor i≤ bδcis at most (bδc+1)(δ+1)−1e|V|< e|V|. This means that Qiexists for 0 ≤i≤ bδc+1. By Lemma 3.11 and Lemma 3.12, q(Qi)≥q(Pi)≥q(Qi−1) + 2p δ. Recall that if c<1, then q(P)is between 0 and 2p. Since q(Q0)≥0 this means by induction that q(Qi)≥2pi δ, and q(Qbδc+1)≥2p(bδc+1) δ>2p, contradiction. Hence Qimust be e-DISC for some 0 ≤i≤ bδc, and the number of parts is at most M. Also, this partition refines P0, so it refines Ptoo. ut Using this lemma and Lemma 3.4, we obtain the following version of the regularity lemma for sparse graphs: Theorem 3.13 (Regularity lemma for jumbled graphs). For every e>0and every positive integer m there exist a constant c(e,m)>0and a positive integer M(e,m)such that, if G is a graph with at least m vertices which is a subgraph of graph Γ, and if Γis a (p,cpn)-jumbled graph, then G admits an e-DISC partition in k non-exceptional parts, with m ≤k≤M. Moreover, if Pis a fixed partition of V(G)with at most m parts, then such an e-DISC partition can be found in a way that each set Xiwith 1≤i≤k is contained in one of the sets of P. Proof. By Lemma 3.8, there are constants Mand δ>0 such that, if Γis δ-uniform, then the result holds (here δis the value of creturned by Lemma 3.8). Also, by Lemma 3.4, there is c>0 such that, if Γis (p,cpn)-jumbled then it is δ-uniform. The corollary follows trivially from these two results. ut The regularity that we required for this result is β=cpn, with phaving exponent 1. We want to prove the removal lemma for an exponent as small as possible. The exponents in the statement of
40 Removal lemmas in sparse graphs For weighted graphs, the entire proof of Lemma 3.19 is still valid. That is to say, the condition R XRY (G(x,y)−p)f(x)g(y)≤γrR X f(x)RY g(y)holds for all fand gif and only if the condition |e(X0,Y0)−p|X0||Y0||≤βp|X0||Y0|holds for any subsets X0and Y0. The same happens for (q,p,e)-DISC graphs. The equivalent weighted condition is Z XZ Y (G(x,y)−p)f(x)g(y)≤ep∀f:X→[0, 1],g:Y→[0, 1] In the case of one-sided discrepancy ((q,p,e)-DISC≥), the formula becomes (12) Z XZ Y (G(x,y)−p)f(x)g(y)≥ −ep∀f:X→[0, 1],g:Y→[0, 1] The proof in both cases is similar to the proof for jumbledness (Lemma 3.19). We are ready to begin with the proof of the counting lemma. We will now state the version that we will prove: Lemma 3.20 (Sparse counting lemma for cycles). Let `≥5be an integer, and let α,θ>0be positive constants. Then there exist c >0and e>0such that the following holds: Let Γbe graph with vertex sets X1,X2, ..., X`such that the bipartite graph (Xi,Xi+1)Γis (p,γ=cpt`)-jumbled for all 1≤i≤`. Let G be a subgraph of Γsuch that (Xi,Xi+1)Gis (qi,p,e)-DISC≥with αp≤qi≤p for all 1≤i≤`. Then (13) Z X1 ···Z X` G(x1,x2)G(x2,x3)···G(x`,x1)≥(1−θ) ` ∏ i=1 qi |{z} =q The proof of this lemma is taken from [ConFoxZha] and will use a key lemma, stated here as Lemma 3.22. For this key lemma we will use the following notation: Definition 3.21. Let Gbe a graph, and let X1,X2, ..., Xkbe subsets of vertices of G. Fix some x1∈X1and xk∈Xk. We denote G(x1,X2, ..., Xk−1,xk) = Z X2 ··· Z Xk−1 G(x1,x2)G(x2,x3)···G(xk−1,xk)dxk−1···dx2 G(x1,X2, ..., Xk−1,Xk) = Z X2 ···Z Xk G(x1,x2)G(x2,x3)···G(xk−1,xk)dxk···dx2 G(X1,X2, ..., Xk−1,Xk) = Z X1 ···Z Xk G(x1,x2)G(x2,x3)···G(xk−1,xk)dxk···dx1 Lemma 3.22 (Key lemma). For any µ>0and m ≥2there are c >0and e>0such that the following holds: let Γbe a weighted graph and G be a weighted subgraph of Γ. Let X0, X1, ..., Xmbe vertex sets, such that, for all 1≤i≤`,(Xi−1,Xi)Γis (p,γ=cp1+1 2m−2)-jumbled and (Xi−1,Xi)Gis
41 (qi,p,e)-DISC≥. Let ˜ G(x0,xm) = G(x0,X1, ..., Xm−1,xm)and G0=min{˜ G, 4pm}. Then G0satisfies (q1q2...qm,pm,µ)-DISC≥ Intuitively, the meaning of this statement is the following: if we have several bipartite graphs forming a path, then we can make an average of them ( ˜ G) and then bound the value of each edge (G0). If in the original Gall the bipartite graphs satisfy DISC≥, and those bipartite graphs are subgraphs of jumbled graphs Γ, then after the average-and-bound process the graph still satisfies DISC≥, for some appropriate parameters. We will use the lemma in the following way: for any 3 ≤a≤`−2, we apply the lemma to construct (X1,Xa)G0and (Xa,X`)G0. Note that 3 ≤`−2 implies `≥5, and for this reason we restrict ourselves to graphs of length at least 5. Then Z X1Z XaZ X` G0(x1,xa)G0(xa,x`)G(x`,x1)≤Z X1Z XaZ X` ˜ G(x1,xa)˜ G(xa,x`)G(x`,x1) =Z X1Z XaZ X` G(x1,X2, ..., Xa−1,xa)G(xa,Xa+1, ..., X`−1,x`)G(x`,x1) =Z X1 ... Z X` G(x1,x2)G(x2,x3)...G(x`,x1) On the other hand, we can use that G0(x1,xa)≤4pa−1and G0(xax`)≤4p`−ato define weights for the discrepancy condition on (X`,X1)Gand obtain Z X1Z XaZ X` G0(x1,xa)G0(xa,x`)(G(x`,x1)−q`) =16p`−1Z Xa Z X1Z X` G0(x1,xa) 4pa−1 | {z } f(x1)∈[0,1] G0(xa,x`) 4p`−a | {z } g(x`)∈[0,1] (G(x`,x1)−q`)dx`dx1 dxa ≥16p`−1(−ep) =−16ep` Combining the two inequalities, then the left hand side of (13) is greater than or equal to the integral of G0(x1,xa)G0(xa,x`)q`minus 16ep`. Notice that 16ep`≤16 e α`q1q2···q`=16 e α`q, and the term 16 e α`goes to 0 as egoes to 0. We can bound the integral of G0(x1,xa)G0(xa,x`)q`in a similar way, using DISC≥twice more. We can define ˜ Γand Γ0for Γin the same way as ˜ Gand G0for G. The proof of this key lemma will consist of three steps: •Show that ˜ Gsatisfies DISC≥(for some parameters). •Show that, if the number of neighbours of every xi∈Xiin Xi+1is roughly the same, then capping off the edges (going from ˜ Gto G0) does not have a big effect on discrepancy. •Show that, under the hypotheses of the key lemma, the graph Ghas a big subgraph which satisfies the similar neighbourhoods condition.
42 Removal lemmas in sparse graphs We begin by showing the first step, which consists of Lemmas 3.23 and 3.24. These two will focus on the process of averaging. The first lemma says that, by taking the average of two bipartite graphs, if each of them satisfies DISC≥, then the average also satisfies DISC≥, and the parameters qand pare the product of the equivalent parameters in each bipartite graph. The proof uses a ‘few bad vertices’ argument: we show that there are few vertices for which a certain value is far from the average, and show that the ones close to the average are enough that G0satisfies DISC≥regardless of the behaviour of those bad vertices. We already used this argument in the proof of Lemma 2.13, and we will use it often in the proof of the key lemma. Lemma 3.23. Let G be a weighted graph on vertex sets X, Y and Z. Let p1,p2,e∈(0, 1]and q1∈ (0, p1], q2∈(0, p2]. If (X,Y)Gsatisfies (q1,p1,e)-DISC≥and (Y,Z)Gsatisfies (q2,p2,e)-DISC≥, then the graph ˜ G(x,z) = G(x,Y,z)satisfies (q1q2,p1p2, 6√e)-DISC≥. Proof. Let f:X→[0, 1]and g:Z→[0, 1]be any two functions. Let Y0= y∈Y:Z X (G(x,y)−q)f(x)≤ −√ep1 Then, applying the DISC≥condition on (X,Y)Gwith weight functions fand 1Y0we obtain −ep1 DISC≥ ≤Z XZ Y (G(x,y)−q1)f(x)1Y0(y) =Z Y Z X (G(x,y)−q1)f(x) 1Y0(y) ≤Z Y−√ep11Y0(y) =−√ep1|Y0| |Y| This means that |Y0| ≤ √e|Y|. Similarly, we define Y00 as Y00 = y∈Y:Z Z (G(y,z)−q2)g(z)≤ −√ep2 which satisfies |Y00| ≤ √e|Y|for the same reason. The conslusion is that |Y\(Y0∪Y00)| ≥ (1− 2√e)|Y|. We apply these to bound the integral:
43 Z XZ Z ˜ G(x,z)f(x)g(z)dzdx =Z XZ ZZ Y G(x,y)G(y,z)f(x)g(z)dydzdx =Z Y Z X G(x,y)f(x)dx Z Z G(y,z)g(z)dz dy G,f,g≥0 ≥Z Y Z X G(x,y)f(x)dx Z Z G(y,z)g(z)dz 1Y0\(Y0∪Y00)(y)dy =|Y\(Y0∪Y00)| |Y|Z Y0\(Y0∪Y00) Z X G(x,y)f(x)dx Z Z G(y,z)g(z)dz dy ≥(1−2√e)Z Y0\(Y0∪Y00) Z X G(x,y)f(x)dx Z Z G(y,z)g(z)dz dy Y0,Y00 ≥(1−2√e) q1Z X f(x)−√ep1 q2Z Z g(z)−√ep2 Expanding and removing some positive terms ≥q1q2Z X f(x)Z Z g(z)−2√eq1q2Z X f(x)Z Z g(z)−2e√ep1p2 −√ep1q2Z Z g(z)−√ep2q1Z X f(x) f,g≤1,q≤p ≥Z XZ Z q1q2f(x)g(z)−6√ep1p2 Rearranging the terms we obtain R XRZ (˜ G(x,z)−q1q2)f(x)g(z)≥ −6√ep1p2ut This result applies for the case m=2. If we apply induction on Lemma 3.23 we can prove that ˜ G satisfies DISC≥for a general m≥2, by merging the graphs two by two: Lemma 3.24. Let G be a weighted graph with vertex subsets X0,X1, ..., Xm, with m ≥2. Let 0< e<1. If (Xi−1,Xi)Gsatisfies (qi,pi,e)-DISC≥for all 1≤i≤m, then the graph ˜ G(x0,xm) = G(x0,X1, ..., Xm−1,xm)satisfies (q1q2···qm,p1p2···pm, 36e1 2m)-DISC≥. Proof. We can define (Xi,Xj)˜ Gfor any i<jas ˜ G(xi,xj) = G(xi,Xi+1, ..., Xj−1,xj)(we are taking the average of the paths from one vertex sets to another). We will show that, if 0 <j−i≤2kfor a non-negative integer k, then (Xi,Xj)˜ Gsatisfies (qi+1···qj,pi+1···pj, 36e2−k). We proceed by induction on k.
44 Removal lemmas in sparse graphs For k=0 we have j−i=1, so by hypothesis, (Xi,Xj)satisfies (qj,pj,e)-DISC≥and hence (qj,pj, 36e)-DISC≥. If k>0 and j−i≤2k−1, then by induction (Xi,Xj)˜ Gsatisfies (qi+1···qj, pi+1···pj, 36e2−(k−1))-DISC≥and therefore (qi+1···qj,pi+1···pj, 36e2−k)-DISC≥(because 36e2−(k−1)≤ 36e2−k). Assume that k>0 and j−i>2k−1. Then by induction (Xi,Xi+2k−1)˜ Gsatisfies (qi+1···qi+2k−1, pi+1···pi+2k−1, 36e2−(k−1))-DISC≥and (Xi+2k−1,Xj)˜ Gsatisfies (qi+2k−1+1···qj,pi+2k−1+1···pj, 36e2−(k−1))-DISC≥. Applying Lemma 3.23 (with e0=36e2−(k−1)) we obtain that (Xi,Xj)˜ Gsatisfies (qi+1···qj,pi+1···pj, 36e2−k). To finalize, there is an integer ksuch that m≤2k<2m. For this value of k,(X0,Xm)˜ G0satisfies (q1q2···qm,p1p2···pm, 36e2−k)-DISC≥, and 36e2−k≤36e1 2m. We conclude that (X0,Xm)˜ G0 satisfies (q1q2···qm,p1p2···pm, 36e1 2m)-DISC≥.ut This completes the first step of the proof, as we have shown that ˜ Gsatisfies DISC≥. The second step is by far the most complex in the proof, and it will consist of Lemmas 3.26, 3.27 and 3.28. It will require the definition of bounded graphs: Definition 3.25. Let Γbe a weighted bipartite graph on vertex sets Xand Y. We say that (X,Y)Γ is (p,ξ,η)-bounded if the following two conditions hold: Γ(x,y)≤ηfor all x∈Xand y∈Y, and |Γ(x,Y)−p| ≤ ξpfor every x∈X. The ηcondition is simple: it is a bound to the weight of the edges. The ξcondition is a bit more subtle, and says that every vertex from xhas roughly the same number of neighbours in Y. Two important things to note in this definition: first, this definition can only be applied to unweighted graphs if η≥1 (which is equivalent to η=1), as the weight of any edge is either 0 or 1. Second, the definition is not symmetric: (X,Y)Γsatisfying boundedness does not imply that (Y,X)Γsatisfies boundedness, because we impose |Γ(x,Y)−p| ≤ ξpfor every x∈Xbut we do not impose that |Γ(X,y)−p| ≤ ξp. For example, in Figure 2, the graph (X,Y)on the left is a good candidate to satisfy boundedness, but the graph (X,Y)on the right is not (because the ξ condition says that every vertex from Xhas roughly the same number of neighbours in Y). FIG. 2. Example of assymetry of boundedness Now we can state the first lemma of step 2:
45 Lemma 3.26. Let X, Y and Z be three vertex sets, and let p1,p2,ξ1,ξ2,ξ3∈(0, 1], and η1,γ2>0. Let Γbe a weighted graph such that (X,Y)Γis (p1,ξ1,η1)-bounded and (Y,Z)Γis (p2,ξ2, 1)-bounded and (p2,γ=γ2)-jumbled. Let η0=max{4γ2 2p−1 2ξ−1 3η1, 4p1p2}and ξ0=ξ1+2ξ2+2ξ3. If ˜ Γ(x,z) = Γ(x,Y,z)and Γ0=min{˜ Γ,η0}, then (X,Z)Γ0is (p1p2,ξ0,η0)-bounded. The statement says that, if (X,Y)Γis bounded and (Y,Z)Γis bounded and jumbled, then (X,Z)Γ0 is also bounded, with certain parameters. The relations between the parameters are quite technical, but the role of each of them can clearly be seen in the statement, except for one: ξ3is a trade-off parameter. This means that, if we want (p,ξ0,η0)-boundedness in Γ0, by increasing ξ3we can increase ξ0and decrease η0, or the opposite by decreasing ξ3. The proof will be very technical, and uses a ‘few bad vertices’ argument. Proof. To see that Γ0is bounded, we must check that Γ0(x,y)≤η0,Γ0(x,Y)≤(1+ξ0)p1p2and Γ0(x,Y)≥(1−ξ0)p1p2. The first one is trivial from the definition of Γ0. From the definition of Γ0we obtain Γ0(x,y)≤˜ Γ(x,y)and Γ0(x,Y)≤˜ Γ(x,Y). Now, we can use the boundedness of (X,Y)Gand (Y,Z)Gto obtain Γ0(x,Z)≤˜ Γ(x,Z) = Γ(x,Y,Z) = Z YZ Z Γ(x,y)Γ(y,z)dzdy bound. YZ ≤Z Y Γ(x,y)(1+ξ2)p2dy bound. XY ≤(1+ξ1)p1(1+ξ2)p2 This implies Γ0(x,Z)≤(1+ξ1+2ξ2)p1p2≤(1+ξ0)p1p2, which is the second condition of boundedness. Finally, we need to prove Γ0(x,Y)≥(1−ξ0)p1p2. Fix some x∈X. We define Z0 x={z∈Z: Γ(x,Y,z)>η0}(this is the same ‘bad vertex’ idea as in other lemmas). Then we have that Γ0(x,Z)≥Z YZ Z Γ(x,y)Γ(y,z)(1−1Z0 x(z)) = Γ(x,Y,Z)−|Z0 x| |Z|Γ(x,Y,Z0 x) Now we use the following chain of inequalities:
46 Removal lemmas in sparse graphs 1 2|Z0 x| |Z| η0 η1 (η0≥4p1p2) ≤η−1 1η0|Z0 x| |Z|−2p1p2|Z0 x| |Z| ≤η−1 1η0|Z0 x| |Z|−(1+ξ1)p1p2|Z0 x| |Z| (def. Z0 x, bound. XY) ≤η−1 1|Z0 x| |Z|Γ(x,Y,Z0 x)−Γ(x,Y)p2|Z0 x| |Z| (9) =Z YZ Z η−1 1Γ(x,y)Γ(y,z)1Z0 x(z)−Z YZ Z η−1 1Γ(x,y)p21Z0 x(z) =Z YZ Z η−1 1Γ(x,y) | {z } f(y)∈[0,1] (Γ(y,z)−p2)1Z0 x(z) | {z } g(z)∈[0,1] (jumb. YZ) ≤γ2sη−1 1Γ(x,Y)|Z0 x| |Z| (bound. XY) ≤γ2s(1+ξ1)p1η−1 1|Z0 X| |Z| From this inequality we find a bound for |Z0 x| |Z|, which is |Z0 x| |Z|≤4γ2 2(1+ξ1)p1η1 η02. Also, from the chain of inequalities we have η−1 1|Z0 x| |Z|Γ(x,Y,Z0 x)−Γ(x,Y)p2|Z0 x| |Z|≤γ2r(1+ξ1)p1η−1 1|Z0 X| |Z|, which can be rearranged as |Z0 x| |Z|Γ(x,Y,Z0 x)≤γ2r(1+ξ1)p1η1|Z0 X| |Z|+p2Γ(x,Y)|Z0 x| |Z|. Plugging one into the other we obtain: |Z0 x| |Z|Γ(x,Y,Z0 x)≤γ2s(1+ξ1)p1η1|Z0 X| |Z|+p2Γ(x,Y)|Z0 x| |Z| ≤2γ2 2(1+ξ1)p1η1 η0+4γ2 2(1+ξ1)2p2 1p2η1 η02 (def. η0) ≤2γ2 2(1+ξ1)p1η1 4γ2 2p−1 2ξ−1 3η1 +4γ2 2(1+ξ1)2p2 1p2η1 (4γ2 2p−1 2ξ−1 3η1)(4p1p2) =1 2(1+ξ1)ξ3p1p2+1 4(1+ξ1)2ξ3p1p2 ≤2ξ3p1p2 Going back to what we wanted to prove, Γ0(x,Z)≥Γ(x,Y,Z)−|Z0 x| |Z|Γ(x,Y,Z0 x)≥(1−ξ1)p1(1−ξ2)p2−2ξ3p1p1≥(1−ξ0)p1p2 This completes the proof of the third condition of boundedness, hence we conclude that (X,Z)Γ0 is (p1p2,ξ0,η0)-bounded. ut
47 Next, we will use Lemma 3.26 as an induction step to extend it to a path formed by mbipartite graphs, the biggest difference now is that there is no trade-off parameter: Lemma 3.27. Let X0,X1, ..., Xmbe vertex sets, with m ≥2. Let c and ξbe such that 0<4c2<ξ<1 4m, and 0<p≤1. Let Γbe a graph such that (Xi−1,Xi)Γis (p,ξ, 1)-bounded and (p,γ=cp1+1 2m−2)- jumbled for all 1≤i≤m. Let ˜ Γ(x0,xm) = Γ(x0,X1, ..., Xm−1,xm)and Γ0=min{˜ Γ, 4pm}. Then Γ0is (pm, 4mξ, 4pm)-bounded. Again, there are three conditions that we need to prove to show boundedness. Like in the proof of Lemma 3.26, one is trivial, one requires few calculations, and the last one is the most complicated one. In this case, we apply Lemma 3.26 to sets of two graphs, applying the average-and-bound procedure to them and using induction to show the boundedness after isteps. Proof. The condition Γ0(x0,xm)≤4pmcomes from the definition of Γ0. To obtain Γ0(x0,Xm)≤ (1+4mξ)pmwe expand and use boundedness on each graph: Γ0(x0,Xm)≤˜ Γ(x0,Xm) = Z X1 ··· Z Xm−1Z Xm Γ(x0,x1)···Γ(xm−2,xm−1)Γ(xm−1,xm) ≤Z X1 ··· Z Xm−1 Γ(x0,x1)···Γ(xm−2,xm−1)(1+ξ)p≤... ≤(1+ξ)mpm and (1+ξ)mpm≤emξpm≤(1+4mξ)pmby the mean value theorem2. All we need to prove is Γ0(x0,Xm)≥(1−4mξ)pm For this proof we will need to define some intermediate graphs. We will construct Γifor 1 ≤ i≤m.Γihas vertex sets X0,Xiand Xi+1, except for Γmwhich will only have X0and Xm.We construct Γ1as (X0,X1)Γ1= (X0,X1)Γand (X1,X2)Γ1= (X1,X2)Γ. For 2 ≤i<m, we define Γi(x0,xi) = min{Γi−1(x0,Xi−1,xi),ηi}and (Xi,Xi+1)Γi= (Xi,Xi+1)Γ. Finally, Γm(x0,xm) = min{Γm−1(x0,Xm−1,xm),ηm}. The value of ηiis ηi=max{(4c2ξ−1)i−1p(i−1)(1+1 m−1), 4pi} First we see that ηm=max{(4c2ξ−1)m−1pm, 4pm}=4pm, since 4c2<ξ, and this means that (4c2ξ−1)m−1pm<pm<4pm. Moreover, we claim that, if ηi=4pi, then ηi+1=4pi+1. Indeed, for i≥2, we have (4c2ξ−1)i−1p(i−1)(1+1 m−1)≥4pi⇔4c2ξ−1p(1+1 m−1)≥4p(1+1 i−1), and the right hand side of this last inequality is decreasing on i, while the left hand side does not depend on i. For i=1, η1=4p⇒max{1, 4p}=4p⇒p≥1 4≥c2ξ−1⇒η2=max{4c2ξ−1p, 4p2}=4p2. As a consequence, there is some tbetween 1 and mfor which ηi= (4c2ξ−1)i−1p(i−1)(1+1 m−1)for i<t and ηi=4pifor i≥t. In addition, η1=max{1, 4p} ≥ 1. We now claim that (X0,Xi)Γiis (pi, 4iξ,ηi)-bounded. We proceed by induction on i. For i= 1, (X0,X1)Γ1= (X0,X1)Γis (p,ξ, 1)-bounded, so it is also (p, 4ξ,η1)-bounded. Now, for the 2For f(x) = exand 0 <x≤1, there is c∈(0, 1)such that ex−1=f(x)−f(0) = x f 0(c) = x f (c), where 1 =f(0)< f(c)<f(1)<4. Hence x<ex−1<4x, or equivalently, 1 +x<ex<1+4x.
48 Removal lemmas in sparse graphs induction step, consider Lemma 3.26 with the following parameters: p1=pi,p2=p,ξ1=4iξ, ξ2=ξ3=ξ,η1=ηiand γ2=cp1+1 2m−2. Then ξ0=ξ1+2ξ2+2ξ3=4(i+1)ξ. We will see that ηi+1=max{4γ2 2p−1 2ξ−1 3η1, 4p1p2}. If i<t, then max{4γ2 2p−1 2ξ−1 3η1, 4p1p2}=max{4c2ξ−1p1+1 m−1ηi, 4pi+1}=max{(4c2ξ−1)ipi(1+1 m−1), 4pi+1}= ηi+1. If i≥tthen max{4γ2 2p−1 2ξ−1 3η1, 4p1p2}=max{4c2ξ−1p1+1 m−1(4pi), 4pi+1}=4pi+1=ηi+1. By Lemma 3.26, if (X0,Xi)Γiis (pi, 4iξ,ηi)-bounded, then (X0,Xi+1)Γi+1is (pi+1, 4(i+1)ξ,ηi+1)- bounded. By induction, (X0,Xm)Γmis (pm, 4mξ, 4pm)-bounded. Finally, we notice that Γi(x0,xi)≤Γ(x0,X1, ..., Xi−1,xi). Indeed, this is trivially true for i=1, and if it holds for some i, then Γi+1(x0,xi+1)def. Γi+1 ≤Γi(x0,Xi,xi+1) = Z Xi Γi(x0,xi)Γi(xi,xi+1) ≤Z Xi Γ(x0,X1, ..., Xi−1,xi)Γ(xi,xi+1) = Γ(x0,X1, ..., Xi,xi+1) We conclude that Γm(x0,xm)≤min{Γ(x0,X1, ..., Xm),ηm=4pm}=Γ0(x0,xm)and Γ0(x0,Xm)≥Γm(x0,Xm)bound. ≥(1−4mξ)pm ut To finish the second step we need to extend this result from Γto G. This is the first time that both Γand Gappear in the same lemma in the proof of the counting lemma. Lemma 3.28 says that if Gis a path of bipartite graphs satisfying DISC≥, and they are subgraphs of bipartite graphs Γ which are jumbled and bounded, then G0(the result of the average-and-bound procedure) is also DISC≥, with some appropriate parameters, which is what the second step claims. The proof is based on the fact that we know that Γ0is bounded (Lemma 3.27) and ˜ Gsatisfies DISC≥(Lemma 3.24), and combining those two results using the inequality ˜ Γ−Γ0≥˜ G−G0. Lemma 3.28. Let 0<4c2<ξand 0<p≤1. Let X0,X1, ..., Xmbe vertex sets, with m ≥2. Let Γbe a graph and G be a subgraph of Γsuch that (Xi−1,Xi)Γis (p,ξ, 1)-bounded and (p,γ= cp1+1 2m−2)-jumbled, and (Xi−1,Xi)Gsatisfies (qi,p,e)-DISC≥, for all 1≤i≤m. Let ˜ G(x0,xm) = G(x0,X1, ..., Xm−1,xm)and G0=min{˜ G, 4pm}. Then G0satisfies (q1q2...qm | {z } =q ,pm, 36e1 2m+8mξ)- DISC≥. Proof. We can suppose that ξ<1 4m, as otherwise 8mξ≥2 and any graph satisfies (q,p, 2)-DISC≥ (since G≥0, the integral R(G−q)uv is bounded by −q, and −q≥ −p). Consider the following inequality: ˜ Γ−Γ0≥˜ G−G0, where ˜ Γand Γ0are defined analogously3as ˜ Γand Γ0, respectively. Both the RHS and the LHS are non-negative. If the RHS is zero, then the 3˜ Γ(x0,xm) = Γ(x0,X1, ..., Xm−1,Xm)and Γ0=min{˜ Γ, 4pm}
49 inequality holds. If the RHS is nonzero, then G0=4pm, which means that Γ0=4pm=G0and the inequality becomes ˜ Γ≥˜ G, which is true. We conclude that ˜ Γ−Γ0≥˜ G−G0holds in all cases. We want to prove that, for any f:X0→[0, 1]and g:Xm→[0, 1], Z X0Z Xm (G0(x0,xm)−q)f(x0)g(xm)≥ −(36e1 2m+8mξ)pm We split the integral into two: Z Z(G0−q)f g =−Z Z(˜ G−G0)f g +Z Z(˜ G−q)f g 3.24 ≥ −Z Z(˜ Γ−Γ0)f g −36e1 2mpm ≥−Z Z(˜ Γ−Γ0)−36e1 2mpm =−Z Z ˜ Γ+Z Z Γ0−36e1 2mpm 3.27 ≥ −(1+ξ)mpm+ (1−4mξ)pm−36e1 2mpm ≥−(36e1 2m+8mξ)pm ut where in the last inequality we used that 1 +x≤ex≤1+4xfor 0 ≤x≤1 to obtain (1+ξ)m≤ eξm≤1+4mξ. This completes the proof of the lemmas forming the second step. For the third step, we need to show that there is a large enough subgraph of Gthat satisfies boundedness. The proof will consist of applying a ‘few bad vertices’ argument on each set. Lemma 3.29. Let 0<δ,˜ γ,ξ,p<1satisfy 2˜ γ2≤δξ2p2. Let Γbe a graph with vertex subsets X0,X1, ..., Xmsuch that (Xi−1,Xi)Γis (p,γ= (1−δ)˜ γ)-jumbled. Then we can find ˜ X0,˜ X1, ... ˜ Xm, with ˜ Xi⊆Xiand |˜ Xi| ≥ (1−δ)|Xi|such that (˜ Xi−1,˜ Xi)Γis (p,ξ, 1)-bounded and (p,γ=˜ γ)-jumbled for all 1≤i≤m. Proof. Any choice of subsets ˜ Xiwith |˜ Xi| ≥ (1−δ)|Xi|will suffice for the jumbledness condition, because for any ˜ X0 i−1⊆˜ Xi−1and ˜ X0 i⊆˜ Xi, using Lemma 3.19, we have eΓ(˜ X0 i−1,˜ X0 i)−p|˜ X0 i−1|| ˜ X0 i|≤(1−δ)˜ γq|Xi−1||Xi|| ˜ X0 i−1|| ˜ X0 i| ≤ ˜ γq|˜ Xi−1|| ˜ Xi|| ˜ X0 i−1|| ˜ X0 i| The choice of subsets is only important for the boundedness condition. We will create the sets ˜ Xi in decreasing order of i, from ˜ Xmto ˜ X0. We begin by making ˜ Xm=Xm. Now suppose that we have created ˜ Xi+1, and that |˜ Xi+1| ≥ (1−δ)|Xi+1|. Let Xi,1 be the set of elements from Xiwith Γ(xi,˜ Xi+1)>(1+ξ)pthis will play the role of the set of bad vertices. Now, using jumbledness with f(xi) = 1Xi,1 and g(xi+1) = 1˜ Xi+1, we obtain |Xi,1| |Xi||˜ Xi+1| |Xi+1|ξp def. Xi,1 ≤Z XiZ Xi+1 (Γ(xi,xi+1)−p)1Xi,1 (xi)1˜ Xi+1(xi+1)jumb. ≤(1−δ)˜ γs|Xi,1| |Xi||˜ Xi+1| |Xi+1|
56 Removal lemmas in sparse graphs FIG. 3. Graphs resulting from the doubling process FIG. 4. Procedure to prove the counting lemma for triangles 3.5. The removal lemma In this section we prove the removal lemma for cycles in sparse pseudorandom graphs. The proof will be analogous to the proof in the dense case, with some extra attention required for the pseudorandomness parameters involved. For this proof, we will use the regularity lemma and the counting lemma. In particular, the versions of those lemmas that we will use will be Lemma 3.8 and Corollary 3.33, respectively. The version of the removal lemma that we prove is: Theorem 3.34 (Removal lemma for pseudorandom graphs). For every integer `≥5, and every µ>0there are δ(`,µ)>0and c(`,µ)>0for which the following holds: let X1,X2, ..., X`be vertex sets, each with n vertices. Let Γbe a graph for which (Xi,Xi+1)Γis (p,γ=cpt`)-jumbled for all 1≤i≤`, and let G be a subgraph of Γ. If ||C`→G||X≤δp`n`, then it is possible to remove at most µpn2edges from G so that ||C`→G||X=0. Remember that ||C`→G||Xdenotes the cycles in which the i-th vertex is in Xifor all 1 ≤i≤`.
57 Lemma 3.8 and Corollary 3.33, as well as this theorem, use the same notation (e,c) for their parameters, but now we want to assign them different values while avoiding confusion. For this purpose, we will use the following functions: •In Lemma 3.8, for every e>0 and every positive integer mthere exist c=f1(e,m)and M=f2(e,m), for which the statement holds. •In Corollary 3.33, for every `≥5 and every α,θ>0 there exist c=f3(`,α,θ)and e= f4(`,α,θ)for which the statement holds Now we can prove the removal lemma for pseudorandom graphs: Proof of Theorem 3.34. Once again, we consider 0 <µ≤1 2, as otherwise it is enough to remove 1 2pn2edges. We consider c1=f3(`,µ 2`,1 2)and e1=f4(`,µ 2`,1 2). We consider e=min{e1,µ 12`2}, c2=f1(e,`)and M=f2(e,`)Finally, let δ=1 2µ 12`M`and c=min{c1,c2 M,√e,` M}. We claim that these values satisfy the statement of the theorem. If (Xi,Xi+1)Γis (p,γ=cpt`)-jumbled, then it is also (p,γ=c2p)-jumbled. By Lemma 3.8, for this value of cthere is an e-regular partition Pinto knon-exceptional parts, `≤k≤M, which refines all sets Xi, by taking P0={X1,X2, ..., X`}as the initial partition. Construct G∗by taking Gand performing the following operations: •Delete all edges having one of its ends in the exceptional set. •Delete all edges between pairs not satisfying discrepancy. •Delete all edges on pairs of parts satisfying (qi,j,p,e)-DISC with qi,j<µ 6`2p(these are the pairs of parts with small density). The number of edges that we remove is at most µpn2. Let us see why: •Let V0be the exceptional set from P. Let V0,i=V0∩Xi. Then |V0,i| ≤ |V0| ≤ e`n=µ 12`n. This implies eG(V0,i,Xi+1)≤eΓ(V0,i,Xi+1)≤p|V0,i||Xi+1|+γnq|V0,i||Xi+1| ≤ pµ 12`n2+cpn√en2≤µ 6`pn2 The same argument shows that eG(V0,i,Xi−1)≤µ 6`pn2. The total number of edges removed in this step is at most eG(V0,V)≤ ` ∑ i=1 eG(V0,i,V) = ` ∑ i=1 (eG(V0,i,Xi−1) + eG(V0,i,Xi+1))≤ ` ∑ i=1 µ 3`pn2=µ 3pn2 •There are at most ek2pairs not satisfying discrepancy. Each of them is between a pair of vertex sets Vi,Vj, with size `n k≥ |Vi| ≥ `n 2k. The number of edges between them is, by the jumbledness of Γ, eG(Vi,Vj)≤eΓ(Vi,Vj)≤p|Vi||Vj|+cpt`nq|Vi||Vj| ≤ pn2 ` k2 +c` k!≤2`2 k2pn2
58 Removal lemmas in sparse graphs The number of edges removed in the second step is at most ∑ (Vi,Vj)irr. eG(Vi,Vj)≤ek22`2 k2pn2≤µ 12`2k22`2 k2pn2<µ 3pn2 •There are at most k2pairs of parts satisfying (qi,j,p,e)-DISC with qi,j≤µ 6`2p. For those pairs, eG(Vi,Vj)≤qi,j|Vi||Vj|+ep|Vi||Vj| ≤ µ 6`2p`n k2 +µ 12`2p`n k2 ≤µpn2 3k2 The total number of edges removed in the third step is at most k2µpn2 3k2≤µ 3pn2. Altogether, the number of edges that are removed in the construction of G∗is at most µpn2. Assume that ||C`→G∗||X6=0. Then each of the vertices of the cycle is contained in a nonexceptional part of P, since in the construction of G∗we removed all edges incident to the exceptional set. Also, the edges of the cycle lie on different vertex sets Xiso, since Prefines all the sets Xi, the vertices of the cycle lie on different parts of P. We call those parts V1,V2, ..., V`, with Vi⊆ Xi. The graph (Vi,Vi+1)Γis (p,γ=cpt`)-jumbled, so it is also (p,γ=c2pt`)-jumbled. The graph (Vi,Vi+1)Gis (qi,p,e)-DISC for some qi≥µ 6`2p, so it is also (qi,p,e1)-DISC≥. By Corollary 3.33, the number of cycles with one vertex in each Viis at least 1 2µ 6`2p|Vi|` ≥1 2µ 6`2p`n 2M` =δp`n`. This shows that, if ||C`→G||X≤δp`n`, then we can remove at most µpn2edges from G(by constructiong G∗) so that ||C`→G∗||X=0, which is what the theorem states. ut 3.6. Application: The sparse arithmetic removal lemma As a conclusion to this thesis, we will prove a sparse version of Theorem 2.23, which can be found in [ConFox1], using the sparse removal lemma that we just proved. Like in the case of the graph removal lemma, when we move to a sparse environment we shall work in subsets of a pseudorandom set. For this reason, we will work with jumbled sets: Definition 3.35 (Jumbled set). Let Gbe a finite group of order n. We say that a set Sis (p,β)- jumbled if, for any X,Y⊆G, we have ||{(x,y)|x∈X,y∈Y,xy ∈S}|− p|X||Y||≤βq|X||Y| This definition looks very similar to that of jumbled bipartite graphs. Indeed, this is what will allow us to go from one removal lemma to the other: Lemma 3.36. Let G be a finite group, let p,β>0and S ⊆G. Let Γbe a bipartite graph defined as follows: it has two vertex sets X and Y, each with n vertices, which are labeled with the elements of G. We join xg1∈X and yg2∈Y if and only if g−1 1g2∈S. Then the graph Γis (p,β)-jumbled if and only if S is (p,β)-jumbled.
59 Proof. Let Aand Bbe subsets of G. We denote by A−1the set of inverses of all the elements from A. Since inversion in a group is a bijection, then |A−1|=|A|. Denote by XA−1the set of vertices from Xwhose labels are in A−1, and by YBthe set of vertices from Ywhose labels are in B. Then e(XA−1,YB) = {(x,y|x∈A−1,y∈B,xy ∈S} Also, since |A|=|A−1|=|XA−1|and |B|=|YB|we have that |{(x,y)|x∈A,y∈B,xy ∈S}|− p|A||B|≤βq|A||B| m e(XA−1,YB)−p|XA−1||YB|≤βq|XA−1||YB| This means that group jumbledness implies graph jumbledness. On the other hand, any subsets of Xand Ycan be written as XA−1and YBfor appropriate Aand B, so the equivalence of both types of jumbledness follows. ut Using this equivalence, we can take the proof of Theorem 2.23 and extend it to the sparse jumbled case. Remember that C(S1,S2, ..., Sk)is the number of solutions of x1x2···xk=1 with xi∈Si: Theorem 3.37 (Arithmetic sparse removal lemma). For any integer k ≥3and any e>0there exist δ(k,e)>0and c(k,e)>0for which the following holds: for any abelian group of order n, and any (p,β=cptkn)-jumbled subset S, if S1, S2, ..., Skare subsets of S for which C(S1,S2, ..., Sk)≤δpknk−1, then there are subsets S0 i⊆Siwith |Si|\|S0 i| ≤ epn and C(S0 1,S0 2, ..., S0 k) = 0. Proof. We construct the graph Kas follows: we consider kvertex sets Xi, each of which containing nvertices, each of which corresponds to an element of G. We denote by vi,gthe vertex from Xi corresponding to g∈G. We join vi,g1and vi+1,g2if and only if g−1 1g2∈Si. We do the same for vk,g1and v1,g2(that is, we treat X1as Xk+1). Let Γbe a graph on the same sets of vertices, where we join vi,g1and vi+1,g2if and only if g−1 1g2∈ S. Since Si⊆Sfor all i, every edge of Kis also an edge of Γ, and Kis a subgraph of Γ. In addition, due to the jumbledness condition on S, the graph (Xi,Xi+1)Γis (p,β)-jumbled. As we showed in the proof of Theorem 2.23, ||Ck→K||X=nC(S1,S2, ..., Sk), since each solution of x1x2···xk=1 generates ndisjoint cycles. Consider the values of δand cthat result from Theorem 3.34 for `=kand µ=e k. For those values, (Xi,Xi+1)Γis (p,β=cptkn)-jumbled and ||Ck→K||X=nC(S1,S2, ..., Sk)≤δpknk. This means that we can apply the sparse removal lemma. Let E0be the set of at most µpn2edges from Ksuch that removing them eliminates all cycles with one vertex in each Xi(the edges deleted in the removal lemma). To produce S0 ifrom Si, we remove an element si∈Siif and only if there are at least n kedges of the form vi,g1and vi+1,g2 with g−1 1g2=si. Since every edge corresponds to exactly one element si, the number of removed elements from all sets is at most |E0| n/k≤µpn2 n/k≤en.
60 Removal lemmas in sparse graphs Assume that C(S0 1,S0 2, ..., S0 k)6=0. Then there is a solution x1x2···xk=1 with xi∈S0 i. This solution generates nvertex-disjoint cycles in K, and in particular edge-disjoint. By construction of E0, each of those cycles contains at least one edge of E0, and that edge is of the form vi,g1vi+1,g2 with g−1 1g2=xifor some 1 ≤i≤k. By pigeonhole principle, the value of iis the same for at least n kof those cycles, which means that there are at least n kdifferent edges in E0of the form vi,g1vi+1,g2with g−1 1g2=xi, and this implies that xi/∈S0 i. This is a contradiction, so we must have C(S0 1,S0 2, ..., S0 k) = 0. ut This result can be used to prove a sparse version of Roth’s theorem, but the proof is not as straightforward as in the dense case because we run into a small problem: it could be that Sis contained in a jumbled set in G, but 2Sis not. Fortunately, there is a workaround: if we consider G=Z/(4n+1)Z, then multiplying by 2 is an automorphism in G, so if a set is jumbled, then after multiplying each element by 2 it is still jumbled. This is because if fis an automorphism, |{(x,y)|x∈X,y∈Y,xy ∈S}| =|{(x,y)|x∈X,y∈Y,f(x)f(y)∈f(S)}| =|{(x,y)|x∈f(X),y∈f(Y),xy ∈f(S)}| This implies that, if Sis contained in a jumbled set, then 2Sis too. 3.7. Concluding remarks We have seen that the regularity lemma opens a path to dealing with problems related to the structure of the graph. Cayley graphs or similar constructions allow us to extend to abelian finite groups this capability to analyze structures, which produces results such as Roth’s theorem and the arithmetic removal lemma. We have also seen that some results that are satisfied for dense graphs can be adapted to sparse graphs using pseudorandomness. This applies to the regularity lemma, the removal lemma and Roth’s theorem, as seen here, but also to Turán’s theorem [ConFox1], Erd˝os-Stone theorem [ConFoxZha] and results from Ramsey theory [ConFoxZha,Koh], among many others. The adapted versions of those theorems that we saw used jumbledness, but this is not the only measure of pseudorandomness that can be used. Regularity and discrepancy, discussed here, and uniformity [Sto] are other commonly used measures of pseudorandomness which can serve the same purpose. Green and Tao [GreTao] used another pseudorandomness measure in which the set of prime numbers is a dense subset of a pseudorandom set in N. This allowed them to extend Szemerédi’s theorem to prime numbers: Theorem 3.38 (Green-Tao). The prime numbers contain an infinite number of non-trivial arithmetic k-term arithmeic progressions, for all positive integers k.
References [AjtSze] Ajtai, M. and Szemerédi, E., Sets of lattice points that form no squares, Studia Scientiarum Mathematicarum Hungarica 9(1974), 9-11. [AloFisKriSze] Alon, N., Fischer, E., Krivelevich, M. and Szegedy, M., Efficient testing of large graphs, Combinatorica 20 (2000), 451-476. [ConFox1] Conlon, D. and Fox, J., Graph removal lemmas, Surveys in Combinatorics (2013), 1-50. [ConFox2] Bounds for graph regularity and removal lemmas, Geometric and Functional Analysis 22 (2012), 1192-1256. [ConFoxSud] Conlon, D., Fox, J. and Sudakov, B., Sidorenko’s conjecture for a class of graphs: an exposition, Geometric and Functional Analysis 20 (2010), 1354-1366. [ConFoxZha] Conlon, D., Fox, J. and Zhao, Y., Extremal results in pseudorandom graphs, Advances in Mathematics 256 (2014), 535-580. [ConGow] Conlon, D. and Gowers, W.T., Combinatorial theorems in sparse random sets. [Die] Diestel, R., "Graph theory", Electronic edition, Springer-Verlag Heidelberg, New York, 2005. [ErdSto] Erd˝os, P. and Stone, A.H., On the structure of linear graphs, Bulletin of the American Mathematical Society 52 (1946), 1087-1091. [ErdTur] Erd˝os, P. and Turán, P., On some sequences of integers, Journal of the London Mathematical society 11 (1936), 261-264 [FraRod] Frankl, P. and Rödl, V., Extremal problems on set systems, Random Structures Algorithms 20 (2002), 131-164. [Fur] Füredi, Z., Extremal hypergraphs and combinatorial geometry, Proceedings of the International Congress of Mathematics 1(1994), 1343-1352. [Gow] Gowers, W.T., Hypergraph regularity and the multidimensional Szemerédi Theorem, Annals of Mathematics 166 (2007), 897-946. [Gre] A Szemeréty-type regularity lemma in abelian groups, with applications, Geometric and Functional Analysis 15 (2005), 340-376. [GreTao] Green, B. and Tao, T., The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics 167 (2008), 481-547. [Koh] Kohayakawa, Y., The Regularity Lemma of Szemerédi for sparse graphs (unpublished manuscript, 1993). [KomSim] Komlós, J. and Simonovits, M., Szemerédi’s Regularity Lemma and its applications in graph theory, Combinatorics, Paul Erd˝os is eighty 2(1993), 295-352. [KraSerVen] Král’, D., Serra, O. and Vena, L., A combinatorial proof of the removal lemma for groups, Journal of Combinatorial Theory, Series A 116 (2009), 971-978. [NagRodSch] Nagle, B., Rödl, V. and Schacht, M., The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms 28 (2006), 113-179. [RodSko] Rödl, V. and Skokan, J., Regularity lemma for uniform hypergraphs, Random Structures Algorithms 25 (2004), 1-42. [Rot] Roth, K.F., On certain sets of integers, Journal of the London Mathematical Society 28 (1953), 104-109 [RuzSze] Ruzsa, I.Z. and Szemerédi, E., Triple systems with no three points carrying three triangles, Colloquia Mathematica Societatis János Bolyai 18 (1978), 939-945. [Sco] Scott, A., Szemerédi’s Regularity lemma for matrices and sparse graphs, Combinatorics, Probability and Computing 20 (2011), 455-466. [Sol] Solymosi, J., Note on a generalization of Roth’s Theorem, Algorithms and Combinatorics 25 (2003), 825-827. [Sze1] Szegedy, B., An information theoretic approach to Sidorenko’s conjecture (2014). [Sze2] Szemerédi, E., Integer sets containing no kelements in arithmetic progression, Acta arithmetica 27 (1975), 299-345. 61
62 Removal lemmas in sparse graphs [Sze3] Szemerédi, E., Regular partitions of graphs, Colloques Internationaux C.N.R.S. 260 (1976), 399-401. [Tao] Tao, T., A variant of the hypergraph removal lemma, Journal of Combinatorial Theory, Series A 113 (2006), 1257-1280.