Ti le: Remo al lemmas in spa se g aphs
Au ho : Ande Lamaison Vida e
Ad iso s: O iol Se a Albo, Lluís Vena C os
Depa men : Applied Ma hema ics IV
Academic yea : 2014/2015
Deg ee in
Ma hema ics
Uni e si a Poli ècnica de Ca alunya
Facul a de Ma emà iques i Es adís ica
Bachelo ’s Deg ee Thesis
Remo al lemmas in spa se g aphs
Ande Lamaison Vida e
Ad iso s: O iol Se a Albo
Lluís Vena C os
Depa amen de Ma emà ica Aplicada IV
This wo k is dedica ed o my amily, o p o iding
me wi h uncondi ional suppo all hese yea s,
and o e e yone who has helped me in he pa h
h ough uni e si y.
Abs ac
Key wo ds: Pseudo andom, egula i y lemma, emo al lemma, spa se g aphs
MSC2010: 05C35, 05C80
The aim o his wo k is o explain and p o e he g aph emo al lemma, in bo h he dense and he spa se cases,
and show how hese can be applied o ini e g oups o ob ain a i hme ic emo al lemmas. The g aph emo al
lemma, in i s mos basic o m, s a es ha o any ixed g aph H, i a g aph Gon n e ices con ains o(n (H))
copies o H, hen all copies can be dele ed om Gby dele ing o(n2)edges. We will show how he concep o
egula i y, and he egula i y and coun ing lemmas, a e c ucial in he p oo o he emo al lemmas. We will
explain he mo i a ion behind he de elopmen o he spa se case, and he ole o pseudo andom g aphs in
spa se e sions o he emo al lemma. Finally, we will see how he emo al lemma, bo h in i s g aph and i s
a i hme ic e sions, can be used o p o e Ro h’s heo em, ha is, he exis ence o non- i ial 3- e m a i hme ic
p og essions in any subse o he na u al numbe s wi h posi i e densi y.
i Remo al lemmas in spa se g aphs
No a ion
[n]{1, 2, ..., n}
E(G)Se o edges o g aph G
V(G)Se o e ices o g aph G
e(G)Numbe o edges o g aph G
(G)Numbe o e ices o g aph G
Con en s
Chap e 1. In oduc ion 1
Chap e 2. Remo al lemma in dense g aphs 3
2.1. The egula i y lemma 4
2.2. The coun ing lemma 11
2.3. The emo al lemma 13
2.4. Applica ions 16
Chap e 3. Spa se pseudo andom g aphs 21
3.1. Mo i a ion 21
3.2. Pseudo andom g aphs 23
3.3. The egula i y lemma 25
3.4. The coun ing lemma 34
3.5. The emo al lemma 56
3.6. Applica ion: The spa se a i hme ic emo al lemma 58
3.7. Concluding ema ks 60
Re e ences 61
i
ii Remo al lemmas in spa se g aphs
Chap e 1
In oduc ion
The o igins o he emo al lemma can be aced back o a conjec u e p oposed by E d˝os and Tu án
in 1936 [E dTu ]. This conjec u e asked whe he any subse o Nin which he sum o he ecip o-
cals o he elemen s is di e gen necessa ily con ains a non- i ial k- e m a i hme ic p og ession
o all posi i e in ege s k. An in e es ing pa icula case o his conjec u e is whe he his holds
o subse s o No posi i e densi y. This is a esul known oday as Szeme édi’s Theo em on
a i hme ic p og essions: o any densi y e>0, subse s o [n]wi h densi y a leas e, o nla ge
enough, always con ain k- e m a i hme ic p og essions.
The i s answe o he dense case came in 1953, when Ro h [Ro ] p o ed he case k=3 using
Fou ie analysis. In he se en ies, Szeme édi p o ed he esul o gene al kusing combina o-
ial me hods [Sze2]. This p oo in oduced a ool ha would be o g ea ele ance in ex emal
combina o ics: egula i y in g aphs, and in pa icula he egula i y lemma.
The concep o egula i y is one o equidis ibu ion o edges. We say ha a g aph is egula when
he densi y o edges be ween any wo la ge enough se s o e ices is app oxima ely he same as
he densi y o he en i e g aph. A pa i ion o he e ex se o he g aph is said o be egula i
almos all o he pai s o pa s a e egula , and he pa s a e o he same size.
F om he many esul s in ol ing egula i y ha ha e been p o en since i was in oduced, he
wo ha we will use a e he egula i y lemma and he coun ing lemma. The egula i y lemma
s a es ha any g aph admi s a egula pa i ion, and he e is an uppe bound on he numbe o
pa s equi ed [Sze3]. Meanwhile, he coun ing lemma gi es a lowe bound on he numbe o
embeddings o a g aph Hin o a egula pa i ion, unde ce ain condi ions [KomSim].
The combina ion o bo h lemmas p oduces he cen al esul o his hesis: he g aph emo al
lemma [RuzSze,Fu ]:
Theo em 2.1 (Remo al lemma). Le e>0 be a cons an and Hbe a g aph on h e ices. Then
he e exis s δ>0 o which he ollowing p ope y holds: any g aph Gon n e ices, which con-
ains a mos δnhcopies o H, can be made H- ee (no con aining any copies o H) by emo ing
a mos en2edges.
This lemma has many applica ions, one o which is ha i allows o a s aigh o wa d p oo o
Ro h’s heo em ( he case k=3 o Szeme édi’s heo em) [Ro ,RuzSze]. In ac , a gene aliza ion o
1
8 Remo al lemmas in spa se g aphs
P oo . By expanding he o mulas o q(A,B)and q(A0,B0), we ob ain
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)
u
Co olla y 2.8. I Pand P0a e wo pa i ions o V such ha P0 e ines P, hen q(P0)≥q(P)
P oo . q(P0) = q(P0,P0)≥q(P,P) = q(P)u
This shows ha , i we ake a sequence o pa i ions, each o which e ines he p e ious ones, hen
q(P)is non-dec easing. The second s ep, which is he key s ep, consis s o showing ha , i a
pa i ion is equi able bu no e- egula , hen we can inc ease q(P)by a cons an depending only
on e.
Lemma 2.9. Le 0<e<1
2and le P={Xi}k
i=0be an equi able pa i ion o V wi h excep ional se
V0and k non-excep ional se s. I |X0|<e|V|and he pa i ion is no e- egula , hen he e is ano he
pa i ion P0, no necessa ily equi able, wi h a mos k4knon-excep ional pa s, he same excep ional se X0
and q(P0)≥q(P) + e5
4.
P oo . Le S={(i,j)∈[k]2:(Xi,Xj)is no e- egula }. I Pis no e- egula , hen ek2≤ |S| ≤ k2.
Fo e e y pai (i,j) ha is no e- egula , by de ini ion o egula i y, he e a e se s Xj
i⊂Xiand
X[i]
j⊂Xjsuch ha |Xj
i| ≥ e|Xi|,|X[i]
j| ≥ e|Xj|and |d(Xj
i,X[i]
j)−d(Xi,Xj)| ≥ e.
Now ake P0 o be he coa ses pa i ion ha e ines all he se s Xj
iand X[i]
j. Wi hin each se Xi
he e a e a mos kse s Xj
iand kse s X[j]
i, which means ha he coa ses pa i ion o Xi ha
e ines all hose se s has a mos 22k=4kse s, so he pa i ion P0 equi es no mo e han k4knon-
excep ional se s. Deno e by ˜
P0(X) he pa i ion o X∈˜
Pin ˜
P0, and by Pi(X) he pa i ion o Xi
in o wo se s 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 aking he i egula pai s:
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
whe e inequali y (*) is de ailed he e:
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
2k2e2u
10 Remo al lemmas in spa se g aphs
This comple es he second s ep. The numbe o pa s could be educed o k2k+1because we can
make Xj
i=X[j]
iwhene e i6=j, bu he e we a e no ying o op imize ou bounds, we jus wan
o show ha hey exis . The hi d s ep conce ns equi able e inemen s o pa i ions.
Lemma 2.10. Le P={Xi}k
i=0be a (no necessa ily equi able) pa i ion o V wi h excep ional se X0,
and le δ>0. Then he e exis s an equi able pa i ion P0={X0
i}k0
i=0wi h excep ional se X0
0which e ines
P, wi h k0≤δ−1k and |X0
0|≤|X0|+δ|V|.
P oo . Le m=δk−1|V|. To cons uc P0, pa i ion each se Xiwi h 1 ≤i≤kin o se s o size m,
and i |Xi|is no di isible by m, add he emaining e ices o he excep ional se X0
0. Once we
ha e done his, e e y non-excep ional se has size m, so he pa i ion is equi able. I k0>δ−1k,
hen
k0
S
i=1
X0
i
=mk0>mδ−1k=|V|, which is impossible, hence k0≤δ−1k. Finally, a mos m
elemen s om each Xiwi h 1 ≤i≤kgo o X0
0, so |X0
0|≤|X0|+km =|X0|+δ|V|.u
We a e now eady o p o e he egula i y lemma, using he p e ious h ee lemmas:
P oo o Lemma 2.4. Wi hou loss o gene ali y, assume ha e≤1
2(indeed, i e>1
2, hen any
1
2- egula pa i ion is also e- egula , so inding a 1
2- egula pa i ion is enough). Take a pa i ion
P0in o exac ly mpa s, wi h emp y excep ional se , ha e ines P. Le δ=4e−5. Now do he
ollowing:
•I Pihas kinon-excep ional se s, hen cons uc an equi able pa i ion Qiwi h a mos (δ+
1)e−1kinon-excep ional pa s in which he excep ional se inc eases by a mos (δ+1)−1e|V|.
The exis ence o such a pa i ion is gua an eed by Lemma 2.10, by se ing δ0= (δ+1)−1e.
•I Qiis equi able, has k0
inon-excep ional se s and i s excep ional se has size a mos e|V|, bu
i is no e- egula , hen cons uc Pi+1such ha i has a mos k0
i4k0
inon-excep ional pa s, i s
excep ional se is he same as in Qi, e ines Qiand q(Pi+1)≥q(Qi) + δ−1. The exis ence o
such a pa i ion is gua an eed by Lemma 2.9.
We claim ha he p ocedu e p oduces a pa i ion Qi ha is e- egula o some 0 ≤i≤ bδc.
Assume he opposi e, and we will each a con adic ion. Fi s we will show ha , i Qiis no e-
egula o any o hose alues o i, hen Qiexis s o 1 ≤i≤ bδc+1. I Qiexis s bu Qi+1does
no , i is because Qiis no equi able, o i s excep ional se is bigge han e|V|. Bu Qiis equi able
by cons uc ion, so he i s op ion is impossible.
The excep ional se o Qiis he excep ional se o Piwi h he addi ion o a mos (δ+1)−1e|V|
e ices, and he excep ional se o Piis he same as he one o Qi−1. Since P0has an emp y
excep ional se , hen Qihas an excep ional se o size a mos (i+1)(δ+1)−1e|V|, which o
i≤δis less han o equal o e|V|. This implies ha Qiexis s o 0 ≤i≤ bδc+1.
By Lemma 2.7, q(Qi)≥q(Pi)≥q(Qi−1) + δ−1. Remembe ha q(Q)is bounded be ween 0 and
1. Since q(Q0)≥0, by induc ion we ob ain q(Qi)≥iδ−1. Bu his means ha qQbδc+1≥
(bδc+1)δ−1>1. This is a con adic ion, so he pa i ion Qiis e- egula o some 0 ≤i≤ bδc.
11
Qi e ines Pi, which in u n e ines Qi−1. Since P0 e ines P, hen he e- egula pa i ion con-
s uc ed e ines P. Le (x) = (δ+1)e−1xand g(x) = x4x. Then he pa i ion Qihas a mos
M= (g( (g( (. . . (m). . . )))))
non-excep ional pa s, whe e appea s bδc+1 imes, and gappea s bδc imes. Monly depends
on eand m, so his alue sa is ies he condi ions o he s a emen o lemma 2.4, and we a e done.
u
Obse a ion: Ideally, once we ix mwe would wan M o g ow as slowly as possible as e ends
o 0, bu as we can see, his is no he case. The ela ion be ween Mand eis owe -like, ha is,
M(e) = 44··4
, whe e he owe con ains O(e−5)laye s. Using Knu h’s a ow no a ion, his would
be w i en as M(e) = 4↑↑ O(e−5). This dependence is wo se han wha would be use ul in
mos p ac ical applica ions, so eis usually ea ed as cons an o his heo em. Conlon and Fox
[ConFox2] showed, by inding a g aph ha whose smalles egula pa i ion has ha size, ha i is
impossible o ob ain a lowe bound less han owe ype, in which he numbe o laye s is a leas
Ω(e−1).
2.2. The coun ing lemma
The second pa o he p oo o he emo al lemma consis s o he p oo o he coun ing lemma
[AloFisK iSze]. The pu pose o his lemma is o es ima e he numbe o copies o a g aph Hin
a g aph G, which consis s o se e al se s o e ices connec ed by ai ly dense e- egula bipa i e
g aphs. The heo em says ha , i each o he e ex se s o Gcon ains m e ices, hen he numbe
o embedded copies o Hin Gg ows like mV(H).
We will i s s a wi h some no a ion:
De ini ion 2.11. Le Rbe a g aph and be a posi i e in ege . We deno e by R( ) he g aph o med
by eplacing each e ex o Rwi h an independen se o size , and each edge wi h a comple e
bipa i e g aph K , .
De ini ion 2.12. Le Hand Gbe wo g aphs. Deno e by ||H→G|| he numbe o embeddings3
o Hin G.
The p oo will use his lemma:
Lemma 2.13. Le G be a bipa i e e- egula g aph on e ex se s X and Y. Le d ≤d(X,Y). Le
Y0⊂Y wi h |Y0|>e|Y|. I d >e, hen he e a e a mos e|X| e ices x ∈X such ha |N(x)∩Y0|<
(d−e)|Y0|.
P oo . Le X0be he se o e ices in Xsa is ying |N(x)∩Y0|<(d−e)|Y0|. Each e ex o
X0has less han (d−e)|Y0|neighbou s in Y0, which means ha e(X0,Y0)<(d−e)|X0||Y0|and
3A mo phism om H o Gis an applica ion :V(H)→V(G)in which ( i) ( j)∈E(G) o all i j∈V(H). An
embedding is an injec i e mo phism.
12 Remo al lemmas in spa se g aphs
d(X0,Y0)<d−e. I |X0| ≥ e|X|, hen by de ini ion o egula i y e<|d(X0,Y0)−d|≤|d(X0,Y0)−
d(X,Y)| ≤ e, con adic ion. This means ha |X0| ≤ e|X|.u
Now we a e eady o s a e and p o e he coun ing lemma. The p oo ollows he one ound in
[KomSim]:
Lemma 2.14 (Coun ing lemma). Le d >e>0be wo cons an s, le R be a g aph and m be a posi i e
in ege . Le G be a g aph p oduced by eplacing each e ex o R wi h an independen se o size m, and
each edge wi h an e- egula bipa i e g aph wi h densi y a leas d. Le H be a subg aph o R( )wi h h
e ices and maximum deg ee ∆>0. Le δ=d−eand e0=δ∆
2+∆. I e≤e0and −1≤e0m, hen
||H→G|| ≥ (e0m)h
Obse a ion: I we ix R,H,dand eand le mg ow, he numbe o e ices o Gis (R)m, and
hence he maximum numbe o embeddings o Hin Gis ( (R)m)h. This gi es us he g ow h o
||H→G|| up o a cons an : ||H→G|| =Θ(mh).
P oo . The p oo will be cons uc i e. We begin by labelling he e ices o Gas u1,u2, ..., uh. To
p o e he esul , we will embed he e ices uione by one in such a way ha in e e y s ep he e
a e a leas e0mchoices o he embedding o he co esponding e ex, implying ha he o al
numbe o embeddings is a leas (e0m)h. Ac ually, he bound on he numbe o choices ha we
ob ain om he calcula ions is (δ∆−∆e)m−( −1), so he i s s ep would be o p o e ha , unde
he hypo hesis o he s a emen , his numbe is a leas e0m. The ollowing inequali y implies his
claim:
−1+e0m≤2e0m= (δ∆−∆e0)m≤(δ∆−∆e)m
The p ocedu e will go as ollows: His a subg aph o R( ), so we deno e by [i] he e ex o R
which p oduces uiin R( ), and by V[i] he se o e ices o Gp oduced by [i].
Du ing ou p ocedu e, o 0 ≤j<i, we will call Vi,j he se o e ices o V[i] ha a e neighbou s
o k o all k≤jsuch ha ukui∈E(H). The i s se s a e Vi,0 =V[i]. No e ha |Vi,0|=m.
The p ocedu e goes like his: in he i- h s ep we choose as uiany e ex om Vi,i−1 ha has no
been chosen be o e and which is adjacen o a leas δ|Vk,i−1| e ices om e e y Vk,i−1such ha
uiuk∈E(H)and k>i.
We now wan o show ha he numbe o choices on each s ep is a leas e0m. Conside e ex
ui. The alue o |Vi,j|
|Vi,j−1|is 1 i i j/∈E(H)(because he se does no change, so Vi,j=Vi,j−1)
and a leas δo he wise (by he choice o uj). Since uihas a mos ∆neighbou s, we ob ain
|Vi,i−1| ≥ δ∆|Vi,0|=δ∆m.
Now le us see how many e ices om Vi,i−1canno be chosen as ui. F om he hypo hesis o he
s a emen , δ∆m>e0m≥em, which means ha |Vk,i−1|>em o any k>isuch ha uiuk∈E(H).
By Lemma 2.13, he numbe o e ices o Vi,i−1 ha do no ha e a leas δ|Vk,i−1|neighbou s in
Vk,i−1is a mos em. Since uiis adjacen o a mos ∆ e ices in H, hen he numbe o disca ded
13
e ices o his eason is a mos ∆em. In addi ion, a mos −1 e ices om V[i]ha e been
chosen be o e, and hence a mos −1 om Vi,i−1. The numbe o choices o uiis a leas
|Vi,i−1|−∆em−( −1)≥(δ∆−em)−( −1)≥e0m
which b ings he numbe o embeddings o a leas (e0m)hu
2.3. The emo al lemma
We now ha e all he necessa y ools o p o e he emo al lemma. We emembe he s a emen :
Theo em 2.1 (Remo al lemma). Le e>0 be a cons an and Hbe a g aph on h e ices. Then
he e exis s δ(e,H)>0 o which he ollowing p ope y holds: any g aph Gon n e ices, wi h
a mos δnhcopies o H, can be made H- ee by emo ing a mos en2edges.
A ske ch o he p oo , as gi en in [ConFox1], would go as ollows: s a by using he egula i y
lemma o ind a µ- egula pa i ion o he e ices o G, o an app op ia e alue o µ. C ea e
a g aph G∗by dele ing om G he edges wi hin pai s, he edges be ween non- egula pai s o
pa s and he edges in egula pa s wi h densi y less han d. Obse e ha his only lea es edges
be ween di e en and egula pai s o pa s, each o which wi h densi y a leas d. These a e p e-
cisely he hypo heses o apply he coun ing lemma. Fo adequa e alues o µand d, he numbe
o emo ed edges is less han en2. Now, i G∗s ill has an embedding o H, we can use he coun -
ing lemma o mla ge enough (which is equi alen o nla ge enough once µis ixed) o ind a
cons an e0=2Mδsuch ha G∗has a leas (δn) (H)copies o H. Tweak he alue o δ o accoun
o small alues o nand he esul ollows.
This is he p oo wi h he de ails illed in:
P oo o heo em 2.1. Assume ha e≤1/2, as o he wise he numbe o edges in Gis less han en2.
Also, assume ha Hcon ains a leas one edge, and hence, wo e ices. Le µ=(e/4)∆(H)
2+∆(H)<e
4.
Then, on accoun o Lemma 2.4, he e exis s an in ege Msuch ha any g aph Gon a leas 4e−1
e ices admi s a µ- egula pa i ion Pon knon-excep ional pa s, wi h 2e−1≤k≤M. Le m
be he size o he non-excep ional pa s, which sa is ies n
2k≤n−|V0|
k≤m≤n
k.
Cons uc G∗ om Gas ollows:
•Remo e all edges ha ing one o bo h o i s ends in he excep ional se .
•Remo e all edges wi h bo h endpoin s in he same se
•Remo e all edges be ween i egula pai s
•Remo e all edges be ween egula pai s o densi y less han d=e/2.
We coun he numbe o emo ed edges o see ha he o al is less han en2:
•The numbe o edges wi h a leas one endpoin in he excep ional se is a mos |V0||V| ≤
µn2<en2
4.
14 Remo al lemmas in spa se g aphs
•The edges con ained in he excep ional se we e emo ed in he p e ious s ep. The numbe
o edges con ained inside he es o he se s is a mos k(m
2)≤km2
2≤n2
2k≤en2
4.
•The e a e a mos µk2≤ek2
4i egula pai s, each one con aining a mos m2edges. The o al
numbe o edges is he e o e a mos ek2m2
4≤en2
4
•We only conside pai s o di e en pa s, as he pai s wi hin he same pa we e al eady
conside ed in he p e ious s ep. The e a e (k
2)≤k2
2pai s o di e en pa s. A pai wi h
densi y less han e/2 has a mos em2
2edges, so he numbe o edges ha we emo e in his
s ep is a mos em2k2
4≤en2
4
The numbe o edges emo ed in all ou s eps al oge he is a mos en2.
Now assume ha His a subg aph o G∗. Conside he g aph R, whe e he e ices a e he non-
excep ional pai s o Pand wo e ices a e connec ed i hey a e connec ed in G∗(in which case
hey a e connec ed by a µ- egula bipa i e g aph o densi y a leas d). No e ha G∗is cons uc ed
om R ollowing he p ocedu e de ailed in Lemma 2.14, and i is a subg aph o R(m). I His a
subg aph o G∗, hen i is also a subg aph o R( (H)).
We will check ha he hypo heses om he emo al lemma a e sa is ied o mla ge enough. d−
µ≥e
2−e
4=e
4. I µ0=(d−µ)∆
2+∆, hen µ0≥(e/4)∆(H)
2+∆(H)≥µ( his is he condi ion e0≥e om he
coun ing lemma). I m≥ (H)−1
µ0, hen he o he condi ion ( −1≤e0m) is also sa is ied. In his
case, om he emo al lemma,
||H→G|| ≥ ||H→G∗|| ≥ (µ0m) (H)≥µ0n
2M (H)
To ake ca e o he case m< (H)−1
µ0, which means n≤2M( (H)−1)
µ0, no ice ha in his case
µ0n
2M( (H)−1) (H)<1, so i δ≤µ0n
2M( (H)−1) (H), hen any g aph wi h ||H→G|| ≤ δn (H)
is H- ee, so he emo al lemma holds i ially in his case. Also, δ≤µ0
2M (H), so i also wo ks
o he case o la ge m.
To w ap up he whole p oo , δis a pa ame e ha only depends on eand H. I m<2M( (H)−1)
µ0,
hen δn (H)<1, so any g aph wi h less han ha many copies o His H- ee. I m≥2M( (H)−1)
µ0,
hen we ind a µ- egula pa i ion o Gand cons uc G∗acco dingly. G∗consis s o emo ing a
mos en2edges om G. I G, and he e o e G∗, has less han δn (H)copies o H, hen i is H- ee.
This comple es he p oo o he emo al lemma. u
The emo al lemma admi s many gene aliza ions and a ian s. One possibili y is he ex ension
o spa se g aphs (Lemma 3.34), which will be discussed in he nex chap e , and equi es a com-
ple ely di e en app oach. Ano he possible gene aliza ion is a emo al lemma in which no any
embedding o Hin Gcoun s, bu only hose embeddings sa is ying some p ope y. In his case,
we can emo e a bounded numbe o edges in such a way ha i emo es all he embeddings sa -
is ying ha p ope y. Fo example, we can es ic he embedding o each e ex o H o a ce ain
subse o V(G):
15
Theo em 2.15 (Remo al lemma on es ic ed se s). Le H be a g aph on h e ices, and e>0. Le
he e ices o H be 1, 2, ..., h. Then he e exis s δ>0such ha he ollowing p ope y holds: o any
g aph G on n e ices and any subse s X1,X2, ..., Xh⊆V(G), deno e by ||H→G||X he numbe o
embeddings o H in G wi h i∈Xi o all 1≤i≤h. I ||H→G||X≤δnh, hen i is possible o emo e
a mos en2edges om G o make ||H→G||X=0.
The p oo in his case is no oo di e en o he p oo in he p e ious case, i only equi es a
modi ica ion when aking P:
P oo . I is enough o show his esul o e<22−h, as making esmalle only makes he s a emen
s onge . Take he coa ses pa i ion P0 ha e ines all Xi(as he se s Xineed no be disjoin ). The
numbe o pa s o P0is a mos 2h<4e−1. This means ha we can ind he µ- egula pa i ion
P∗ e ining P0. Cons uc G∗in he same way as in he p oo o 2.1. Now obse e ha i he e is
s ill a copy o Hin G∗wi h i s e ices in he co esponding Xi, hen all copies gene a ed by he
coun ing lemma a e also in he same se s (because P e ines all se s Xi). Hence, he same bound
(µ0m)happlies in his case, and also he same δ.u
This heo em will be use ul in he p oo o he emo al lemma o g oups, in he nex subsec ion.
To illus a e a case in which heo em 2.15 can be applied bu heo em 2.1 canno , conside he
ollowing g aph, o H=C4.
FIG. 2. Example o applica ion o he emo al lemma on es ic ed subse s
In he g aph om Figu e 2, only he cycles con aining one e ex on each se a e coun ed in ||H→
G||X. The numbe o copies o C4g ows like Θ(n4), bu mos o he copies ha e hei e ices in
wo o h ee o he se s Xi. Howe e , e e y cycle wi h each e ex in one se Ximus include a
g een edge, and since he numbe o g een edges is o(n2), he numbe o cycles wi h e ices on all
se s is o(n4). This means ha he emo al lemma can be applied he e ( he o(n2)edges ha mus
be emo ed a e he g een edges).
16 Remo al lemmas in spa se g aphs
2.4. Applica ions
We will now show some applica ions o he emo al lemma. The wo mos impo an esul s om
his sec ion a e Ro h’s heo em and he a i hme ic emo al lemma, bu o he esul s a e included,
ei he because hey a e used in he p oo o hose esul s o because hey p o ide some insigh in o
he possibili es ha he emo al lemma opens.
We begin wi h a esul ha can be ob ained om he p oo o he emo al lemma:
Theo em 2.16. Le H be a bipa i e g aph on h e ices, and e>0. Then he e exis N and δsuch ha
he ollowing holds: I G is a g aph on n e ices, n >N, and e(G)≥en2, hen ||H→G|| ≥ δnh.
P oo . Follow he p oo o he emo a lemma o e0=e/2. When we cons uc G∗, we emo e a
mos e
2n2edges, so G∗has a leas one edge. The g aph His a subg aph o R(h), as his g aph
con ains a copy o Kh,hand H⊂Kh,h. Fo m>h−1
µ0, we ob ain
||H→G|| ≥ ||H→G∗|| ≥ (µ0m)h≥µ0n
2Mh
Taking N=2M(h−1)
µ0and δ=µ0
2Mhcomple es he p oo . u
This esul is an imp o emen o e he E d˝os-S one ho em in he bipa i e case [E dS o], which
asse s ha , unde he same hypo heses as in his heo em, ||H→G|| >0. On he o he hand,
Sido enko’s conjec u e claims ha such an Nexis s o all δ<(2e)e(H), which would be an
imp o emen o e his heo em. In a andom E d˝os-Rényi g aph Gn,pwi h cons an p obabili y
p=2e, he expec ed numbe o edges is en2+o(n2), and he expec ed numbe o copies o Hin G
is (2e)e(H)nh+o(nh), so Sido enko’s conjec u e says ha he lowes possible asymp o ic g ow h
o ||H→G|| is p ecisely he expec ed alue o andom g aphs. This conjec u e has been p o en
o a wide amily o bipa i e g aphs, including ees, hype cubes, g ids, g aphs wi h a mos 4
e ices on one side o he pa i ion [ConFoxSud] and g aphs in which one e ex is adjacen o all
he e ices in he o he side o he pa i ion [Sze1].
The nex esul , by Ruzsa ans Szeme édi [Sol,RuzSze], conce ns induced ma chings. In a g aph
G, a se o edges {e1, ..., ek} o ms an induced ma ching i he 2kendpoin s o hose edges a e
di e en , and he induced subg aph o Gon hose 2k e ices has only hose kedges.
Lemma 2.17. Fo any e>0 he e is N >0wi h he ollowing p ope y: i a g aph G on n >N e ices
is he union o n induced ma chings, hen e(G)≤en2.
P oo . Le 1, 2, ..., nbe he e ices o G, and le M1,M2, ..., Mnbe he ma chings ha o m
G. Suppose ha each edge is con ained in exac ly one ma ching, o he wise emo e i om e e y
ma ching excep one. Cons uc a g aph G0as ollows: ake h ee se s o n e ices ai,biand ci.
I i jis an edge in Mk, hen join ai,bjand ck. The numbe o e ices is n0=3n.
Now conside he iangles in his g aph. The e a e some iangles o he o m aibjck, whe e
i j∈Mk. In ac , he e a e exac ly 2e(G)such iangles, wo o each edge o G. Le us show
ha he edges o hese iangles a e disjoin . The edges aibja e all di e en because he edge i j
17
is in exac ly one Mk. Also, he edges aicka e disjoin because, i one such edge appea ed in wo
iangles aibj1ckand aibj2ck, hen i j1and i j2would bo h be in Mk, and hen Mkwould no be
an induced ma ching. The same holds o he edges bjck.
I is also ue ha hose a e he only iangles in G0. Indeed, any iangle in G0mus con ain
one e ex om A, ano he om Band ano he om C, as o he wise i would be con ained in
a bipa i e g aph. I aibjckis a iangle in G0and i j/∈Mk, hen Mkcanno be an induced
ma ching, as Mkwould con ain an edge om iand an edge om jbu no i j. The conclusion
is ha he only iangles a e he ones desc ibed abo e. The e a e less han n2=n02/9 iangles.
Apply he emo al lemma o e0=2e/9 and H=K3. This gi es us a δsuch ha , i he numbe o
iangles is less han δn03, hen hey can all be emo ed by emo ing e0n02=2en02
9=2en2edges.
Bu since he iangles a e edge disjoin , a leas an edge mus be emo ed om each iangle. Fo
n>δ−1, we ha e δn03>δn3>n2>2e(G), so he second condi ion mus also apply, which
means 2en2≥e(G)and e(G)<en2.N=δ−1sa is ies he condi ion om he s a emen . u
F om his esul , we can p o e his o he esul , due o Aj ai and Szeme édi [Aj Sze]. The p oo
p esen ed he e is due o Solymosi [Sol]:
Theo em 2.18 (Co ne s heo em). Fo any e>0 he e exis s N such ha , o any n >N, any subse
S∈[n]2o size a leas en2includes h ee elemen s o he o m (a,b),(a+d,b)and (a,b+d)wi h
d6=0.
P oo . Suppose ha Scon ains en2elemen s om [n]2such ha he con igu a ion (a,b),(a+d,b)
and (a,b+d)does no appea . We cons uc a g aph Gas ollows: he se o e ices will be
1, 2, ..., n,w1,w2, ..., wn. We join iand wji (i,j)∈S. This g aph has 2n e ices and |S|
edges.
Le Mkbe he se o edges iwjsuch ha i+j=k, o 1 ≤k≤2n. This includes all edges o
he g aph. We claim ha he se s Mk o m an induced ma ching. Indeed, he endpoin s o he
edges o Mka e all di e en . Assume ha awyand xwba e wo di e en edges om Mkand
awb∈E(G). Then, since a+y=b+x, we also ha e x−a=y−b. Se ing his as d, we see
ha d6=0 and ha (a,b),(a+d,b)and (a,b+d)a e elemen s o S. This con adic s ou ini ial
hypo hesis, so he se s Mka e induced ma chings.
F om lemma 2.17, he e is Nsuch ha i 2n>N, hen e(G)≤e
8(2n)2=e
2n2. Bu since e(G) =
|S| ≥ en2, he only possibili y is 2n≤N.u
The d6=0 om he s a emen can be eplaced wi h a d>0 using a symme y a gumen . The
p oo goes as ollows: conside he pai s o poin s {(p,q)|p,q∈S}. The e a e |S|2such pai s. The
numbe o possible midpoin s o he segmen pq is (2n−1)2, as he coo dina es o he midpoin
a e ei he an in ege o hal an in ege om he in e al [1, n]. By pigeonhole’s p inciple, he e a e
a leas |S|2
(2n−1)2≥e2n4
4n2=e2
4n2pai s o poin s wi h he same midpoin m, and e e y poin appea s
in a mos wice. This means ha he e is a se Sm⊆Swi h a leas e2
4n2poin s which is symme ic
a ound m. By he co ne s heo em, he e is an Nsuch ha o n>N he se Smcon ains a se o
24 Remo al lemmas in spa se g aphs
De ini ion 3.2 ((p,β)-jumbledness). Le Gbe a g aph, and le pand βbe posi i e cons an s. We
say ha Gis (p,β)-jumbled i , o any wo subse s X0,Y0⊆V(G), we ha e
e(X0,Y0)−p|X0||Y0|≤βq|X0||Y0|
I Gis a bipa i e g aph wi h s able e ex se s Xand Y, we say ha Gis (p,β)-jumbled i he
same condi ion holds o any subse s X0⊆X,Y0⊆Y.
Fo con enience, we say ha a g aph is (p,γ=x)-jumbled i i is (p,β)-jumbled o β=
xp|X||Y|.
Le us see he meaning o each pa ame e . pin his de ini ion is app oxima ely equal o he densi y
o he g aph G: he numbe o edges e(X0,Y0)is oughly he same as p|X0||Y0|, so d(X,Y)≈p.
This ole is he same as in he andom g aph Gn,p. The pa ame e βis a measu emen o how
jumbled ou g aph is: a smalle βmeans ha he e o allowed in he numbe o edges is smalle ,
and consequen ly he edges a e mo e e enly dis ibu ed. The pa ame e γis simila o β, wi h he
di e ence ha , as we will see la e , when we s a e ou heo ems he pa ame e γwill no depend
on he size o he g aph.
E e y non-emp y (p,β)-jumbled g aph has β>0. The comple e g aph on n e ices is (1, 1)-
jumbled, because |e(X0,Y0)−|X0||Y0|| =|X0∩Y0| ≤ min{|X0|,|Y0|} ≤ p|X0||Y0|. Fo any ixed
e>0, any amily o (p,β)-jumbled g aphs wi h p=d(V,V)≤1−esa is ies β=Ω(√pn). Le
us see why. By double coun ing, pn is he a e age deg ee o he e ices o G, so he e is a e ex
x∈V(G)wi h |N(x)| ≥ pn. Then, by se ing X0={x}and Y0=N(x)we ob ain
β≥|e(X0,Y0)−p|X0||Y0||
p|X0||Y0|=||N(x)|− p|N(x)||
p|N(x)|= (1−p)q|N(x)| ≥ e√np
Fo a ixed p, he andom g aph Gn,pis a.a.s. (p,β)-jumbled, wi h β=O(√pn), which means
ha i is op imally jumbled.
A simila concep is ha o uni o mi y. This de ini ion is simila o he de ini ion o egula i y, bu
in his chap e i will sa is y a e y di e en ole.
De ini ion 3.3 ((p,η)-uni o mi y). We say ha a g aph Gis (p,η)-uni o m i , o any wo subse s
X0,Y0⊆Vsa is ying |X0|,|Y0| ≥ η|V(G)|, we ha e
|d(X0,Y0)−p| ≤ ηp
I Gis a bipa i e g aph on e ex se s Xand Y, we say ha Gis (p,η)-uni o m i he same
condi ion holds o any subse s X0⊆X,Y0⊆Ywi h |X0| ≥ η|X|and |Y0| ≥ η|Y|.
Fo β=Θ(pn)and η=Θ(1), he (p,β)-jumbledness condi ion is s onge han (p,η)-uni o mi y:
Lemma 3.4. Fo e e y η>0 he e exis s c >0such ha he ollowing holds: any (p,cpn)-jumbled
g aph is (p,η)-uni o m.
P oo . We conside c=η2. Then, o any X0,Y0⊆V(G)sa is ying |X0|,|Y0| ≥ η|V(G)|we ha e
|d(X0,Y0)−p|=|e(X0,Y0)−p|X0||Y0||
|X0||Y0|≤βp|X0||Y0|
|X0||Y0|=β
p|X0||Y0|≤η2pn
ηn=ηp
25
u
The same esul holds o bipa i e g aphs, o β=cpp|X||Y|.
Finally, he las kind o pseudo andomness ha we will in oduce in his sec ion is disc epancy:
De ini ion 3.5 (DISC(q,p,e)). We say ha a bipa i e g aph Gon e ex se s Xand Ysa is ies
DISC(q,p,e)i , o any X0⊆Xand Y0⊆Y, we ha e
|e(X0,Y0)−q|X0||Y0|| ≤ ep|X||Y|
We say ha Gsa is ies DISC≥(q,p,e)i , unde he same condi ions,
e(X0,Y0)−q|X0||Y0|≥−ep|X||Y|
The ole o disc epancy will be he same as egula i y sa is ied in he dense case. The p oo o he
emo al lemma will consis on inding a pa i ion in which mos pai s o pa s sa is y disc epancy,
and show a coun ing lemma o g aphs sa is ying disc epancy. Fo he coun ing lemma, we will
only use one-sided disc epancy (DISC≥): we will impose ha he g aph does no ha e subse s oo
spa se, and we will allow subse s oo dense.
We no ice ha , om he disc epancy condi ion, i e1≤e2, hen e e y g aph sa is ying (q,p,e1)-
DISC also sa is ies (q,p,e2)-DISC. The same happens wi h he pa ame e ein DISC≥, wi h β
and γin jumbledness, and wi h ηin uni o mi y.
Now we s a e he e sion o he emo al lemma ha we will p o e. We conside 3=3, 4=2,
`=1+1
`−3 o odd `≥5 and `=1+1
`−4 o e en `≥6.
Theo em 3.34 (Remo al lemma o pseudo andom g aphs). Fo e e y in ege `≥5, and e e y
µ>0 he e a e δ>0 and c>0 o which he ollowing holds: le X1,X2, ..., X`be e ex se s, each
wi h n e ices. Le Γbe a g aph o which (Xi,Xi+1)Γis (p,γ=cp `)-jumbled o all 1 ≤i≤`,
and le Gbe a subg aph o Γ. I ||C`→G||X≤δp`n`, hen i is possible o emo e a mos µpn2
edges om Gso ha ||C`→G||X=0.
3.3. The egula i y lemma
This sec ion will s a e and p o e he spa se e sion o he egula i y lemma. Mos o he concep s
and p oo s a e analogous o he ones om Sec ion 2.1.
In his p oo we will ha e a g aph Gwhich is subg aph o a g aph o Γ. Fo his eason, we will
need he no ion o densi y wi hin a g aph:
De ini ion 3.6. Le Gand Γbe wo g aphs such ha Gis a subg aph o Γ, and le Xand Ybe
wo subse s o V(G). Then we de ine
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)
I eΓ(X,Y) = 0 (which implies eG(X,Y) = 0) we de ine dG,Γ(X,Y) = 0
26 Remo al lemmas in spa se g aphs
Wi h his de ini ion i is easy o see ha 0 ≤dG,Γ(X,Y)≤1. In his sec ion, bo h o con e-
nience and o highligh he di e ence be ween he wo, we will deno e d(X,Y) = dG,Γ(X,Y)and
(X,Y) = dΓ(X,Y).
We al eady in oduced he concep o disc epancy in he p e ious sec ion, so now we in oduce
e-disc epan pa i ions:
De ini ion 3.7 (e-DISC pa i ion). Le Gbe a g aph, p∈[0, 1]be a pa ame e and P={V0,V1, ..., Vk}
be a pa i ion o V(G), wi h excep ional se V0. We say ha Psa is ies e-DISC i he ollowing
holds:
• |V1|=|V2|=... =|Vk|
• |V0| ≤ e (G)
•All bu a mos ek2pai s o pa s (Vi,Vj)wi h 1 ≤i,j≤ksa is y DISC(qi,j,p,e) o some
qi,j.
We can see ha now he condi ion ha (Vi,Vj)needs o sa is y has a di e ence wi h espec o he
one in egula i y pai s: i depends on a pa ame e qi,j. Howe e , his pa ame e will gene ally be
e y close o dG(Vi,Vj), which makes i somewha simila o he egula case. Mo eo e , a simple
calcula ion shows ha any DISC(qi,j,p,e)pai is also (dG(Vi,Vj),p, 2e)-DISC.
In his e sion o he egula i y lemma, Γwill be a jumbled (o uni o m) g aph, while Gwill be
a g aph in which we will wan o ind a pa i ion sa is ying he disc epancy condi ion. This is he
eason why, when we de ined DISC, we included h ee pa ame e s (q,p,e):qwill measu e he
densi y o G, while pwill measu e he densi y o Γ.e, as in he case o egula i y, will be he
pa ame e ha measu es how low he disc epancy is.
Now we s a e ou spa se e sion o he egula i y lemma:
Lemma 3.8. Fo e e y e>0and e e y posi i e in ege m he e exis a cons an c >0and a posi i e
in ege M such ha , i G is a g aph wi h a leas m e ices which is a subg aph o g aph Γ, i Γis a (p,c)-
uni o m g aph, hen G admi s an e-DISC pa i ion, wi h he same alue o p, in o k non-excep ional pa s,
wi h m ≤k≤M. Mo eo e , i Pis a ixed pa i ion o V(G)wi h a mos m pa s, hen such an e-DISC
pa i ion can be ound in a way ha each se Xiwi h 1≤i≤k is con ained in one o he se s o P.
Compa ing his esul o Lemma 2.4, we see ha , o he han he ac ha we now ha e disc epancy
ins ead o egula i y, he bigges di e ence is ha we now impose ha he g aph Gis a subg aph
o a g aph sa is ying a ce ain condi ion, which is uni o mi y.
The iden i y below will ha e a c ucial ole in he p oo o his e sion o he egula i y lemma:
Lemma 3.9. Le Γbe a bipa i e g aph on s able e ex se s X and Y, le G be a subg aph o Γ, and le
X=X1∪X2∪... ∪Xaand Y=Y1∪Y2∪... ∪Ybbe pa i ions o 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 ha d(X,Y) = eG(X,Y)
eΓ(X,Y).
27
P oo . The equali y comes om he ac ha each edge o Gis con ained in exac ly one g aph
G|XiYj, so by double coun ing,
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)
u
As in he iden i y (1), he iden i y (3) comes om double coun ing, his ime o eG(X,Y). The e ms
eΓ(Xi,Yj)a e non-nega i e, so applying Jensen’s inequali y o a con ex unc ion :[0, 1]→R
wi h hose e ms as weigh s yields
(4)
a
∑
i=1
b
∑
j=1
eΓ(Xi,Yj) (dXi,Yj)≥
a
∑
i=1
b
∑
j=1
eΓ(Xi,Yj) (d(X,Y))
The analogous de ini ion o quad a ic mean densi y (De ini ion 2.6) is he ollowing:
De ini ion 3.10. Le Γbe a g aph on e ex se V, wi h |V|=n, and Gbe a subg aph o Γ. Le
X,Y⊂V. We de ine
q(X,Y):=eΓ(X,Y)
n2d2(X,Y)
Le Xand Ybe pa i ions o se s X,Y. Then
q(X,Y):=∑
Xi∈X
Yj∈Y
q(Xi,Yj)
I Pis a pa i ion o Vwi hou excep ional se , hen
q(P):=q(P,P)
I P=X0∪X1∪... ∪Xkis a pa i ion o Vwi h excep ional se X0, hen
q(P):=q(˜
P)
(Remembe he de ini ion o ˜
P om De ini ion 2.6)
This unc ion sa is ies ha , o any pa i ion Po V, hen 0 ≤q(P)≤eG(V,V)
n2, since he pa i ion
in which we ake each e ex indi idually e ines Pand, as we will see, e ining a pa i ion does
no dec ease q(P)(we do no use he inequali y in he p oo o he p ope y o e inemen s in
Lemma 3.11, so we do no un in o a ci cula easoning). I Γis (p,c)-uni o m wi h c<1, hen
q(P)≤eG(V,V)
n2≤eΓ(V,V)
n2≤2p|V|2
n2=2p.
28 Remo al lemmas in spa se g aphs
The p oo o he egula i y lemma will be based on ha o he spa se case om [Die], using ideas
om [Koh]. I will consis o he same h ee s eps as in Sec ion 2.1, namely:
•I P0is a e inemen o P, hen q(P0)≥q(P)
•I Pis an equi able pa i ion in kpa s wi h small excep ional se and i is no e-DISC, hen
he e is a e inemen in a mos k4kpa s which does no inc ease he size o he excep ional
se and wi h q(P0)≥q(P) + e3p
32 .
•I Pis a pa i ion in kpa s and δ>0, hen he e is a e inemen o Pin a mos δ−1kpa s
which is equi able and which inc eases he size o he excep ional se by a mos δn.
Once we ha e hese h ee s eps we can comple e he p oo in a simila ashion as in he dense case.
The only s ep wi h subs an ial di e ences is he second s ep. Fo he i s s ep, a simple calcula ion
is enough:
Lemma 3.11. Le X and Y be se s o e ices o G ⊆Γ, and le Aand A0be wo pa i ions o X and
Band B0be wo pa i ions o Y such ha A0 e ines Aand B0 e ines B. Then q(A0,B0)≥q(A,B).
(Pa i ions may ha e excep ional se s)
P oo . By expanding he o mulas o q(A,B)and q(A0,B0), we ob ain
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)
u
The second s ep is whe e we equi e mo e wo k han in he p e ious case, and whe e uni o mi y
o g aph Γwill come in o place:
Lemma 3.12. Fo e e y 0<e<1
2and in ege k, he e is c >0such ha he ollowing holds: le
P={Xi}k
i=0be an equi able pa i ion o V(G)wi h excep ional se X0and k non-excep ional se s. I G
is a subse o a (p,c)-uni o m g aph Γ,Psa is ies |X0|<e|V|and i is no e-DISC, wi h he same alue
o p, hen he e is ano he pa i ion P0wi h a mos k4knon-excep ional pa s, he same excep ional se
X0and q(P0)≥q(P) + e3p
32 .
29
P oo . Le S={(i,j)∈[k]2:(Xi,Xj)is no (q,p,e)-DISC o any alue o q}. I Pis no e-DISC,
hen ek2≤ |S| ≤ k2. Fo e e y pai (i,j) ha is no DISC, by de ini ion o disc epancy, he e a e
se s Xj
i⊂Xiand X[i]
j⊂Xjsuch ha eG(Xj
i,X[i]
j)−eG(Xi,Xj)
|Xi||Xj||Xj
i||X[i]
j|≥ep|Xi||Xj|(i he DISC
condi ion does no hold o any qi,j, in pa icula i does no hold o qi,j=eG(Xi,Xj)
|Xi||Xj|).
Now ake P0 o be he coa ses pa i ion ha e ines all he se s Xj
iand X[i]
j. Wi hin each se Xi
he e a e a mos kse s Xj
iand kse s X[j]
i, which means ha he coa ses pa i ion o Xi ha
e ines all hose se s has a mos 22k=4kse s, so he pa i ion P0 equi es no mo e han k4knon-
excep ional se s. Deno e by ˜
P0(X) he pa i ion o X∈˜
Pin ˜
P0, and by Pi(X) he pa i ion o Xi
in o wo se s induced by X⊂Xi.
We claim ha , i Γis (p,c)-uni o m wi h c≤e
8k hen |Xj
i|,|X[i]
j| ≥ cn. Indeed, i wo se s Yi⊂Xi
and Yj⊂Xjsa is y eG(Yi,Yj)−qi,j|Yi||Yj|≥ep|Xi||Xj|( ha is, hey a e a coun e example o
DISC), hen ei he
(1) eG(Yi,Yj)≥ep|Xi||Xj|o
(2) qi,j|Yi||Yj| ≥ ep|Xi||Xj|.
In he second case, qi,j=eG(Xi,Xj)
|Xi||Xj|≤eΓ(Xi,Xj)
|Xi||Xj|
uni o m
≤(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 wo ks o Yj. In he i s case, assume ha Yihas size less han cn, so i is con ained in
a se Y0
io 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|
con adic ion. Hence, |Yi| ≥ cn.
Suppose ha Γis p,e
8k-uni o m. Assume o a momen he ollowing inequali y:
(5) d(Xj
i,X[i]
j)−d(Xi,Xj)≥ep|Xi||Xj|
2eΓ(Xj
i,X[i]
j)
We will p o e his inequali y la e . Then:
30 Remo al lemmas in spa se g aphs
q(P0)−q(P)de .
=∑
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)
es ic ion, 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
Γuni .
≥∑
(i,j)∈Se2p
41
2 1
4k2
≥(ek2)e2p
41
2 1
4k2
=e3p
32
whe e inequali y (*) is de ailed he e. Fo ease o no a ion, we will deno e 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 wan o p o e (5). No e ha , om he uni o mi y o Γ, bo h eΓ(Xi,Xj)and eΓ(Yi,Yj)a e
nonze o. F om he de ini ion o Yiand Yjas se s ha iola e he (qi,j,p,e)-DISC condi ion, we
ha e
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) (Xi,Xj)
(Yi,Yj)≥ep|Xi||Xj|
eΓ(Yi,Yj)
(6)
Now emembe ha by he (p,c)-uni o m condi ion on Γ, we ha e ha | (A,B)−p| ≤ cp o
|A|,|B| ≥ cn. Since |Xi|,|Xj|,|Yi|,|Yj| ≥ cn, we ha e ha
32 Remo al lemmas in spa se g aphs
| (Yi,Yj)− (Xi,Xj)|≤| (Yi,Yj)−p|+|p− (Xi,Xj)| ≤ 2cp ≤ep
2≤ep|Xi||Xj|
2|Yi||Yj|
F om his we can ind
(Yi,Yj)− (Xi,Xj)
(Yi,Yj)≤ep|Xi||Xj|
2|Yi||Yj| (Yi,Yj)
d(Xi,Xj) 1− (Xi,Xj)
(Yi,Yj)!
(d≤1)
≤ep|Xi||Xj|
2eΓ(Yi,Yj)
d(Xi,Xj)−d(Xi,Xj) (Xi,Xj)
(Yi,Yj)≤ep|Xi||Xj|
2eΓ(Yi,Yj)
(7)
Finally, by he iangle inequali y,
|d(Yi,Yj)−d(Xi,Xj)| ≥
d(Yi,Yj)−d(Xi,Xj) (Xi,Xj)
(Yi,Yj)−
d(Xi,Xj)−d(Xi,Xj) (Xi,Xj)
(Yi,Yj)
(6),(7)
≥ep|Xi||Xj|
eΓ(Yi,Yj)−ep|Xi||Xj|
2eΓ(Yi,Yj)
=ep|Xi||Xj|
2eΓ(Yi,Yj)
u
Finally, o he las s ep, we ake a look a Lemma 2.10:
Lemma 2.10. Le P={Xi}k
i=0be a (no necessa ily equi able) pa i ion o Vwi h excep ional se
X0, and le δ>0. Then he e exis s an equi able pa i ion P0={X0
i}k0
i=0wi h excep ional se X0
0
which e ines P, wi h k0≤δ−1kand |X0
0|≤|X0|+δ|V|.
This lemma only in ol es se s o e ices, and does no ake in conside a ion he edges in be ween
hem (in ac , he lemma does no men ion any g aph a all). Fo his eason we can use he same
lemma as in he dense case, wi hou aking any special conside a ions.
Wi h all o his we can p o e he spa se e sion o he egula i y lemma, using he same easoning
as in he dense case:
P oo o lemma 3.8. Le δ=64e−3, and suppose ha c<e
8M, whe e we will de ine M=M(e,m)
la e . S a wi h any pa i ion P0in mpa s and wi hou excep ional se . I a pa i ion Pin o a
mos mpa s is gi en, ake P0in o exac ly mpa s such ha i e ines P. Once we ha e ha , do
he ollowing un il we can no con inue:
•Assume ha e≤1
2, as o he wise any 1
2-DISC pa i ion is e-DISC (The e-DISC condi ion is
mo e es ic i e o smalle alues o e). I Pihas kinon-excep ional se s, hen cons uc
33
an equi able pa i ion Qiwi h a mos (δ+1)e−1kinon-excep ional pa s in which he ex-
cep ional se inc eases by a mos (δ+1)−1e|V| e ices. The exis ence o such a pa i ion is
gua an eed by Lemma 2.10, se ing δ0= (δ+1)−1e.
•I Qiis equi able, has k0
inon-excep ional se s and i s excep ional se has size a mos e|V|,
bu i is no e-DISC, hen cons uc Pi+1such ha i has a mos k0
i4k0
inon-excep ional pa s,
has he same excep ional se as Qi, e ines Qiand q(Pi+1)≥q(Qi) + 2p
δ. The exis ence o
such a pa i ion is gua an eed by Lemma 3.12 i k0
i≤M.
We claim ha he p ocedu e p oduces a pa i ion Qi ha is e-DISC o some 0 ≤i≤ bδc. Assume
he opposi e, and we will each a con adic ion. Fi s we will show ha , i Qiis no e-DISC o
any o hose alues o i, hen Qiexis s o 1 ≤i≤ bδc+1. I Qiexis s bu Qi+1does no , i
is because Qiis no equi able, o i s excep ional se is bigge han e|V|, o i s numbe o pa s
exceeds M. Bu Qiis equi able by cons uc ion, so he i s op ion is impossible.
Le (x) = (δ+1)e−1x4x. The numbe s o pa s kiand k0
isa i y k0
i≤(δ+1)e−1ki≤(δ+
1)e−1k0
i−14k‘i−1= (k0
i−1). Since k0
0≤((δ+1)e−1m), hen se ing M= ( (... ((δ+1)e−1m)...)),
whe e appea s bδc imes gua an ees ha k0
i≤M o 0 ≤i≤ bδc.
Qiand Pi+1ha e he same excep ional se . By cons uc ion o Qi, i Vi
0is he excep ional se o
Qi, hen |Vi+1
0|≥|Vi
0|+ (δ+1)−1e|V|. By induc ion, his means ha |Vi
0| ≤ (i+1)(δ+1)−1e|V|.
I i≤ bδc, hen he size o he excep ional se o Qi o i≤ bδcis a mos (bδc+1)(δ+1)−1e|V|<
e|V|. This means ha Qiexis s o 0 ≤i≤ bδc+1.
By Lemma 3.11 and Lemma 3.12, q(Qi)≥q(Pi)≥q(Qi−1) + 2p
δ. Recall ha i c<1, hen
q(P)is be ween 0 and 2p. Since q(Q0)≥0 his means by induc ion ha q(Qi)≥2pi
δ, and
q(Qbδc+1)≥2p(bδc+1)
δ>2p, con adic ion. Hence Qimus be e-DISC o some 0 ≤i≤ bδc, and
he numbe o pa s is a mos M. Also, his pa i ion e ines P0, so i e ines P oo. u
Using his lemma and Lemma 3.4, we ob ain he ollowing e sion o he egula i y lemma o
spa se g aphs:
Theo em 3.13 (Regula i y lemma o jumbled g aphs). Fo e e y e>0and e e y posi i e in ege
m he e exis a cons an c(e,m)>0and a posi i e in ege M(e,m)such ha , i G is a g aph wi h a leas
m e ices which is a subg aph o g aph Γ, and i Γis a (p,cpn)-jumbled g aph, hen G admi s an e-DISC
pa i ion in k non-excep ional pa s, wi h m ≤k≤M. Mo eo e , i Pis a ixed pa i ion o V(G)wi h
a mos m pa s, hen such an e-DISC pa i ion can be ound in a way ha each se Xiwi h 1≤i≤k is
con ained in one o he se s o P.
P oo . By Lemma 3.8, he e a e cons an s Mand δ>0 such ha , i Γis δ-uni o m, hen he esul
holds (he e δis he alue o c e u ned by Lemma 3.8). Also, by Lemma 3.4, he e is c>0 such
ha , i Γis (p,cpn)-jumbled hen i is δ-uni o m. The co olla y ollows i ially om hese wo
esul s. u
The egula i y ha we equi ed o his esul is β=cpn, wi h pha ing exponen 1. We wan o
p o e he emo al lemma o an exponen as small as possible. The exponen s in he s a emen o
40 Remo al lemmas in spa se g aphs
Fo weigh ed g aphs, he en i e p oo o Lemma 3.19 is s ill alid. Tha is o say, he condi ion
R
XRY
(G(x,y)−p) (x)g(y)≤γ R
X
(x)RY
g(y)holds o all and gi and only i he condi ion
|e(X0,Y0)−p|X0||Y0||≤βp|X0||Y0|holds o any subse s X0and Y0.
The same happens o (q,p,e)-DISC g aphs. The equi alen weigh ed condi ion is
Z
XZ
Y
(G(x,y)−p) (x)g(y)≤ep∀ :X→[0, 1],g:Y→[0, 1]
In he case o one-sided disc epancy ((q,p,e)-DISC≥), he o mula becomes
(12) Z
XZ
Y
(G(x,y)−p) (x)g(y)≥ −ep∀ :X→[0, 1],g:Y→[0, 1]
The p oo in bo h cases is simila o he p oo o jumbledness (Lemma 3.19).
We a e eady o begin wi h he p oo o he coun ing lemma. We will now s a e he e sion ha
we will p o e:
Lemma 3.20 (Spa se coun ing lemma o cycles). Le `≥5be an in ege , and le α,θ>0be posi i e
cons an s. Then he e exis c >0and e>0such ha he ollowing holds: Le Γbe g aph wi h e ex se s
X1,X2, ..., X`such ha he bipa i e g aph (Xi,Xi+1)Γis (p,γ=cp `)-jumbled o all 1≤i≤`. Le G
be a subg aph o Γsuch ha (Xi,Xi+1)Gis (qi,p,e)-DISC≥wi h αp≤qi≤p o 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 p oo o his lemma is aken om [ConFoxZha] and will use a key lemma, s a ed he e as
Lemma 3.22. Fo his key lemma we will use he ollowing no a ion:
De ini ion 3.21. Le Gbe a g aph, and le X1,X2, ..., Xkbe subse s o e ices o G. Fix some
x1∈X1and xk∈Xk. We deno e
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). Fo any µ>0and m ≥2 he e a e c >0and e>0such ha he
ollowing holds: le Γbe a weigh ed g aph and G be a weigh ed subg aph o Γ. Le X0, X1, ..., Xmbe
e ex se s, such ha , o all 1≤i≤`,(Xi−1,Xi)Γis (p,γ=cp1+1
2m−2)-jumbled and (Xi−1,Xi)Gis
41
(qi,p,e)-DISC≥. Le ˜
G(x0,xm) = G(x0,X1, ..., Xm−1,xm)and G0=min{˜
G, 4pm}. Then G0sa is ies
(q1q2...qm,pm,µ)-DISC≥
In ui i ely, he meaning o his s a emen is he ollowing: i we ha e se e al bipa i e g aphs
o ming a pa h, hen we can make an a e age o hem ( ˜
G) and hen bound he alue o each edge
(G0). I in he o iginal Gall he bipa i e g aphs sa is y DISC≥, and hose bipa i e g aphs a e
subg aphs o jumbled g aphs Γ, hen a e he a e age-and-bound p ocess he g aph s ill sa is ies
DISC≥, o some app op ia e pa ame e s.
We will use he lemma in he ollowing way: o any 3 ≤a≤`−2, we apply he lemma o
cons uc (X1,Xa)G0and (Xa,X`)G0. No e ha 3 ≤`−2 implies `≥5, and o his eason we
es ic ou sel es o g aphs o leng h a leas 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 he o he hand, we can use ha G0(x1,xa)≤4pa−1and G0(xax`)≤4p`−a o de ine weigh s
o he disc epancy condi ion on (X`,X1)Gand ob ain
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 }
(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 he wo inequali ies, hen he le hand side o (13) is g ea e han o equal o he
in eg al o G0(x1,xa)G0(xa,x`)q`minus 16ep`. No ice ha 16ep`≤16 e
α`q1q2···q`=16 e
α`q, and
he e m 16 e
α`goes o 0 as egoes o 0. We can bound he in eg al o G0(x1,xa)G0(xa,x`)q`in a
simila way, using DISC≥ wice mo e.
We can de ine ˜
Γand Γ0 o Γin he same way as ˜
Gand G0 o G. The p oo o his key lemma
will consis o h ee s eps:
•Show ha ˜
Gsa is ies DISC≥( o some pa ame e s).
•Show ha , i he numbe o neighbou s o e e y xi∈Xiin Xi+1is oughly he same, hen
capping o he edges (going om ˜
G o G0) does no ha e a big e ec on disc epancy.
•Show ha , unde he hypo heses o he key lemma, he g aph Ghas a big subg aph which
sa is ies he simila neighbou hoods condi ion.
42 Remo al lemmas in spa se g aphs
We begin by showing he i s s ep, which consis s o Lemmas 3.23 and 3.24. These wo will ocus
on he p ocess o a e aging.
The i s lemma says ha , by aking he a e age o wo bipa i e g aphs, i each o hem sa is ies
DISC≥, hen he a e age also sa is ies DISC≥, and he pa ame e s qand pa e he p oduc o he
equi alen pa ame e s in each bipa i e g aph. The p oo uses a ‘ ew bad e ices’ a gumen : we
show ha he e a e ew e ices o which a ce ain alue is a om he a e age, and show ha
he ones close o he a e age a e enough ha G0sa is ies DISC≥ ega dless o he beha iou o
hose bad e ices. We al eady used his a gumen in he p oo o Lemma 2.13, and we will use i
o en in he p oo o he key lemma.
Lemma 3.23. Le G be a weigh ed g aph on e ex se s X, Y and Z. Le p1,p2,e∈(0, 1]and q1∈
(0, p1], q2∈(0, p2]. I (X,Y)Gsa is ies (q1,p1,e)-DISC≥and (Y,Z)Gsa is ies (q2,p2,e)-DISC≥,
hen he g aph ˜
G(x,z) = G(x,Y,z)sa is ies (q1q2,p1p2, 6√e)-DISC≥.
P oo . Le :X→[0, 1]and g:Z→[0, 1]be any wo unc ions. Le
Y0=
y∈Y:Z
X
(G(x,y)−q) (x)≤ −√ep1
Then, applying he DISC≥condi ion on (X,Y)Gwi h weigh unc ions and 1Y0we ob ain
−ep1
DISC≥
≤Z
XZ
Y
(G(x,y)−q1) (x)1Y0(y)
=Z
Y
Z
X
(G(x,y)−q1) (x)
1Y0(y)
≤Z
Y−√ep11Y0(y)
=−√ep1|Y0|
|Y|
This means ha |Y0| ≤ √e|Y|. Simila ly, we de ine Y00 as
Y00 =
y∈Y:Z
Z
(G(y,z)−q2)g(z)≤ −√ep2
which sa is ies |Y00| ≤ √e|Y| o he same eason. The conslusion is ha |Y (Y0∪Y00)| ≥ (1−
2√e)|Y|. We apply hese o bound he in eg al:
43
Z
XZ
Z
˜
G(x,z) (x)g(z)dzdx =Z
XZ
ZZ
Y
G(x,y)G(y,z) (x)g(z)dydzdx
=Z
Y
Z
X
G(x,y) (x)dx
Z
Z
G(y,z)g(z)dz
dy
G, ,g≥0
≥Z
Y
Z
X
G(x,y) (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) (x)dx
Z
Z
G(y,z)g(z)dz
dy
≥(1−2√e)Z
Y0 (Y0∪Y00)
Z
X
G(x,y) (x)dx
Z
Z
G(y,z)g(z)dz
dy
Y0,Y00
≥(1−2√e)
q1Z
X
(x)−√ep1
q2Z
Z
g(z)−√ep2
Expanding and emo ing some posi i e e ms
≥q1q2Z
X
(x)Z
Z
g(z)−2√eq1q2Z
X
(x)Z
Z
g(z)−2e√ep1p2
−√ep1q2Z
Z
g(z)−√ep2q1Z
X
(x)
,g≤1,q≤p
≥Z
XZ
Z
q1q2 (x)g(z)−6√ep1p2
Rea anging he e ms we ob ain R
XRZ
(˜
G(x,z)−q1q2) (x)g(z)≥ −6√ep1p2u
This esul applies o he case m=2. I we apply induc ion on Lemma 3.23 we can p o e ha ˜
G
sa is ies DISC≥ o a gene al m≥2, by me ging he g aphs wo by wo:
Lemma 3.24. Le G be a weigh ed g aph wi h e ex subse s X0,X1, ..., Xm, wi h m ≥2. Le 0<
e<1. I (Xi−1,Xi)Gsa is ies (qi,pi,e)-DISC≥ o all 1≤i≤m, hen he g aph ˜
G(x0,xm) =
G(x0,X1, ..., Xm−1,xm)sa is ies (q1q2···qm,p1p2···pm, 36e1
2m)-DISC≥.
P oo . We can de ine (Xi,Xj)˜
G o any i<jas ˜
G(xi,xj) = G(xi,Xi+1, ..., Xj−1,xj)(we a e aking
he a e age o he pa hs om one e ex se s o ano he ). We will show ha , i 0 <j−i≤2k o
a non-nega i e in ege k, hen (Xi,Xj)˜
Gsa is ies (qi+1···qj,pi+1···pj, 36e2−k). We p oceed by
induc ion on k.
44 Remo al lemmas in spa se g aphs
Fo k=0 we ha e j−i=1, so by hypo hesis, (Xi,Xj)sa is ies (qj,pj,e)-DISC≥and hence
(qj,pj, 36e)-DISC≥. I k>0 and j−i≤2k−1, hen by induc ion (Xi,Xj)˜
Gsa is ies (qi+1···qj,
pi+1···pj, 36e2−(k−1))-DISC≥and he e o e (qi+1···qj,pi+1···pj, 36e2−k)-DISC≥(because 36e2−(k−1)≤
36e2−k).
Assume ha k>0 and j−i>2k−1. Then by induc ion (Xi,Xi+2k−1)˜
Gsa is ies (qi+1···qi+2k−1,
pi+1···pi+2k−1, 36e2−(k−1))-DISC≥and (Xi+2k−1,Xj)˜
Gsa is ies (qi+2k−1+1···qj,pi+2k−1+1···pj,
36e2−(k−1))-DISC≥. Applying Lemma 3.23 (wi h e0=36e2−(k−1)) we ob ain ha (Xi,Xj)˜
Gsa is-
ies (qi+1···qj,pi+1···pj, 36e2−k).
To inalize, he e is an in ege ksuch ha m≤2k<2m. Fo his alue o k,(X0,Xm)˜
G0sa is-
ies (q1q2···qm,p1p2···pm, 36e2−k)-DISC≥, and 36e2−k≤36e1
2m. We conclude ha (X0,Xm)˜
G0
sa is ies (q1q2···qm,p1p2···pm, 36e1
2m)-DISC≥.u
This comple es he i s s ep o he p oo , as we ha e shown ha ˜
Gsa is ies DISC≥. The second
s ep is by a he mos complex in he p oo , and i will consis o Lemmas 3.26, 3.27 and 3.28. I
will equi e he de ini ion o bounded g aphs:
De ini ion 3.25. Le Γbe a weigh ed bipa i e g aph on e ex se s Xand Y. We say ha (X,Y)Γ
is (p,ξ,η)-bounded i he ollowing wo condi ions hold: Γ(x,y)≤η o all x∈Xand y∈Y,
and |Γ(x,Y)−p| ≤ ξp o e e y x∈X.
The ηcondi ion is simple: i is a bound o he weigh o he edges. The ξcondi ion is a bi mo e
sub le, and says ha e e y e ex om xhas oughly he same numbe o neighbou s in Y.
Two impo an hings o no e in his de ini ion: i s , his de ini ion can only be applied o un-
weigh ed g aphs i η≥1 (which is equi alen o η=1), as he weigh o any edge is ei he 0 o
1. Second, he de ini ion is no symme ic: (X,Y)Γsa is ying boundedness does no imply ha
(Y,X)Γsa is ies boundedness, because we impose |Γ(x,Y)−p| ≤ ξp o e e y x∈Xbu we
do no impose ha |Γ(X,y)−p| ≤ ξp. Fo example, in Figu e 2, he g aph (X,Y)on he le is
a good candida e o sa is y boundedness, bu he g aph (X,Y)on he igh is no (because he ξ
condi ion says ha e e y e ex om Xhas oughly he same numbe o neighbou s in Y).
FIG. 2. Example o assyme y o boundedness
Now we can s a e he i s lemma o s ep 2:
45
Lemma 3.26. Le X, Y and Z be h ee e ex se s, and le p1,p2,ξ1,ξ2,ξ3∈(0, 1], and η1,γ2>0. Le
Γbe a weigh ed g aph such ha (X,Y)Γis (p1,ξ1,η1)-bounded and (Y,Z)Γis (p2,ξ2, 1)-bounded and
(p2,γ=γ2)-jumbled. Le η0=max{4γ2
2p−1
2ξ−1
3η1, 4p1p2}and ξ0=ξ1+2ξ2+2ξ3. I ˜
Γ(x,z) =
Γ(x,Y,z)and Γ0=min{˜
Γ,η0}, hen (X,Z)Γ0is (p1p2,ξ0,η0)-bounded.
The s a emen says ha , i (X,Y)Γis bounded and (Y,Z)Γis bounded and jumbled, hen (X,Z)Γ0
is also bounded, wi h ce ain pa ame e s. The ela ions be ween he pa ame e s a e qui e echnical,
bu he ole o each o hem can clea ly be seen in he s a emen , excep o one: ξ3is a ade-o
pa ame e . This means ha , i we wan (p,ξ0,η0)-boundedness in Γ0, by inc easing ξ3we can
inc ease ξ0and dec ease η0, o he opposi e by dec easing ξ3. The p oo will be e y echnical,
and uses a ‘ ew bad e ices’ a gumen .
P oo . To see ha Γ0is bounded, we mus check ha Γ0(x,y)≤η0,Γ0(x,Y)≤(1+ξ0)p1p2and
Γ0(x,Y)≥(1−ξ0)p1p2. The i s one is i ial om he de ini ion o Γ0.
F om he de ini ion o Γ0we ob ain Γ0(x,y)≤˜
Γ(x,y)and Γ0(x,Y)≤˜
Γ(x,Y). Now, we can use
he boundedness o (X,Y)Gand (Y,Z)G o ob ain
Γ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 he second condi ion o
boundedness.
Finally, we need o p o e Γ0(x,Y)≥(1−ξ0)p1p2. Fix some x∈X. We de ine Z0
x={z∈Z:
Γ(x,Y,z)>η0}( his is he same ‘bad e ex’ idea as in o he lemmas). Then we ha e ha
Γ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 he ollowing chain o inequali ies:
46 Remo al lemmas in spa se g aphs
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|
(de . 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 }
(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|
F om his inequali y we ind a bound o |Z0
x|
|Z|, which is |Z0
x|
|Z|≤4γ2
2(1+ξ1)p1η1
η02. Also, om he chain
o inequali ies we ha e η−1
1|Z0
x|
|Z|Γ(x,Y,Z0
x)−Γ(x,Y)p2|Z0
x|
|Z|≤γ2 (1+ξ1)p1η−1
1|Z0
X|
|Z|, which can
be ea anged as |Z0
x|
|Z|Γ(x,Y,Z0
x)≤γ2 (1+ξ1)p1η1|Z0
X|
|Z|+p2Γ(x,Y)|Z0
x|
|Z|. Plugging one in o he
o he we ob ain:
|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
(de . η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 o wha we wan ed o p o e,
Γ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 comple es he p oo o he hi d condi ion o boundedness, hence we conclude ha (X,Z)Γ0
is (p1p2,ξ0,η0)-bounded. u
47
Nex , we will use Lemma 3.26 as an induc ion s ep o ex end i o a pa h o med by mbipa i e
g aphs, he bigges di e ence now is ha he e is no ade-o pa ame e :
Lemma 3.27. Le X0,X1, ..., Xmbe e ex se s, wi h m ≥2. Le c and ξbe such ha 0<4c2<ξ<1
4m,
and 0<p≤1. Le Γbe a g aph such ha (Xi−1,Xi)Γis (p,ξ, 1)-bounded and (p,γ=cp1+1
2m−2)-
jumbled o all 1≤i≤m. Le ˜
Γ(x0,xm) = Γ(x0,X1, ..., Xm−1,xm)and Γ0=min{˜
Γ, 4pm}. Then Γ0is
(pm, 4mξ, 4pm)-bounded.
Again, he e a e h ee condi ions ha we need o p o e o show boundedness. Like in he p oo o
Lemma 3.26, one is i ial, one equi es ew calcula ions, and he las one is he mos complica ed
one. In his case, we apply Lemma 3.26 o se s o wo g aphs, applying he a e age-and-bound
p ocedu e o hem and using induc ion o show he boundedness a e is eps.
P oo . The condi ion Γ0(x0,xm)≤4pmcomes om he de ini ion o Γ0. To ob ain Γ0(x0,Xm)≤
(1+4mξ)pmwe expand and use boundedness on each g aph:
Γ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 he mean alue heo em2. All we need o p o e is
Γ0(x0,Xm)≥(1−4mξ)pm
Fo his p oo we will need o de ine some in e media e g aphs. We will cons uc Γi o 1 ≤
i≤m.Γihas e ex se s X0,Xiand Xi+1, excep o Γmwhich will only ha e X0and Xm.We
cons uc Γ1as (X0,X1)Γ1= (X0,X1)Γand (X1,X2)Γ1= (X1,X2)Γ. Fo 2 ≤i<m, we de-
ine Γ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 alue o ηiis
ηi=max{(4c2ξ−1)i−1p(i−1)(1+1
m−1), 4pi}
Fi s we see ha ηm=max{(4c2ξ−1)m−1pm, 4pm}=4pm, since 4c2<ξ, and his means ha
(4c2ξ−1)m−1pm<pm<4pm. Mo eo e , we claim ha , i ηi=4pi, hen ηi+1=4pi+1. Indeed, o
i≥2, we ha e (4c2ξ−1)i−1p(i−1)(1+1
m−1)≥4pi⇔4c2ξ−1p(1+1
m−1)≥4p(1+1
i−1), and he igh hand
side o his las inequali y is dec easing on i, while he le hand side does no depend on i. Fo
i=1, η1=4p⇒max{1, 4p}=4p⇒p≥1
4≥c2ξ−1⇒η2=max{4c2ξ−1p, 4p2}=4p2. As a
consequence, he e is some be ween 1 and m o which ηi= (4c2ξ−1)i−1p(i−1)(1+1
m−1) o i<
and ηi=4pi o i≥ . In addi ion, η1=max{1, 4p} ≥ 1.
We now claim ha (X0,Xi)Γiis (pi, 4iξ,ηi)-bounded. We p oceed by induc ion on i. Fo i=
1, (X0,X1)Γ1= (X0,X1)Γis (p,ξ, 1)-bounded, so i is also (p, 4ξ,η1)-bounded. Now, o he
2Fo (x) = exand 0 <x≤1, he e is c∈(0, 1)such ha ex−1= (x)− (0) = x 0(c) = x (c), whe e 1 = (0)<
(c)< (1)<4. Hence x<ex−1<4x, o equi alen ly, 1 +x<ex<1+4x.
48 Remo al lemmas in spa se g aphs
induc ion s ep, conside Lemma 3.26 wi h he ollowing pa ame e s: 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 ha
ηi+1=max{4γ2
2p−1
2ξ−1
3η1, 4p1p2}.
I i< , hen 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. I i≥ hen 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, i (X0,Xi)Γiis (pi, 4iξ,ηi)-bounded, hen (X0,Xi+1)Γi+1is (pi+1, 4(i+1)ξ,ηi+1)-
bounded. By induc ion, (X0,Xm)Γmis (pm, 4mξ, 4pm)-bounded.
Finally, we no ice ha Γi(x0,xi)≤Γ(x0,X1, ..., Xi−1,xi). Indeed, his is i ially ue o i=1, and
i i holds o some i, hen
Γi+1(x0,xi+1)de . Γ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 ha Γm(x0,xm)≤min{Γ(x0,X1, ..., Xm),ηm=4pm}=Γ0(x0,xm)and
Γ0(x0,Xm)≥Γm(x0,Xm)bound.
≥(1−4mξ)pm
u
To inish he second s ep we need o ex end his esul om Γ o G. This is he i s ime ha bo h
Γand Gappea in he same lemma in he p oo o he coun ing lemma. Lemma 3.28 says ha
i Gis a pa h o bipa i e g aphs sa is ying DISC≥, and hey a e subg aphs o bipa i e g aphs Γ
which a e jumbled and bounded, hen G0( he esul o he a e age-and-bound p ocedu e) is also
DISC≥, wi h some app op ia e pa ame e s, which is wha he second s ep claims. The p oo is
based on he ac ha we know ha Γ0is bounded (Lemma 3.27) and ˜
Gsa is ies DISC≥(Lemma
3.24), and combining hose wo esul s using he inequali y ˜
Γ−Γ0≥˜
G−G0.
Lemma 3.28. Le 0<4c2<ξand 0<p≤1. Le X0,X1, ..., Xmbe e ex se s, wi h m ≥2.
Le Γbe a g aph and G be a subg aph o Γsuch ha (Xi−1,Xi)Γis (p,ξ, 1)-bounded and (p,γ=
cp1+1
2m−2)-jumbled, and (Xi−1,Xi)Gsa is ies (qi,p,e)-DISC≥, o all 1≤i≤m. Le ˜
G(x0,xm) =
G(x0,X1, ..., Xm−1,xm)and G0=min{˜
G, 4pm}. Then G0sa is ies (q1q2...qm
| {z }
=q
,pm, 36e1
2m+8mξ)-
DISC≥.
P oo . We can suppose ha ξ<1
4m, as o he wise 8mξ≥2 and any g aph sa is ies (q,p, 2)-DISC≥
(since G≥0, he in eg al R(G−q)u is bounded by −q, and −q≥ −p).
Conside he ollowing inequali y: ˜
Γ−Γ0≥˜
G−G0, whe e ˜
Γand Γ0a e de ined analogously3as
˜
Γand Γ0, espec i ely. Bo h he RHS and he LHS a e non-nega i e. I he RHS is ze o, hen he
3˜
Γ(x0,xm) = Γ(x0,X1, ..., Xm−1,Xm)and Γ0=min{˜
Γ, 4pm}
49
inequali y holds. I he RHS is nonze o, hen G0=4pm, which means ha Γ0=4pm=G0and he
inequali y becomes ˜
Γ≥˜
G, which is ue. We conclude ha ˜
Γ−Γ0≥˜
G−G0holds in all cases.
We wan o p o e ha , o any :X0→[0, 1]and g:Xm→[0, 1],
Z
X0Z
Xm
(G0(x0,xm)−q) (x0)g(xm)≥ −(36e1
2m+8mξ)pm
We spli he in eg al in o wo:
Z Z(G0−q) g =−Z Z(˜
G−G0) g +Z Z(˜
G−q) g
3.24
≥ −Z Z(˜
Γ−Γ0) 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
u
whe e in he las inequali y we used ha 1 +x≤ex≤1+4x o 0 ≤x≤1 o ob ain (1+ξ)m≤
eξm≤1+4mξ. This comple es he p oo o he lemmas o ming he second s ep.
Fo he hi d s ep, we need o show ha he e is a la ge enough subg aph o G ha sa is ies
boundedness. The p oo will consis o applying a ‘ ew bad e ices’ a gumen on each se .
Lemma 3.29. Le 0<δ,˜
γ,ξ,p<1sa is y 2˜
γ2≤δξ2p2. Le Γbe a g aph wi h e ex subse s
X0,X1, ..., Xmsuch ha (Xi−1,Xi)Γis (p,γ= (1−δ)˜
γ)-jumbled. Then we can ind ˜
X0,˜
X1, ... ˜
Xm, wi h
˜
Xi⊆Xiand |˜
Xi| ≥ (1−δ)|Xi|such ha (˜
Xi−1,˜
Xi)Γis (p,ξ, 1)-bounded and (p,γ=˜
γ)-jumbled o
all 1≤i≤m.
P oo . Any choice o subse s ˜
Xiwi h |˜
Xi| ≥ (1−δ)|Xi|will su ice o he jumbledness condi ion,
because o any ˜
X0
i−1⊆˜
Xi−1and ˜
X0
i⊆˜
Xi, using Lemma 3.19, we ha e
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 o subse s is only impo an o he boundedness condi ion. We will c ea e he se s ˜
Xi
in dec easing o de o i, om ˜
Xm o ˜
X0. We begin by making ˜
Xm=Xm. Now suppose ha we
ha e c ea ed ˜
Xi+1, and ha |˜
Xi+1| ≥ (1−δ)|Xi+1|. Le Xi,1 be he se o elemen s om Xiwi h
Γ(xi,˜
Xi+1)>(1+ξ)p his will play he ole o he se o bad e ices. Now, using jumbledness
wi h (xi) = 1Xi,1 and g(xi+1) = 1˜
Xi+1, we ob ain
|Xi,1|
|Xi||˜
Xi+1|
|Xi+1|ξp
de . 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 Remo al lemmas in spa se g aphs
FIG. 3. G aphs esul ing om he doubling p ocess
FIG. 4. P ocedu e o p o e he coun ing lemma o iangles
3.5. The emo al lemma
In his sec ion we p o e he emo al lemma o cycles in spa se pseudo andom g aphs. The p oo
will be analogous o he p oo in he dense case, wi h some ex a a en ion equi ed o he pseu-
do andomness pa ame e s in ol ed.
Fo his p oo , we will use he egula i y lemma and he coun ing lemma. In pa icula , he e -
sions o hose lemmas ha we will use will be Lemma 3.8 and Co olla y 3.33, espec i ely. The
e sion o he emo al lemma ha we p o e is:
Theo em 3.34 (Remo al lemma o pseudo andom g aphs). Fo e e y in ege `≥5, and e e y
µ>0 he e a e δ(`,µ)>0and c(`,µ)>0 o which he ollowing holds: le X1,X2, ..., X`be e ex se s,
each wi h n e ices. Le Γbe a g aph o which (Xi,Xi+1)Γis (p,γ=cp `)-jumbled o all 1≤i≤`,
and le G be a subg aph o Γ. I ||C`→G||X≤δp`n`, hen i is possible o emo e a mos µpn2edges
om G so ha ||C`→G||X=0.
Remembe ha ||C`→G||Xdeno es he cycles in which he i- h e ex is in Xi o all 1 ≤i≤`.
57
Lemma 3.8 and Co olla y 3.33, as well as his heo em, use he same no a ion (e,c) o hei
pa ame e s, bu now we wan o assign hem di e en alues while a oiding con usion. Fo his
pu pose, we will use he ollowing unc ions:
•In Lemma 3.8, o e e y e>0 and e e y posi i e in ege m he e exis c= 1(e,m)and
M= 2(e,m), o which he s a emen holds.
•In Co olla y 3.33, o e e y `≥5 and e e y α,θ>0 he e exis c= 3(`,α,θ)and e=
4(`,α,θ) o which he s a emen holds
Now we can p o e he emo al lemma o pseudo andom g aphs:
P oo o Theo em 3.34. Once again, we conside 0 <µ≤1
2, as o he wise i is enough o emo e
1
2pn2edges. We conside c1= 3(`,µ
2`,1
2)and e1= 4(`,µ
2`,1
2). We conside e=min{e1,µ
12`2},
c2= 1(e,`)and M= 2(e,`)Finally, le δ=1
2µ
12`M`and c=min{c1,c2
M,√e,`
M}. We claim
ha hese alues sa is y he s a emen o he heo em.
I (Xi,Xi+1)Γis (p,γ=cp `)-jumbled, hen i is also (p,γ=c2p)-jumbled. By Lemma 3.8, o
his alue o c he e is an e- egula pa i ion Pin o knon-excep ional pa s, `≤k≤M, which
e ines all se s Xi, by aking P0={X1,X2, ..., X`}as he ini ial pa i ion.
Cons uc G∗by aking Gand pe o ming he ollowing ope a ions:
•Dele e all edges ha ing one o i s ends in he excep ional se .
•Dele e all edges be ween pai s no sa is ying disc epancy.
•Dele e all edges on pai s o pa s sa is ying (qi,j,p,e)-DISC wi h qi,j<µ
6`2p( hese a e he
pai s o pa s wi h small densi y).
The numbe o edges ha we emo e is a mos µpn2. Le us see why:
•Le V0be he excep ional se om P. Le 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 a gumen shows ha eG(V0,i,Xi−1)≤µ
6`pn2. The o al numbe o edges emo ed
in his s ep is a mos
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
•The e a e a mos ek2pai s no sa is ying disc epancy. Each o hem is be ween a pai o
e ex se s Vi,Vj, wi h size `n
k≥ |Vi| ≥ `n
2k. The numbe o edges be ween hem is, by he
jumbledness o Γ,
eG(Vi,Vj)≤eΓ(Vi,Vj)≤p|Vi||Vj|+cp `nq|Vi||Vj| ≤ pn2 `
k2
+c`
k!≤2`2
k2pn2
58 Remo al lemmas in spa se g aphs
The numbe o edges emo ed in he second s ep is a mos
∑
(Vi,Vj)i .
eG(Vi,Vj)≤ek22`2
k2pn2≤µ
12`2k22`2
k2pn2<µ
3pn2
•The e a e a mos k2pai s o pa s sa is ying (qi,j,p,e)-DISC wi h qi,j≤µ
6`2p. Fo hose pai s,
eG(Vi,Vj)≤qi,j|Vi||Vj|+ep|Vi||Vj| ≤ µ
6`2p`n
k2
+µ
12`2p`n
k2
≤µpn2
3k2
The o al numbe o edges emo ed in he hi d s ep is a mos k2µpn2
3k2≤µ
3pn2.
Al oge he , he numbe o edges ha a e emo ed in he cons uc ion o G∗is a mos µpn2.
Assume ha ||C`→G∗||X6=0. Then each o he e ices o he cycle is con ained in a non-
excep ional pa o P, since in he cons uc ion o G∗we emo ed all edges inciden o he excep-
ional se . Also, he edges o he cycle lie on di e en e ex se s Xiso, since P e ines all he se s
Xi, he e ices o he cycle lie on di e en pa s o P. We call hose pa s V1,V2, ..., V`, wi h Vi⊆
Xi. The g aph (Vi,Vi+1)Γis (p,γ=cp `)-jumbled, so i is also (p,γ=c2p `)-jumbled. The g aph
(Vi,Vi+1)Gis (qi,p,e)-DISC o some qi≥µ
6`2p, so i is also (qi,p,e1)-DISC≥. By Co olla y 3.33,
he numbe o cycles wi h one e ex in each Viis a leas 1
2µ
6`2p|Vi|`
≥1
2µ
6`2p`n
2M`
=δp`n`.
This shows ha , i ||C`→G||X≤δp`n`, hen we can emo e a mos µpn2edges om G(by
cons uc iong G∗) so ha ||C`→G∗||X=0, which is wha he heo em s a es. u
3.6. Applica ion: The spa se a i hme ic emo al lemma
As a conclusion o his hesis, we will p o e a spa se e sion o Theo em 2.23, which can be ound
in [ConFox1], using he spa se emo al lemma ha we jus p o ed. Like in he case o he g aph
emo al lemma, when we mo e o a spa se en i onmen we shall wo k in subse s o a pseudo an-
dom se . Fo his eason, we will wo k wi h jumbled se s:
De ini ion 3.35 (Jumbled se ). Le Gbe a ini e g oup o o de n. We say ha a se Sis (p,β)-
jumbled i , o any X,Y⊆G, we ha e
||{(x,y)|x∈X,y∈Y,xy ∈S}|− p|X||Y||≤βq|X||Y|
This de ini ion looks e y simila o ha o jumbled bipa i e g aphs. Indeed, his is wha will
allow us o go om one emo al lemma o he o he :
Lemma 3.36. Le G be a ini e g oup, le p,β>0and S ⊆G. Le Γbe a bipa i e g aph de ined as
ollows: i has wo e ex se s X and Y, each wi h n e ices, which a e labeled wi h he elemen s o G. We
join xg1∈X and yg2∈Y i and only i g−1
1g2∈S. Then he g aph Γis (p,β)-jumbled i and only i S
is (p,β)-jumbled.
59
P oo . Le Aand Bbe subse s o G. We deno e by A−1 he se o in e ses o all he elemen s om
A. Since in e sion in a g oup is a bijec ion, hen |A−1|=|A|. Deno e by XA−1 he se o e ices
om Xwhose labels a e in A−1, and by YB he se o e ices om Ywhose labels a e 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 ha e ha
|{(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 ha g oup jumbledness implies g aph jumbledness. On he o he hand, any subse s
o Xand Ycan be w i en as XA−1and YB o app op ia e Aand B, so he equi alence o bo h
ypes o jumbledness ollows. u
Using his equi alence, we can ake he p oo o Theo em 2.23 and ex end i o he spa se jumbled
case. Remembe ha C(S1,S2, ..., Sk)is he numbe o solu ions o x1x2···xk=1 wi h xi∈Si:
Theo em 3.37 (A i hme ic spa se emo al lemma). Fo any in ege k ≥3and any e>0 he e exis
δ(k,e)>0and c(k,e)>0 o which he ollowing holds: o any abelian g oup o o de n, and any
(p,β=cp kn)-jumbled subse S, i S1, S2, ..., Ska e subse s o S o which C(S1,S2, ..., Sk)≤δpknk−1,
hen he e a e subse s S0
i⊆Siwi h |Si| |S0
i| ≤ epn and C(S0
1,S0
2, ..., S0
k) = 0.
P oo . We cons uc he g aph Kas ollows: we conside k e ex se s Xi, each o which con aining
n e ices, each o which co esponds o an elemen o G. We deno e by i,g he e ex om Xi
co esponding o g∈G. We join i,g1and i+1,g2i and only i g−1
1g2∈Si. We do he same o
k,g1and 1,g2( ha is, we ea X1as Xk+1).
Le Γbe a g aph on he same se s o e ices, whe e we join i,g1and i+1,g2i and only i g−1
1g2∈
S. Since Si⊆S o all i, e e y edge o Kis also an edge o Γ, and Kis a subg aph o Γ. In
addi ion, due o he jumbledness condi ion on S, he g aph (Xi,Xi+1)Γis (p,β)-jumbled.
As we showed in he p oo o Theo em 2.23, ||Ck→K||X=nC(S1,S2, ..., Sk), since each solu ion
o x1x2···xk=1 gene a es ndisjoin cycles. Conside he alues o δand c ha esul om
Theo em 3.34 o `=kand µ=e
k. Fo hose alues, (Xi,Xi+1)Γis (p,β=cp kn)-jumbled
and ||Ck→K||X=nC(S1,S2, ..., Sk)≤δpknk. This means ha we can apply he spa se emo al
lemma.
Le E0be he se o a mos µpn2edges om Ksuch ha emo ing hem elimina es all cycles
wi h one e ex in each Xi( he edges dele ed in he emo al lemma). To p oduce S0
i om Si, we
emo e an elemen si∈Sii and only i he e a e a leas n
kedges o he o m i,g1and i+1,g2
wi h g−1
1g2=si. Since e e y edge co esponds o exac ly one elemen si, he numbe o emo ed
elemen s om all se s is a mos |E0|
n/k≤µpn2
n/k≤en.
60 Remo al lemmas in spa se g aphs
Assume ha C(S0
1,S0
2, ..., S0
k)6=0. Then he e is a solu ion x1x2···xk=1 wi h xi∈S0
i. This
solu ion gene a es n e ex-disjoin cycles in K, and in pa icula edge-disjoin . By cons uc ion
o E0, each o hose cycles con ains a leas one edge o E0, and ha edge is o he o m i,g1 i+1,g2
wi h g−1
1g2=xi o some 1 ≤i≤k. By pigeonhole p inciple, he alue o iis he same o a
leas n
ko hose cycles, which means ha he e a e a leas n
kdi e en edges in E0o he o m
i,g1 i+1,g2wi h g−1
1g2=xi, and his implies ha xi/∈S0
i. This is a con adic ion, so we mus ha e
C(S0
1,S0
2, ..., S0
k) = 0. u
This esul can be used o p o e a spa se e sion o Ro h’s heo em, bu he p oo is no as s aigh -
o wa d as in he dense case because we un in o a small p oblem: i could be ha Sis con-
ained in a jumbled se in G, bu 2Sis no . Fo una ely, he e is a wo ka ound: i we conside
G=Z/(4n+1)Z, hen mul iplying by 2 is an au omo phism in G, so i a se is jumbled, hen
a e mul iplying each elemen by 2 i is s ill jumbled. This is because i is an au omo phism,
|{(x,y)|x∈X,y∈Y,xy ∈S}| =|{(x,y)|x∈X,y∈Y, (x) (y)∈ (S)}|
=|{(x,y)|x∈ (X),y∈ (Y),xy ∈ (S)}|
This implies ha , i Sis con ained in a jumbled se , hen 2Sis oo.
3.7. Concluding ema ks
We ha e seen ha he egula i y lemma opens a pa h o dealing wi h p oblems ela ed o he
s uc u e o he g aph. Cayley g aphs o simila cons uc ions allow us o ex end o abelian ini e
g oups his capabili y o analyze s uc u es, which p oduces esul s such as Ro h’s heo em and
he a i hme ic emo al lemma.
We ha e also seen ha some esul s ha a e sa is ied o dense g aphs can be adap ed o spa se
g aphs using pseudo andomness. This applies o he egula i y lemma, he emo al lemma and
Ro h’s heo em, as seen he e, bu also o Tu án’s heo em [ConFox1], E d˝os-S one heo em [ConFoxZha]
and esul s om Ramsey heo y [ConFoxZha,Koh], among many o he s.
The adap ed e sions o hose heo ems ha we saw used jumbledness, bu his is no he only
measu e o pseudo andomness ha can be used. Regula i y and disc epancy, discussed he e, and
uni o mi y [S o] a e o he commonly used measu es o pseudo andomness which can se e he
same pu pose. G een and Tao [G eTao] used ano he pseudo andomness measu e in which he
se o p ime numbe s is a dense subse o a pseudo andom se in N. This allowed hem o ex end
Szeme édi’s heo em o p ime numbe s:
Theo em 3.38 (G een-Tao). The p ime numbe s con ain an in ini e numbe o non- i ial a i hme ic
k- e m a i hmeic p og essions, o all posi i e in ege s k.
Re e ences
[Aj Sze] Aj ai, M. and Szeme édi, E., Se s o la ice poin s ha o m no squa es, S udia Scien ia um Ma hema ica um Hun-
ga ica 9(1974), 9-11.
[AloFisK iSze] Alon, N., Fische , E., K i ele ich, M. and Szegedy, M., E icien es ing o la ge g aphs, Combina o ica 20
(2000), 451-476.
[ConFox1] Conlon, D. and Fox, J., G aph emo al lemmas, Su eys in Combina o ics (2013), 1-50.
[ConFox2] Bounds o g aph egula i y and emo al lemmas, Geome ic and Func ional Analysis 22 (2012), 1192-1256.
[ConFoxSud] Conlon, D., Fox, J. and Sudako , B., Sido enko’s conjec u e o a class o g aphs: an exposi ion, Geome ic and
Func ional Analysis 20 (2010), 1354-1366.
[ConFoxZha] Conlon, D., Fox, J. and Zhao, Y., Ex emal esul s in pseudo andom g aphs, Ad ances in Ma hema ics 256
(2014), 535-580.
[ConGow] Conlon, D. and Gowe s, W.T., Combina o ial heo ems in spa se andom se s.
[Die] Dies el, R., "G aph heo y", Elec onic edi ion, Sp inge -Ve lag Heidelbe g, New Yo k, 2005.
[E dS o] E d˝os, P. and S one, A.H., On he s uc u e o linea g aphs, Bulle in o he Ame ican Ma hema ical Socie y 52 (1946),
1087-1091.
[E dTu ] E d˝os, P. and Tu án, P., On some sequences o in ege s, Jou nal o he London Ma hema ical socie y 11 (1936), 261-264
[F aRod] F ankl, P. and Rödl, V., Ex emal p oblems on se sys ems, Random S uc u es Algo i hms 20 (2002), 131-164.
[Fu ] Fü edi, Z., Ex emal hype g aphs and combina o ial geome y, P oceedings o he In e na ional Cong ess o Ma hema ics
1(1994), 1343-1352.
[Gow] Gowe s, W.T., Hype g aph egula i y and he mul idimensional Szeme édi Theo em, Annals o Ma hema ics 166
(2007), 897-946.
[G e] A Szeme é y- ype egula i y lemma in abelian g oups, wi h applica ions, Geome ic and Func ional Analysis 15 (2005),
340-376.
[G eTao] G een, B. and Tao, T., The p imes con ain a bi a ily long a i hme ic p og essions, Annals o Ma hema ics 167
(2008), 481-547.
[Koh] Kohayakawa, Y., The Regula i y Lemma o Szeme édi o spa se g aphs (unpublished manusc ip , 1993).
[KomSim] Komlós, J. and Simono i s, M., Szeme édi’s Regula i y Lemma and i s applica ions in g aph heo y, Combina-
o ics, Paul E d˝os is eigh y 2(1993), 295-352.
[K aSe Ven] K ál’, D., Se a, O. and Vena, L., A combina o ial p oo o he emo al lemma o g oups, Jou nal o Combina-
o ial Theo y, Se ies A 116 (2009), 971-978.
[NagRodSch] Nagle, B., Rödl, V. and Schach , M., The coun ing lemma o egula k-uni o m hype g aphs, Random S uc-
u es Algo i hms 28 (2006), 113-179.
[RodSko] Rödl, V. and Skokan, J., Regula i y lemma o uni o m hype g aphs, Random S uc u es Algo i hms 25 (2004),
1-42.
[Ro ] Ro h, K.F., On ce ain se s o in ege s, Jou nal o he London Ma hema ical Socie y 28 (1953), 104-109
[RuzSze] Ruzsa, I.Z. and Szeme édi, E., T iple sys ems wi h no h ee poin s ca ying h ee iangles, Colloquia Ma hema ica
Socie a is János Bolyai 18 (1978), 939-945.
[Sco] Sco , A., Szeme édi’s Regula i y lemma o ma ices and spa se g aphs, Combina o ics, P obabili y and Compu ing 20
(2011), 455-466.
[Sol] Solymosi, J., No e on a gene aliza ion o Ro h’s Theo em, Algo i hms and Combina o ics 25 (2003), 825-827.
[Sze1] Szegedy, B., An in o ma ion heo e ic app oach o Sido enko’s conjec u e (2014).
[Sze2] Szeme édi, E., In ege se s con aining no kelemen s in a i hme ic p og ession, Ac a a i hme ica 27 (1975), 299-345.
61
62 Remo al lemmas in spa se g aphs
[Sze3] Szeme édi, E., Regula pa i ions o g aphs, Colloques In e na ionaux C.N.R.S. 260 (1976), 399-401.
[Tao] Tao, T., A a ian o he hype g aph emo al lemma, Jou nal o Combina o ial Theo y, Se ies A 113 (2006), 1257-1280.
