Clique factors in pseudorandom graphs

© 2023 Eu opean Ma hema ical Socie y
Published by EMS P ess and licensed unde a CC BY 4.0 license
J. Eu . Ma h. Soc. 27, 801–875 (2025) DOI 10.4171/JEMS/1388
Pa ick Mo is
Clique ac o s in pseudo andom g aphs
Recei ed July 2, 2021; e ised July 1, 2022
Abs ac . An n- e ex g aph is said o o be .p; ˇ/-bijumbled i o any e ex se s A; B V.G/,
we ha e
e.A; B/ DpjAjjBj˙ˇpjAjjBj:
We p o e ha o any 2N3and c > 0 he e exis s an ">0such ha any n- e ex .p; ˇ/-
bijumbled g aph wi h n2 N,p > 0,ı.G/ cpn and ˇ"p 1ncon ains a K - ac o . This
implies a co esponding esul o he s onge pseudo andom no ion o .n; d; /-g aphs.
Fo he case o iangle ac o s, ha is, when D3, his esul esol es a conjec u e o K i ele-
ich, Sudako and Szabó om 2004 and i is igh due o a pseudo andom iangle- ee cons uc ion
o Alon. In ac , in his case e en mo e is ue: as a co olla y o his esul and a esul o Han,
Kohayakawa, Pe son and he au ho , we can conclude ha he same condi ion o ˇDo.p2n/ ac u-
ally gua an ees ha a .p; ˇ/-bijumbled g aph Gcon ains e e y g aph on n e ices wi h maximum
deg ee a mos 2.
Keywo ds. Pseudo andom g aphs, clique ac o s, ex emal g aph heo y
Con en s
1. In oduc ion .................................................... 802
2. P oo o main heo em ............................................. 806
3. P elimina ies .................................................... 817
3.1. No a ion ................................................... 817
3.2. P ope ies o bijumbled g aphs .................................... 818
3.3. Concen a ion o andom a iables ................................. 823
3.4. Pe ec ac ional ma chings ...................................... 823
3.5. Almos pe ec ma chings in hype g aphs ............................. 825
3.6. Templa es .................................................. 828
4. Diamond ees ................................................... 829
4.1. Sca e ed diamond ees ......................................... 831
5. Cascading abso p ion h ough o cha ds .................................. 834
5.1. Abso bing o cha ds ........................................... 835
5.2. Sh inkable o cha ds ........................................... 838
6. Sh inkable o cha ds o small o de ..................................... 840
6.1. F om o cha ds o sys ems ....................................... 840
Pa ick Mo is: Depa men o Ma hema ics, Uni e si a Poli ècnica de Ca alunya, Ba celona,
Spain; [email p o ec ed]
Ma hema ics Subjec Classi ica ion (2020): P ima y 05C35; Seconda y 05C48, 05C70
P. Mo is 802
6.2. Su icien condi ions o sh inkabili y ............................... 841
6.3. The exis ence o sh inkable o cha ds o small o de ...................... 844
6.4. Con olling deg ees ela i e o emo able se s o e ices .................. 845
6.5. The exis ence o sh inkable o cha ds o la ge o de ..................... 847
7. Sh inkable o cha ds o la ge o de ..................................... 848
7.1. A densi y condi ion which gua an ees sh inkabili y ...................... 848
7.2. Popula diamond ees .......................................... 850
7.3. The exis ence o sh inkable o cha ds o la ge o de ...................... 852
7.4. P ep ocessing he o cha d ....................................... 854
7.5. Comple ing he o cha d ......................................... 857
7.6. The exis ence o sh inkable o cha ds o smalle o de .................... 859
8. The inal abso p ion ............................................... 860
8.1. De ining an abso bing s uc u e ................................... 861
8.2. Finding an abso bing s uc u e .................................... 863
9. Concluding ema ks ............................................... 871
Re e ences ........................................................ 872
1. In oduc ion
We say a g aph Gcon ains a K - ac o i he e is a collec ion o e ex disjoin copies
o K ha comple ely co e he e ex se o G. When D3, we o en e e o a K3- ac o
as a iangle ac o . As a na u al gene alisa ion o a pe ec ma ching in a g aph, K -
ac o s a e a undamen al objec in g aph heo y wi h a weal h o esul s s udying a ious
aspec s and a ian s, in pa icula explo ing p obabilis ic [11,36,39,45,51], ex emal
[4,12,62,68], and algo i hmic [18,42,44,46] conside a ions. Howe e , unlike pe ec
ma chings, i is no easy o e i y whe he a g aph Gcon ains a K - ac o o no . Ce ainly
i is necessa y ha he numbe o e ices o Gmus be di isible by bu gi en his,
i was p o ed by Schae e [43] (in he case D3) and by Ki kpa ick and Hell [46]
(in gene al) ha de e mining whe he a g aph on n2 N e ices con ains a K - ac o
is an NP-comple e p oblem. Gi en ha we canno hope o a nice cha ac e isa ion o
g aphs which con ain K - ac o s, he e has been a ocus on p o iding su icien condi ions
which a e compu a ionally easy o e i y. One classical such heo em is due o Hajnal and
Szeme édi [29] who showed ha a K - ac o is gua an eed i he hos g aph is su icien ly
dense. The case o iangle ac o s was p e iously shown by Co ádi and Hajnal [24].
Theo em 1.1. I 2N3and Gis a g aph on n2 N e ices wi h minimum deg ee
ı.G/ .1 1= /n, hen Gcon ains a K - ac o .
This heo em is igh , as can be seen, o example, by aking G o be a comple e
g aph wi h a clique o size n= C1 emo ed o lea e an independen se o e ices,
say I. One hen has ı.G/ D.1 1= /n 1and Gdoes no ha e a K - ac o . Indeed,
any copy o K in a amily o e ex disjoin K s can use a mos one e ex o Ibu a
K - ac o should con ain n= < jIjcopies o K . All examples e i ying he igh ness
o Theo em 1.1 sha e some ea u es wi h he g aph gi en he e. Fo example hey con ain
much la ge independen se s han almos all g aphs o his densi y. The e o e, one migh
hope o cap u e mo e g aphs ha ing a K - ac o by adding a condi ion ha p ecludes he
a ypical beha iou o he ex emal examples.
Clique ac o s in pseudo andom g aphs 803
This na u ally leads us o he no ion o pseudo andom g aphs, which a e, oughly
speaking, g aphs which imi a e andom g aphs o he same densi y. The s udy o pseu-
do andom g aphs, ini ia ed in he 1980s by Thomason [65,66], has become a cen al
and ib an ield a he in e sec ion o combina o ics and heo e ical compu e science.
We e e o he excellen su ey o K i ele ich and Sudako [53] o an in oduc ion o
he opic. One way o imposing pseudo andomness is h ough he spec al no ion o he
eigen alue gap. This hen leads o he s udy o .n; d; /-g aphs Gwhich a e d- egula
n- e ex g aphs wi h second eigen alue . By second eigen alue, wha is ac ually mean
is he second la ges eigen alue in absolu e alue, as ollows. Gi en an n- e ex d- egula
g aph G, we can look a he eigen alues o he adjacency ma ix Ao Gwhich, as Ais a
symme ic 0=1-ma ix, a e eal and can be o de ed as 1   n. The second eigen-
alue is hen de ined o be WDmax ¹j2j;jnjº. I u ns ou ha his pa ame e con ols
he pseudo andomness o he g aph G, wi h smalle alues o gi ing g aphs ha ha e
s onge pseudo andom p ope ies. Mo e conc e ely, he ela ion is gi en by he ollowing
p ope y o .n;d;/-g aphs (see e.g. [53, Theo em 2.1]), which is known as he Expande
Mixing Lemma and shows ha con ols he edge dis ibu ion be ween e ex se s. Fo
any e ex subse s A; B o an .n; d; /-g aph G, one has
ˇˇˇˇ
e.A; B/ d
njAjjBjˇˇˇˇpjAjjBj;(1.1)
whe e e.A; B/ WD j¹u 2E.G/ Wu2A; b 2Bºj deno es he numbe 1o edges in G
wi h one endpoin in Aand he o he in B. No e ha d=n is he densi y o he g aph G,
and hence one would expec o see d
njAjjBjedges be ween he e ex se s Aand Bin a
andom g aph G. The pseudo andom pa ame e  hen con ols he disc epancy om his
pa adigm.
I ollows om simple linea algeb a (see e.g. [53]) ha o an .n; d; /-g aph, one
has dalways and mo eo e , as long as dis no oo close o n, say d2n=3, one
has D.pd/. Thus, we hink o .n; d; /-g aphs wi h D‚.pd/ as being op i-
mally pseudo andom. Fo example, i is known ha andom egula g aphs a e op imally
pseudo andom .n; d; /-g aphs wi h high p obabili y2[16,67].
A p ominen heme in he s udy o pseudo andom g aphs has been o gi e condi ions
on he pa ame e s, n,dand  ha gua an ee ce ain p ope ies o an .n; d; /-g aph. Fo
example, i ollows easily om (1.1) ha any .n; d; /-g aph Gwi h <d2=n con-
ains a iangle as he e is an edge in he neighbou hood o e e y e ex. In pa icula ,
any op imally pseudo andom g aph wi h dD!.n2=3/mus con ain a iangle. Mo e-
o e , his condi ion is igh due o a iangle- ee cons uc ion o an .n; d; /-g aph due
o Alon [5] wi h dD‚.n2=3/and D‚.n1=3/. Alon’s cons uc ion is op imally pseu-
do andom and K i ele ich, Sudako and Szabó [54] gene alised i o he whole possible
1No e ha edges ha lie in A Ba e coun ed wice.
2He e, and h oughou , we say ha a p ope y holds wi h high p obabili y i he p obabili y ha
i holds ends o 1as he numbe no e ices ends o in ini y.
P. Mo is 804
ange o densi ies. Tha is, o any dDd.n/ such ha .n2=3/Ddn, hey ga e
a sequence o in ini ely many nand iangle- ee .n0; d; /-g aphs wi h n0D‚.n/ and
D‚.d2=n/. In gene al, inding op imal condi ions o subg aph appea ance in .n;d;/-
g aphs seems ha d. Indeed, he only igh condi ions ha a e known a e hose o ixed size
odd cycles [9,53]. Wi h espec o spanning s uc u es, i is only pe ec ma chings ha
ha e been well unde s ood [17,20,53]. Whils such ques ions a e in e es ing in hei own
igh , hey also ha e implica ions in o he a eas o ma hema ics. As an example, we men-
ion he beau i ul connec ion gi en by Alon and Bou gain [6] (see also [2]) who used he
exis ence o ce ain subg aphs in pseudo andom g aphs o p o e he exis ence o addi i e
pa e ns in la ge mul iplica i e subg oups o ini e ields.
The pu pose o his pape is o answe wha has become one o he cen al p oblems
in his a ea, by gi ing a igh condi ion o an .n; d; /-g aph o con ain a iangle ac o .
Theo em 1.2. The e exis s ">0such ha any .n; d; /-g aph wi h n23N,d > 0 and
"d2=n con ains a iangle ac o .
Theo em 1.2 was conjec u ed by K i ele ich, Sudako and Szabó [54] in 2004. Focus-
ing solely on op imally pseudo andom g aphs, ha is, se ing D‚.pd/, Theo em 1.4
implies ha any op imally pseudo andom g aph wi h dD!.n2=3/con ains a iangle
ac o . Compa ing his o Theo em 1.1, we see ha imposing pseudo andomness, which
is easy o compu e ia he second eigen alue, allows us o cap u e much spa se g aphs
which a e gua an eed o con ain a iangle ac o .
Theo em 1.2 (and he mo e gene al Theo em 1.4 below) conclude a body o wo k
owa ds he conjec u e o K i ele ich, Sudako and Szabó, and he p oo o he heo em,
discussed in Sec ion 2, builds upon he many beau i ul ideas o a ious au ho s, which
ha e a isen in his s udy. The i s s ep owa ds he conjec u e was gi en by K i ele-
ich, Sudako and Szabó [54] hemsel es, who showed ha "d3=.n2log n/ o some
su icien ly small "is enough o gua an ee a iangle ac o . This was imp o ed o 
"d5=2=n3=2 by Allen, Bö che , Hàn, Kohayakawa and Pe son [3] who also p o ed ha he
same condi ion gua an ees he appea ance o he squa e o a Hamil on cycle, a supe g aph
o a iangle ac o . Recen ly, Nenado [61] go e y close o he conjec u e, showing ha
"d2=.n log n/ gua an ees a iangle ac o . Concen a ing solely on op imally pseu-
do andom g aphs, hese esul s imply ha ha ing deg ee dD!.n4=5.log n/2=5/,!.n3=4/
and !..n log n/2=3/ espec i ely, gua an ees he exis ence o a iangle ac o .
In a di e en di ec ion, one can ix he condi ion ha "d2=n o some small ">0
and p o e he exis ence o o he s uc u es gi ing e idence o a iangle ac o . Again,
his was ini ia ed by K i ele ich, Sudako and Szabó [54] who p o ed ha wi h his con-
di ion, one can gua an ee he exis ence o a ac ional iangle ac o . Tha is, hey showed
ha he e is a unc ion wwhich assigns a weigh w.T / 2Œ0; 1 o each iangle Tin a
pseudo andom g aph Gand is such ha o e e y e ex 2V.G/, he sum P 2Tw.T /
o he weigh s o iangles con aining is p ecisely equal o 1. Imposing ¹0; 1º-weigh s
eco e s he no ion o a iangle ac o and a ac ional iangle ac o is hus a na u al
elaxa ion. Ano he in e es ing esul o Sudako , Szabó and Vu [64] showed ha when
"d2=n, we ha e many iangles and hese a e well dis ibu ed in he .n;d;/-g aph G.
Clique ac o s in pseudo andom g aphs 805
Indeed, hey p o ed a Tu án- ype esul showing ha any iangle- ee subg aph o such
a g aph Gmus con ain a mos hal he edges o G. A mo e ecen esul due o Han,
Kohayakawa and Pe son [34,35] shows ha "d2=n gua an ees he exis ence o a
nea iangle ac o : he e a e e ex disjoin iangles co e ing all bu n647=648 e ices
o such an .n; d; /-g aph.
We will deduce Theo em 1.2 om a mo e gene al heo em (Theo em 1.4 below)
which deals wi h K - ac o s o all 3and wo ks wi h a la ge class o pseudo an-
dom g aphs whe e we do no es ic solely o egula g aphs. Indeed, we will wo k wi h
he no ion o bijumbledness, whose usage da es back o he o iginal wo ks o Thoma-
son [65,66], and whose de ini ion cap u es he key p ope y o edge dis ibu ion, gi en
o .n; d; /-g aphs by (1.1).
De ini ion 1.3. Le n2N,pDp.n/ 2Œ0; 1 and ˇDˇ.n; p/ > 0. An n- e ex g aph
GD.V; E/ is .p; ˇ/-bijumbled i o e e y pai o e ex subse s A; B V, one has
ˇˇe.A; B/ pjAjjBjˇˇˇpjAjjBj:(1.2)
No e ha , due o (1.1), .n; d; /-g aphs a e .d=n; /-bijumbled. As wi h .n; d; /-
g aphs, we a e in e es ed in inding condi ions on he pa ame e s n,pand ˇ ha gua an ee
he exis ence o ce ain subg aphs in n- e ex .p;ˇ/-bijumbled g aphs. Ou main heo em
gi es condi ions o he exis ence o K - ac o s o all 3in his se ing.
Theo em 1.4. Fo e e y 2N3and c > 0 he e exis s an " > 0 such ha any n- e ex
.p; ˇ/-bijumbled g aph wi h n2 N,p > 0,ı.G/ cpn and ˇ"p 1ncon ains a
K - ac o .
We ema k ha he condi ion ha ı.G/ cpn is na u al. Indeed, De ini ion 1.3
implies ha almos all e ices will ha e deg ee a leas cpn, and some lowe bound
on minimum deg ee is necessa y o a oid isola ed e ices. Theo em 1.2 ollows di ec ly
om Theo em 1.4, and much o he con ex and pas esul s discussed abo e ha e analo-
gous s a emen s when 4wi h many au ho s also wo king in he mo e gene al se ing
o .p; ˇ/-bijumbled g aphs. In pa icula , o all 3, a condi ion o ˇDo.p 1n/
gua an ees a copy o K , and be o e Theo em 1.4 he bes condi ion known o ensu -
ing a K - ac o was ˇDo.p 1n=log n/ due o Nenado [61]. Ano he esul due o
Han, Kohayakawa, Pe son and he au ho [32] appea ed a oughly he same ime as
ha o Nenado and ga e a condi ion o ˇDo.p n/ o a K - ac o , which o 4
gi es a s onge esul han he p e iously bes known condi ion o Allen, Bö che , Hàn,
Kohayakawa and Pe son [3]. Al hough his condi ion is weake han Nenado ’s only when
he bijumbled g aph is e y dense, i u ns ou ha he p oo me hods o bo h esul s will
be use ul in p o ing Theo em 1.4.
The e is one key di e ence be ween he pic u es o D3and o 4: he igh ness
o he condi ion ˇDo.p 1n/ o bo h he clique and he clique ac o when 4is
unknown. We de e a mo e in-dep h discussion o his o ou concluding ema ks (Sec ion
9) and conclude his in oduc ion by again ocusing on he mos in e es ing case o iangle
ac o s whe e we know ha Theo ems 1.4 and 1.2 a e igh due o he cons uc ion o Alon

P. Mo is 806
(and i s gene alisa ion o he whole ange o densi ies by K i ele ich, Sudako and Szabó)
discussed abo e. Indeed, one o he easons ha he K i ele ich–Sudako –Szabó conjec-
u e (Theo em 1.2) has a ac ed so much a en ion is ha i ma ks a dis inc di e ence
be ween he beha iou o andom g aphs and ha o (op imally) pseudo andom g aphs. In
andom g aphs, we know ha iangles appea a densi y oughly pDn1, whils o i-
angle ac o s he h eshold is conside ably dense , namely pDn2=3.log n/1=3 [39] (see
also ecen esul s [37,40,41,63] ha imply ha his h eshold is sha p). On he o he hand,
he e exis iangle- ee, op imally pseudo andom g aphs wi h densi y oughly n1=3, bu
Theo em 1.4 asse s ha any pseudo andom g aph whose densi y is a cons an ac o
la ge han his is gua an eed o ha e no only a iangle bu a iangle ac o . Fu he mo e,
i ollows om Theo em 1.4 and ( he p oo o ) a esul o Han, Kohayakawa, Pe son and
he au ho [33] ha e en mo e is ue.
Co olla y 1.5. Fo e e y c > 0 he e exis s an ">0such ha any n- e ex .p; ˇ/-
bijumbled g aph wi h ı.G/ cpn,p > 0 and ˇ"p2nis 2-uni e sal. Tha is, gi en
any g aph Fon a mos n e ices, wi h maximum deg ee 2,Gcon ains a copy o F. In
pa icula , any .n; d; /-g aph Gwi h "d2=n is 2-uni e sal.
Ou p oo o Theo em 1.4 inco po a es disc e e algo i hmic echniques, p obabilis-
ic me hods, ac ional elaxa ions and linea p og amming duali y, and he me hod o
abso p ion. In he nex sec ion we discuss he p oo in de ail and educe he p oblem o
p o ing wo in e media e p oposi ions and a lemma. These will hen be p o en in wha
ollows a e de eloping he necessa y heo y.
Rema k. An accompanying con e ence e sion [59] o his wo k deals solely wi h he
se ing o Theo em 1.2. Mo e echnical pa s o he p oo a e omi ed he e and we hope
ha i se es as a gen le in oduc ion o he p esen pape .
2. P oo o main heo em
The p oo o Theo em 1.4 es s on he shoulde s o he p e ious esul s [3,32–35,54,61]
wo king owa ds he conjec u e o K i ele ich, Sudako and Szabó. Indeed, i is ai o
say ha he solu ion o he conjec u e would no ha e been possible wi hou he insigh s
and ideas o he many au ho s who ackled his p oblem. In his sec ion, we discuss hese
as well as ou no el ideas and lay ou he key concep s and scheme o he p oo . In doing
so, we will educe he heo em o se e al in e media e esul s, whose p oo s will be he
subjec o he es o he pape .
Ou p oo , like some o i s p edecesso s [3,32,61], wo ks by he me hod o abso p ion.
I u ns ou ha inding many e ex disjoin copies o K in a .p; ˇ/-bijumbled g aph G
as in Theo em 1.4 is easy. This ollows om a simple consequence o De ini ion 1.3
which gua an ees ha any small linea sized se o e ices con ains a copy o K ; see e.g.
Co olla y 3.5 (2) o a p ecise s a emen . The e o e we can g eedily choose copies o K
o be in ou K - ac o and con inue his p ocess un il we a e le wi h some small le o e
se o e ices L, whe e small means o size a mos " n, say. Howe e , a his poin we
Clique ac o s in pseudo andom g aphs 807
ge s uck: we ha e no way o gua an eeing he exis ence o a K in Land so we do no
know how o ge a la ge se o e ex disjoin copies o K . The idea o abso p ion is
o pu aside an abso bing se o e ices which can abso b he le o e e ices Lin o
aK - ac o . Tha is, be o e unning his g eedy p ocess o build a K - ac o , we ind
some special se o e ices XV.G/ which has he p ope y ha o any small se o
e ices LV.G/ nX, he e is a K - ac o in GŒX [L (unde he i ial di isibili y
cons ain ha j.jXjCjLj/). I we can ind such an Xin G, hen we can pu i o one
side and un he g eedy a gumen o co e almos all he e ices which do no lie in X,
wi h e ex disjoin copies o K . We can hen use he abso bing p ope y o abso b he
le o e e ices Land ge a ull K - ac o .
This lea es he challenge o de ining some s uc u e in Gwhich has his abso bing
p ope y and inding such a s uc u e (on some e ex se X) in G. The building blocks
o ou abso bing s uc u e will be subg aphs ha we call K -diamond ees. In wo ds, a
K -diamond ee DD.T; R; †/ is he g aph ob ained by aking a ee Tand eplacing
each edge e2E.T / by a copy o K
C1whose deg ee 1 e ices a e he e ices o e
and whose deg ee e ices a e new and dis inc om p e ious choices; see Figu e 1 o
an example. The ollowing de ini ion o malises his no ion.
R={ }
Σ= 
T=D= (T, R, Σ)
DD.T; R; †/ T D
RD ¹º
†D
Fig. 1. An example o a K3-diamond ee DD.T; R; †/ o o de 9shown on he le . The emo -
able e ices Ra e he la ge e ices o Dand he in e io cliques †a e he edges gi en in g ey.
The auxilia y ee Tis depic ed on he igh .
De ini ion 2.1. AK -diamond ee Do o de min a g aph Gis a uple DD.T; R; †/
whe e Tis an (auxilia y) ee o o de m(i.e. wi h m e ices), RV.G/ is a subse
o m e ices o Gand3†K 1.G/ is a se o m1copies o K 1in Gwi h he
ollowing p ope y. The e a e bijec i e maps WV.T / !Rand WE.T / !†such ha
 he copies o K 1in †a e pai wise e ex disjoin in Gand hey a e also disjoin
om R, i.e. V.S/ V .S0/D ; and V.S/ RD ; o all S; S02†;
 o all eDu 2E.T /, we ha e V..e// NG..u// NG.. //, ha is, he 1-
clique .e/ 2K 1.G/ can be ex ended o a copy o K in Gby adding he e ex
.u/ and likewise wi h . /.
3He e and h oughou , we use K 1.G/ o deno e he amily o . 1/-cliques in G.
P. Mo is 808
We e e o Ras he se o emo able e ices o Dand o †as he se o in e io cliques
o D. We de ine he e ices o D o be all he emo able e ices and he e ices in
in e io cliques. Tha is, V.D/WD.SS2†V .S// [R. Finally, we de ine he lea es o he
diamond ee o be he e ices which a e images o lea es in Tunde .
No e ha a K -diamond ee o o de mhas exac ly .m 1/ C1 e ices. K i ele-
ich [51] used K3-diamond ees in an abso p ion a gumen o iangle ac o s in andom
g aphs which is o en ci ed as one o he i s appea ances o he abso p ion me hod.
Nenado [61] also used his idea in his esul ha go wi hin a log- ac o o Theo em 1.4.
The u ili y o hese subg aphs in abso p ion a gumen s comes om he ollowing key
obse a ion which shows ha hey can con ibu e o a K - ac o in many ways.
Obse a ion 2.2. Gi en a K -diamond ee DD.T; R; †/ in G, o any emo able
e ex 2R he e is a K - ac o o GŒV .D/n¹ º. Indeed, conside uD1. / in V.T /
and he map 'WE.T / !V.T / n¹uºwhich maps each edge eo T o he e ex in ewhich
has he la ge dis ance om uin T. Then 'is a bijec ion and aking he copies o K on
.e/ [.'.e// o each edge e2E.T / gi es he equi ed K - ac o . See Figu e 2 o
some examples.
Fig. 2. Some examples o K3- ac o s ound a e emo ing a emo able e ex om he K3-
diamond ee in Figu e 1(see Obse a ion 2.2).
Obse a ion 2.2 wo ks o any unde lying auxilia y ee T. I u ns ou ha in he
.p; ˇ/-bijumbled g aphs Gwe a e in e es ed in, one can ind K -diamond ees o any
o de up o linea size. Indeed, one can use he a gumen o K i ele ich [51] o cons uc
hese o a di e en a gumen due o Nenado [61]. The me hod o Nenado gi es diamond
ees whose auxilia y ee is a pa h, whils he a gumen o K i ele ich gi es no con ol
o e he unde lying auxilia y ee which de ines he diamond ee ound. As a key pa
o ou a gumen , we will need o p o e he exis ence o diamond ees which ha e ex a
s uc u e, as we discuss sho ly.
In o de o u ilise he abso bing powe o diamond ees, we need o g oup hem
oge he in collec ions. The ollowing de ini ion o an o cha d cap u es how we do his.
De ini ion 2.3. We say a collec ion OD ¹D1; : : : ; Dkºo pai wise e ex disjoin K -
diamond ees in a g aph Gis a .k; m/ -o cha d i he e a e kdiamond ees in he
Clique ac o s in pseudo andom g aphs 809
collec ion and each has o de a leas mand a mos 2m. We e e o kas he size o
he o cha d, and o mas i s o de .4We deno e by V .O/ he e ices ea u ing in diamond
ees in O, ha is, V.O/DSi2Œk V.Di/. Finally, i O0Ois a subse o diamond ees
in an o cha d O, we call O0asubo cha d o O.
The e m o cha d he e is supposed o be ins uc i e, indica ing ha his is a ‘nea ’
collec ion o diamond ees ha all ha e a simila o de and a e comple ely disjoin
om one ano he . As no ed in Obse a ion 2.2, a K -diamond ee can con ibu e o a
K - ac o in many ways. By g ouping oge he many e ex disjoin K -diamond ees
in o a .k; m/ -o cha d such ha km D.n/, we ge a s uc u e wi h a s ong abso b-
ing p ope y, as he ollowing lemma shows. We say a .K; M / -o cha d Oabso bs a
.k; m/ -o cha d Ri he e is an .. 1/k; M / -subo cha d O0Osuch ha he e is a
K - ac o in GŒV.R/[V.O0/.
Lemma 2.4. Fo any 2N3and 0 < ; < 1 he e exis s an " > 0 such ha he ollowing
holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n. Le Obe a .K; M / -
o cha d in Gsuch ha KM n. Then he e exis s a se BV.G/ such ha jBj 
p2 4nand Oabso bs any .k; m/ -o cha d Rin Gwi h
V.R/ .B [V.O// D ;; k K=.8 / and kM mK: (2.1)
Mo ally, Lemma 2.4 says ha la ge o cha ds abso b small o cha ds. He e, by la ge we
e e o bo h he size and he o de o he o cha ds. Indeed, he second condi ion in (2.1)
shows ha he la ge o cha d has o ha e a la ge size han he smalle o cha d. This is he
c i ical condi ion when we wan abso p ion be ween o cha ds o simila o de . The hi d
condi ion shows ha he a io be ween he o de s o he o cha ds is cons ained by he
a io o he sizes. Tha is, he la ge Ois compa ed o Rwi h espec o hei sizes, he
smalle Rcan be han Owi h espec o hei o de s. This will be he c i ical condi ion
when we wan abso p ion be ween o cha ds o (polynomially) di e en o de s. The i s
condi ion in (2.1) simply s a es ha in o de o O o abso b R, we need ha Ra oids
some small se Bo bad e ices. This will be easy o implemen in applica ions.
Lemma 2.4 will be p o en in Sec ion 5.1. I p o ides us wi h an abso p ion p ope y
be ween wo dis inc o cha ds. We will also need an abso p ion p ope y wi hin o cha ds
hemsel es, showing ha we can ind a la ge subo cha d which hos s a K - ac o in G.
Gi en Obse a ion 2.2, in o de o ind K - ac o s on subo cha ds i su ices o ind copies
o K which a e se se s o emo able e ices. We he e o e make he ollowing de ini-
ion.
De ini ion 2.5. Gi en a .k; m/ -o cha d OD ¹D1; : : : ; Dkºin a g aph G, he K -
hype g aph gene a ed by O, deno ed HDH.O/, is he -uni o m hype g aph wi h
4No e ha we abuse no a ion sligh ly he e. Indeed, we e e o he o de o an o cha d al hough
his may no be uniquely de ined by he o cha d. We ake he con en ion ha when we e e o he
o de o an o cha d, we simply ix one o he possible o de s a bi a ily, no ing ha hese possible
o de s di e by a ac o o a mos 2.
P. Mo is 816
D ;. The e o e, by Lemma 2.4,Qiabso bs any subo cha d POi1wi h jPj  k1
i1
i k1
i1k
i=.8 / and k1
i1mik
imi1.
Now as miDnmi1and n1=.8 / o su icien ly la ge n, i su ices o show
ha k1
i1k
in. To see his, no e ha since ˛n ki1mi1and kimi2˛n, we
ha e
ki12˛n
mi1D2˛n1C
mi2kin2k
in
;
and using his as a lowe bound o k
i, i su ices o show ha
k
i12n2
:
This is ce ainly ue as ki1k ˛n1=8 > n4= , ecalling ha 4= D4 om
(2.2). This shows ha (i ) holds o all iand concludes he p oo o he claim and hence
he p oo o Theo em 1.4.
We ema k ha his p oo scheme builds on ha o Nenado [61] (which in u n is
in luenced by ha o K i ele ich [51]), who p o ed ha ˇ"p2n=log nsu ices o
a iangle ac o in an n- e ex .p; ˇ/-bijumbled g aph. Indeed, Nenado also uses a
esul akin o Lemma 2.4, albei be ween o cha ds whose o de s only di e by a con-
s an ac o . His abso bing s uc u e hen con ains a sequence o ‚.log n/ o cha ds whose
o de inc eases by a cons an ac o along he sequence. The e o e he las o cha d in he
sequence con ains cons an ly many diamond ees o la ge o de (o o de ‚.n=log n/).
These can be ully abso bed because any h ee la ge se s hos a ans e sal iangle and so
ans e sal iangles be ween emo able se s can be g eedily ound, comple ing a iangle
ac o in he las s ep. Simila ly, he .k;m/3-o cha ds used in his a gumen a e no imposed
o be sh inkable bu can be seen o hos a iangle ac o on all bu o.k/ o he diamond
ees by again applying a g eedy app oach o inding ans e sal iangles. The necessi y
o he log nin he condi ion o Nenado is hus due o needing ‚.log n/ o cha ds in he
abso bing s uc u e and hus equi ing sligh ly s onge p ope ies o he .p;ˇ/-bijumbled
g aph, o example he exis ence o iangles on se s o .n=log n/ e ices.
The key challenge in his pape is hen o p o e P oposi ions 2.8 and 2.9. Bo h esul s
ely hea ily on a echnique we de elop o p o ide he exis ence o K -diamond ees in
which we ha e some con ol o e he se o emo able e ices. This con ol is a he
weak; we canno gua an ee ha any ixed e ices appea as emo able e ices bu we
can gi e some lexibili y o e he choice o emo able e ices. See P oposi ion 4.1 o
he echnical s a emen o wha we p o e.
In o de o p o e P oposi ion 2.8, we build on he app oach o Han, Kohayakawa and
Pe son [34,35]. Indeed, hei esul showing he exis ence o a nea K - ac o (co e ing
all bu some n1"0 e ices) in .n; d; /-g aphs can be seen as a s ep owa ds p o ing
he exis ence o sh inkable o cha ds o o de 1. The app oach in ol es showing he exis-
ence o a nea -pe ec ma ching in a subhype g aph H0o he K -hype g aph gene a ed
by V.G/. In o de o do his, one needs o ca e ully choose H0and his is done by inding

Clique ac o s in pseudo andom g aphs 817
many ac ional K - ac o s in Gwhich do no pu oo much weigh on (copies o K con-
aining) any gi en edge. The e o e, he me hods o K i ele ich, Sudako and Szabó [54],
who p o ed he exis ence o singula ac ional K - ac o s, become pe inen . They use
he powe o linea p og amming duali y o p o e ha ce ain expansion p ope ies gua -
an ee he exis ence o ac ional ac o s. In ou se ing, i u ns ou ha we need se e al
dis inc a gumen s o p o e he exis ence o sh inkable o cha ds o di e en o de s. We
ollow he scheme o using ac ional ac o s (in ac , ac ional pe ec ma chings in K -
hype g aphs) bu need o adap he me hod o di e en applica ions and we ely c ucially
on p obabilis ic me hods o ac ually p o e he exis ence o o cha ds which sa is y he
necessa y expansion p ope ies.
I can be seen ha P oposi ion 2.8 alone ( o all o de s o o cha ds) would lead ia
he same p oo scheme o a condi ion o ˇ"p 1n=.log log n/. In o de o close he
gap and achie e Theo em 1.4, P oposi ion 2.9 is necessa y. To p o e his, we appeal
o a di e en abso p ion a gumen whose oo s go back o an ingenious a gumen o
Mon gome y [57,58] in his wo k on spanning ees in andom g aphs. The app oach,
some imes called he abso p ion- ese oi me hod, uses a bipa i e g aph, which we call
a empla e (see Sec ion 3.6) as an auxilia y g aph o de ine an abso bing s uc u e. This
idea was p e iously used by Han, Kohayakawa, Pe son and he au ho [32] o ind clique
ac o s in pseudo andom g aphs, and we used his app oach again in ou esul on 2-
uni e sali y [33]. He e we combine his idea wi h he abso bing powe o o cha ds and
p o e P oposi ion 2.9 wi h a h ee-s age algo i hm which inds he abso bing s uc u e
necessa y.
The es o his pape is o ganised as ollows. In he nex sec ion, we un h ough
he necessa y p elimina ies, p o iding he backg ound heo y ha we will use. This
includes p ope ies o bijumbled g aphs, he s udy o pe ec ac ional ma chings ia
linea p og ams, p obabilis ic me hods and he abso p ion- ese oi me hod o Mon -
gome y [57,58]. In Sec ion 4we hen s udy wha kinds o diamond ees we can gua an ee
in ou bijumbled g aph. The key esul he e is P oposi ion 4.1, which will be c ucial a
a ious poin s in ou p oo . We hen u n o add essing he necessa y esul s o he cas-
cading abso p ion h ough he o cha ds in Sec ion 5. We p o e Lemma 2.4 in Sec ion 5.1
and discuss P oposi ion 2.8 in Sec ion 5.2, educing i o wo in e media e p oposi ions
which ackle small and la ge o de sh inkable o cha ds sepa a ely. We go on o p o e
he exis ence o sh inkable o cha ds o small o de in Sec ion 6and la ge o de in Sec-
ion 7. Finally, we p o e P oposi ion 2.9 which p o ides he inal abso p ion in he p oo
o Theo em 1.4, in Sec ion 8.
3. P elimina ies
3.1. No a ion
Fo a g aph Gand 2N, we de ine K .G/ o be he se o copies o K in G. When
e e ing o (a copy o ) a clique S2K .G/, we will iden i y he copy wi h he se
o e ices ha hos s i . Tha is, we hink o S2K .G/ as a se o e ices which
P. Mo is 818
hos a clique in G a he han he copy o he clique i sel . Gi en a se †K .G/
o -cliques, we use he no a ion V.†/ o deno e all e ices ha ea u e in cliques
in †, i.e. V.†/ WD SS2†S. We call †K .G/ ama ching o cliques i i is com-
posed o pai wise e ex disjoin cliques, ha is, S S0D ; o any S¤S02†. Now
gi en subse s S; W V.G/ o e ices, we le NG
W.S/ deno e he common neighbou s
o he e ices in Swhich lie in W. Tha is, NG
W.S/ WD .T 2SNG. // W. Like-
wise, we de ine degG
W.S/ WD jNG
W.S/j o be he ca dinali y o his neighbou hood. I
he g aph Gis clea om con ex hen we d op he supe sc ip s. Also i SD ¹uºis
a single e ex, we will d op he se b acke s. We say ha a clique S2K .G/ a-
e ses e ex subse s U1; : : : ; U V .G/ i he e exis s some o de ing o Sas SD
¹u1; : : : ; u ºsuch ha ui2Ui o all i2Œ . No e ha when he Uia e pai wise disjoin ,
his simpli ies o equi ing ha Scon ains one e ex om each Ui. Howe e , a imes
we will deal wi h no necessa ily disjoin se s Uiand so his mo e delica e de ini ion is
needed.
I His an -uni o m hype g aph o some 2Nand ; u 2V.H /, hen degH. /
deno es he numbe o edges in Hcon aining , and codegH.u; / deno es he numbe
o edges o Hwhich con ain bo h uand . I he hype g aph His clea om con ex , we
d op he supe sc ip s. I His an -uni o m hype g aph wi h 3and Jis a 2-uni o m
g aph on he same e ex se V.H/, hen HJdeno es he subhype g aph o Hgi en by
all edges o H ha con ain some edge o J.
Fo g aphs Q
Gand Gon he same e ex se wi h Q
Ga subg aph o G, we le GnQ
G
deno e he g aph on V.G/ gi en by he se o edges ha ea u e in Gbu no in Q
G. I
H0and Ha e -uni o m hype g aphs wi h H0a subg aph o H, hen HnH0is de ined
simila ly.
We use xDy˙z o deno e ha xyCzand xyz, and we say a p ope y
holds wi h high p obabili y (whp, o sho ) i he p obabili y ha i holds ends o 1 wi h
some pa ame e n(usually he numbe o e ices o a g aph). Finally, we d op ceilings
and loo s unless necessa y, so as no o clu e he a gumen s.
3.2. P ope ies o bijumbled g aphs
He e we collec some p ope ies o bijumbled g aphs. These ange om simple conse-
quences o De ini ion 1.3 o mo e in ol ed s a emen s ca e ed o ou pu poses. We begin
by showing ha we can assume ha he g aphs we conside ha e an a bi a ily la ge num-
be o e ices.
Fac 3.1. Gi en any 2N3and n02N, he e exis s " > 0 such ha any n- e ex .p;ˇ/-
bijumbled g aph Gwi h n2 N,p > 0,ı.G/ < .1 1= /n and ˇ"p 1nmus ha e
nn0.
P oo . Le " > 0 be such ha " < 1=.2n0 /. Suppose o a con adic ion ha he e exis s
an n- e ex .p; ˇ/-bijumbled g aph wi h ı.G/ < .1 1= /n,ˇ"p 1nand n < n0.
Then due o he uppe bound on he minimum deg ee o G, he e exis s a e ex u2V.G/
Clique ac o s in pseudo andom g aphs 819
and a se W2V.G/ n¹uºsuch ha jWj D n= and degG
W.u/ D0. Howe e , om De i-
ni ion 1.3, we ha e
e.¹uº; W / pjWj"p 1n n
pn
.1 "pn / pn
2 > 0;
a con adic ion.
Fac 3.1 shows ha by choosing ">0su icien ly small, we gua an ee ha any
bijumbled g aph Gwe a e in e es ed in ei he has a la ge numbe o e ices o has
ı.G/ .1 1= /n, in which case Theo em 1.1 implies he exis ence o a K - ac o and
we a e done. We will use his a a ious poin s in ou a gumen and simply s a e ha we
choose ">0su icien ly small o o ce n o be su icien ly la ge.
The ollowing well known ac s a es ha bijumbled g aphs canno o be oo spa se.
Fac 3.2. Fo any 2N3and any C > 0, he e exis s an " > 0 such ha i Gis an
n- e ex .p; ˇ/-bijumbled g aph wi h p > 0 and ˇ"p 1n, hen pC n1=.2 3/
C n1=3.
P oo . Le " > 0 be such ha "21=.32C 2 3/and small enough ha we can assume
ha
(i) n9;
(ii) p1=16.
Indeed, om Fac 3.1, we can choose "so ha (i) holds and C n1=.2 3/ < 1=16 and so
we a e done i we a e no in case (ii). We will also es ic o he case ha
(iii) p1=.2n/.
To see ha we can do his, suppose o a con adic ion ha he e exis s a .p; ˇ/-bijumbled
g aph GD.V; E/ wi h pn < 1=2. We appeal o De ini ion 1.3 and uppe bound 2e.G/ D
e.V; V / by pn2C"p 1n2< n 1. Hence he e mus be some e ex u2Vwhich is
isola ed in G. Bu hen de ining WWD Vn¹uº, he lowe bound o De ini ion 1.3 gi es
e.¹uº; W / p.n 1/ "p 1npn1pn.1=2 "pn/ > 0, a con adic ion.
We now u n o p o ing he s a emen in ull gene ali y. Ou aim is o cons uc la ge
(disjoin ) e ex subse s Uand Wsuch ha e.U; W / D0. We do his in he ollowing
g eedy ashion. We ini ia e he p ocess by se ing UD ; and WDV.G/. Now, whils
jWj3n=4, he e exis s some u2Wwi h degW.u/ 2pjWj2pn. Indeed, his ollows
om De ini ion 1.3 because
X
w2W
degW.w/ De.W; W / pjWj2C"p 1jWj  2pjWj2:
We hen choose such a u, dele e i om Wand add i o Uand also emo e NW.u/
om W.
Le Uand Wbe he esul ing se s a e his p ocess e mina es. I is clea ha e.U;W /
D0as we ha e emo ed all he neighbou s o each e ex u2U om Wdu ing he
p ocess. We also claim ha jWjn=2 and U1=.16p/. Indeed, he las s ep emo ed a
P. Mo is 820
mos 1C2pn e ices om W. Due o ou assump ions (i) and (ii), we see ha 1C2pn <
n=4 and so as Whad size g ea e han 3n=4 be o e his s ep, we indeed ha e jWj  n=2
as he p ocess e mina es. To see he lowe bound on he size o U, no e ha i his was
no he case, hen
jV.G/ nWj D ˇˇˇ[
u2U
.¹uº[NG.u//ˇˇˇX
u2Uj¹uº[NG.u/jjUj.1 C2pn/
1
16p Cn
8n
4;
using assump ion (iii) in he las inequali y. This implies ha jWj3n=4, a con adic ion
as he p ocess e mina ed.
Thus jWj  n=2,jUj  1=.16p/ and om De ini ion 1.3, we ha e
0De.U; W / pjUjjWj"p 1npjUjjWj;
implying ha p2 31=.32"2n/. Gi en ou uppe bound on ", his implies ha p
C n1=.2 3/ as equi ed.
Ou i s lemma shows ha ew e ices ha e deg ee much smalle o much la ge han
expec ed wi h espec o a gi en se .
Lemma 3.3. Fo any 2N3and >0 he e exis s an ">0such ha i Gis an n- e ex
.p; ˇ/-bijumbled g aph wi h ˇ"p 1n hen o WV .G/:
(i) The numbe o e ices 2V.G/ such ha degW. / < pjWj=2 is less han
p2 4n2
jWj:
(ii) Fo any qsuch ha 2p q1, he numbe o e ices 2V.G/ such ha degW. /
> qjWjis less han
p2 2n2
q2jWj:
P oo . Fix ">0such ha 4"2< . We p o e only (ii); he p oo o (i) is bo h simila and
simple . We se B o be he se o ‘bad’ e ices, i.e. e ices such ha degW. / > qjWj.
Thus we ha e
qjBjjWj< e.B; W / pjBjjWjC"p 1npjBjjWj;
using he de ini ion o Band (1.2). Rea anging gi es
jBj<"2p2 2n2
.q p/2jWj;
and using pq=2 gi es he desi ed conclusion wi h ou choice o ".
Nex , we s a e some u he consequences o De ini ion 1.3, showing ha we can ind
cliques a e sing la ge enough subse s o e ices. The ollowing lemma is e y gene al
Clique ac o s in pseudo andom g aphs 821
and will be used a a ious poin s in ou a gumen . Due o i s gene ali y, he e a e some
echnical ea u es. Whils hese a e all necessa y o ce ain pa s o ou a gumen , we
do no need all o hese a once. In ac , o easy e e ence, we lis he consequences o
Lemma 3.4 ha we will use in Co olla y 3.5. This may also se e o diges he s a emen
o Lemma 3.4, seeing how i is applied in p ac ice.
Lemma 3.4. Fo any 2N3and 0 < ˛ < 1=22 he e exis s an " > 0 such ha he
ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n. Suppose
ha he e a e in ege s xi,i2Œ C1, such ha x1x C10and o some 2Œ ,
one has
xiCxiC1C2i 2 2 o all 1i .(3.1)
De ine yWDmax ¹xiC1CiWi2Œ º. Then o any collec ion o subse s UiV .G/ such
ha jUij  ˛pxin o all i2Œ C1 and o any subg aph Q
Go Gwi h maximum deg ee
less han ˛2pyn, de ining G0WD GnQ
G, he e exis s a clique S2K .G0/ a e sing
U1; : : : ; U such ha
degG0
Uj.S/ ˛p jUjj o C1j C1.
P oo . Fix " > 0 small enough o apply Lemma 3.3 (i) wi h WD ˛2=.24 /. Fu he ,
ix yand Q
Gas in he s a emen , se ing G0WD GnQ
G. We will p o e induc i ely ha
o iD1; : : : ; , he e exis s an i-clique Si2Ki.G0/ a e sing U1; : : : ; Uisuch ha
degG0
Uj.Si/.p=4/ijUjj o all jwi h iC1j C1. No e ha S is he desi ed
copy o K in he s a emen , using ˛1=4 he e.
So ix some i2Œ . I i2, by induc ion we deduce he exis ence o Si1as claimed
and o ij C1, de ine WjUjso ha WjWD NG0
Uj.Si/. I iD1, we simply se
WjWD Uj o all j. We hus ha e
jWjj  p
4i1
jUjj  ˛41ipxjCi1n(3.2)
o ij C1. Now we appeal o Lemma 3.3 (i) and conclude ha o each jwi h
iC1j C1, he e is some se BjV.G/ such ha degG
Wj. / pjWjj=2 o all
2V.G/ nBjand
jBjj  p2 4n2
jWjj4i1p2 3ixjn
˛˛p2 3ixiC1n
4i ˛pxiCi1n
4i jWij
2 :
(3.3)
He e, we used (3.2) in he second inequali y, he de ini ion o and he ac he xj
xiC1in he hi d, (3.1) in he ou h and (3.2) once again in he inal inequali y. We can
hus conclude om (3.3) ha he e exis s a e ex wi2Wisuch ha wi…Bj o all
iC1j 1. We claim ha choosing SiDSi1[¹wiºcomple es he induc i e
s ep. Indeed, Si2Ki.G0/as wiwas chosen om he common neighbou hood o Si1in
G0. Also, ixing some iC1j 1, we see ha NG.wi/in e sec s WjDNG0
Uj.Si1/
in a leas pjWjj=2 e ices. Fu he mo e, a mos
˛2pyn˛2pxiC1Cin˛
22 pxjCinpjWjj=4

P. Mo is 822
edges adjacen o wilie in Q
G, using he de ini ion o y, he uppe bound on ˛, he ac
ha xjxiC1and (3.2). The e o e we can conclude ha o all iC1j , we
ha e degG0
Uj.Si/degG0
Wj.Si/pjWjj=4 .p=4/ijUjj, as equi ed. This comple es he
induc ion and he p oo .
We now collec some easy consequences o Lemma 3.4 o e e ence la e in he p oo .
Co olla y 3.5. Fo any 2N3and 0 < ˛ < 1=22 he e exis s an ">0such ha he
ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n:
(1) Le Q
Gbe any subg aph Q
Go Gwi h maximum deg ee less han ˛2p 1n.
(i) Fo any U1; : : : ; U 1V .G/ such ha jUij  ˛pn o i2Œ 1, he e exis s
an . 1/-clique S2K 1.G nQ
G/ a e sing he Ui.
(ii) Fo any U1; : : : ; U V .G/ such ha jU1j  ˛p2 4nand jUij  ˛n o 2
i , he e exis s an -clique S2K .G nQ
G/ a e sing he Ui.
(2) Fo any U1; : : : ; U V .G/ such ha jU1j  ˛p 1n,jUij  ˛pn o 2i 2
and jU 1j;jU j  ˛n, he e exis s an -clique S2K .G/, a e sing he Ui.
(3) Fo any W0; W1; W2V .G/ such ha jW0j;jW1j;jW2j  ˛n, he e exis s an S2
K 1.GŒW0/ such ha degWi.S/ ˛2p 1n o jD1; 2.
P oo . Fix " > 0 small enough o apply Lemma 3.4. This is p edominan ly a case o plug-
ging in he alues and checking he condi ions o Lemma 3.4. Fo pa (1), we le G0D
GnQ
G. Then o (1)(i), we ake D 2,xiD1 o 1i C1and yD 1. We
hus see ha o i2Œ ,xiCxiC1C2i D2C2i 2 2and xiC1CiD1Ci 1
Dy. The e o e aking Ui o 1i 1wi h jUij˛pn (and de ining U C1DU D
U 1), Lemma 3.4 gi es us an . 2/-clique S02K 1.G0/ a e sing U1; : : : ; U 2
such ha degG0
U 1.S0/˛2p 1n > 0 (he e Fac 3.2 shows posi i i y). The e o e choos-
ing any e ex 2NG0
U 1.S0/and ixing SDS0[¹ ºgi es he equi ed clique.
The o he cases a e simila . Fo pa (1)(ii), we ix D 1,x1D2 4,xiD0 o
2i C1and yD 1. Again, i is easily checked ha he condi ions on he xia e all
sa is ied and so applying Lemma 3.4 ( ixing U C1DU ) gi es an . 1/-clique S0in G0
a e sing U1; : : : ; U 1such ha S0has a nonemp y G0-neighbou hood in U . The e o e
adding any e ex in his neighbou hood o S0gi es he equi ed -clique S2K .G0/.
Fo pa (2), we ix D 1,x1D 1,xiD1 o all isuch ha 2i 2
and x 1Dx Dx C1D0. We also le Q
Gbe he emp y g aph and so GDG0. Now no e
ha o D3, we ha e x1D2and x2D0and so x1Cx2C2D4D2 2, whils o
4, we ha e x1Cx2C2D C22 2. Condi ions (3.1) o 2i D 1
can be simila ly checked. The e o e Lemma 3.4 gi es an . 1/-clique S02K 1.G/
a e sing U1; : : : ; U 1such ha NG
U .S0/¤ ; and so as abo e, we ex end S0 o he
equi ed -clique S.
Finally, o pa (3) we ix D 1,xiD0 o all 1i and de ine ou
se s as UiDW0 o i2Œ 1 and U DW1,U C1DW2. Applying Lemma 3.4 hen
di ec ly gi es he equi ed . 1/-clique S2K 1.GŒW0/ (again he e Q
Gis aken o be
emp y).
Clique ac o s in pseudo andom g aphs 823
3.3. Concen a ion o andom a iables
We will use he ollowing well-known concen a ion bounds (see e.g. [38, Theo em 2.1,
Co olla y 2.4 and Theo em 2.8]).
Theo em 3.6 (Che no bounds). Le Xbe he sum o a se o mu ually independen
Be noulli andom a iables and le DEŒX. Then o any 0 < ı < 3=2, we ha e
PŒX .1 Cı/ eı2=3 and PŒX .1 ı/ eı2=2:
Fu he mo e, i x7, hen PŒX x ex.
3.4. Pe ec ac ional ma chings
Gi en an -uni o m hype g aph H, a ac ional ma ching in His a unc ion W
E.H/ !R0such ha PeW 2e .e/ 1 o all 2V .H/. We say he ac ional ma ch-
ing is pe ec i PeW 2e .e/ D1 o all 2V .H/. The alue o a ac ional ma ching
is j j WD Pe2E.H / .e/: The maximum alue j jo e all choices o ac ional ma ch-
ing o H, we call he ac ional ma ching numbe o H, which we deno e by .H /.
A ac ional co e o His a unc ion gWV.H / !R0such ha o all e2E.H /,
one has P 2eg. / 1. The alue o a ac ional co e gis jgj WD P 2V.H / g. /. The
ac ional co e numbe o H, deno ed .H/, is hen he minimum alue o a ac ional
co e go H.
Fo an -uni o m hype g aph H, he ac ional ma ching numbe o Hcan be encoded
as he op imal solu ion o a linea p og am. Taking he dual o his linea p og am gi es
ano he linea p og am which ou pu s he ac ional co e numbe as an op imal solu ion.
The duali y heo em om linea p og amming hus ells us ha .H/ D.H / o any
hype g aph H. Using his, as well as he so called ‘complemen a y slackness condi ions’
ha ollow om he duali y heo em, one can de i e he ollowing simple consequences
(see e.g. [50, P oposi ion 2] o [35, P oposi ion 2.4]).
P oposi ion 3.7. Fo any -uni o m hype g aph Hon N e ices, he ollowing hold:
(1) .H/ N= , wi h equali y i and only i he e exis s a pe ec ac ional ma ching
in H.
(2) .H/ .H/ whe e .H/ deno es he size o he la ges ma ching in H.
(3) I gWV.H/ !R0is a ac ional co e and UV.H /, hen g0WDgjUWU!R0is
a ac ional co e o HŒU  and hence jg0jDPu2Ug.u/ .H ŒU / D.HŒU /.
(4) I gWV.H/ !R0is an op imal ac ional co e , i.e. jgj D .H/, hen .H/ 
jWj= whe e WWD ¹ 2V .H/ Wg. / > 0º.
We now gi e wo lemmas, explo ing some simple condi ions which gua an ee he
exis ence o a pe ec ac ional ma ching.
Lemma 3.8. Suppose His an N- e ex, -uni o m hype g aph such ha gi en any e ex
2V.H/ and any subse WV.H/ n ¹ ºo a leas N=.2 / e ices, he e exis s
P. Mo is 824
an edge in Hcon aining and 1 e ices o W. Then Hhas a pe ec ac ional
ma ching.
P oo . Suppose o a con adic ion ha Hdoes no ha e a pe ec ac ional ma ching.
Thus, by P oposi ion 3.7 (1), i we ake gWV.H/ !R0 o be an op imal ac ional co e
o Hso ha jgj D .H/ D.H / we ha e jgj< N= . Hence, i we o de he e ices
in dec easing weigh o de acco ding o g, we see by P oposi ion 3.7 (4) ha g.w/ D0,
whe e wis he inal e ex in his o de . Take WV.H/ n¹wº o be he se o N=.2 /
e ices p eceding win he o de . Then by he condi ion o he lemma, he e exis s an
edge using wand 1 e ices o W. Since g.w/ D0, he e is some e ex w0in W
wi h g.w0/1=. 1/. The e o e all e ices p eceding Win he o de (as well as w0)
ha e a leas his weigh and in o al
jgj  NN=
1N= ;
a con adic ion.
Gi en a e ex subse UVWDV.H / in a hype g aph H, a an ocused a Uin His a
subse FE.H/ o edges o Hsuch ha je UjD1 o all e2Fand e e0 .V nU /
D; o all e¤e02F. In wo ds, each edge o a an in e sec s Uin exac ly one e ex and
ou side o U, he edges in a an a e pai wise disjoin . The size o a an is simply he num-
be o edges in he an. I UD¹uºis a single e ex, we simply e e o a an ocused a u.
Lemma 3.8 shows ha i Hhas he p ope y ha he link o e e y e ex has no
la ge independen se s, hen i mus ha e a pe ec ac ional ma ching. In ac , we do
no necessa ily need such an expansion p ope y o hold locally a e e y e ex and can
ins ead ocus on subse s o e ices, i we ha e an added condi ion ha e e y e ex has a
la ge enough an ocused a i . This is he con en o he ollowing lemma.
Lemma 3.9. Suppose His an N- e ex, -uni o m hype g aph and he e exis s M
N=.2 / such ha
(i) o all 2V.H/ he e is a an ocused a in Ho size M;
(ii) o e e y subse W0V.G/ wi h jW0j D Mand e e y subse W1V.G/ nW0wi h
jW1j  N=.2 /, he e exis s an edge o Hwi h one e ex in W0and he o he 1
e ices in W1.
Then Hhas a pe ec ac ional ma ching.
P oo . We s a by no icing ha (ii) leads o he ollowing wo consequences:
(a) Fo all UV.H/ wi h jUjD. 1/M , ixing V0WDV .H/ nUwe ind ha o all
U0V0such ha jU0jDM, he e is a an o size N= M ocused a U0in H ŒV 0.
(b) E e y subse o a leas N= e ices o Hinduces an edge in H.
Indeed, o U0as in (a) we can build he an FU0 ocused a U0g eedily. Whils jFU0j 
N= M, we see ha WWD V .G/ n.V .FU0/[U0[U / has size a leas
N.N= M /. 1/ M. 1/M N.2 1/N=.2 / N=.2 /;
Clique ac o s in pseudo andom g aphs 825
using MN=.2 / he e. Hence we can ind an edge using one e ex o U0and 1
e ices o Wwhich ex ends he an FU0. Condi ion (b) also ollows easily because ak-
ing W0 o be a se wi h N= e ices, we ind ha o any W00 W0wi h jW00j D M,
he e is an edge con aining a e ex in W00 and 1 e ices o W0nW00 om (ii).
Now we u n o he main p oo . We ix gWV.H / !R0 o be an op imal ac ional
co e and suppose o a con adic ion ha jgj< N= . We deduce he exis ence o a e ex
w2V.H/ wi h g.w/ D0and a an Fw ocused a wo size M. Taking U1WDS¹en¹wºW
e2Fwº, we ha e jU1j D . 1/M and Pu2U1g.u/ M.
Now conside V0WD V.H / nU1. I .HŒV 0/ N= M hen we can conclude
ha P 2V0g. / N= M om P oposi ion 3.7 (3), which implies ha jgj  N= ,
a con adic ion. Hence
.HŒV 0/ < N
MDN0M
;(3.4)
whe e N0WDjV0jDN. 1/M . We ix g0WV0!R0 o be some op imal ac ional
co e o HŒV 0wi h jg0j D .HŒV 0/. By P oposi ion 3.7 (4), we he e o e deduce ha
he e is some se U2V0wi h jU2jDMand g0.u0/D0 o all u02U2. By (a) he e exis s
a an FU2o size N= M ocused a U2in HŒV 0. Taking ZWD S¹eWe2FU2ºnU2,
we ha e jZj D . 1/.N= M / and simila ly o be o e, using he ac ha o each
edge e2FU2we ha e P 2eg0. / 1and g0.u0/D0 o all u02U2, we can conclude
ha Pz2Zg0.z/  jFU2j D N= M.
Finally, we look a V00 WD V0nZ. We ha e N00 WD jV00j D N0. 1/.N= / C
. 1/M and using (b) and P oposi ion 3.7 (2), we ind ha
.HŒV 00/ N00 N=
DN0C. 1/M
N
:
Hence, by P oposi ion 3.7 (3), we deduce ha P 002V00 g0. 00/.N 0C. 1/M /=
N= . Combining his wi h he lowe bound on he sum o g0 alues on Zimplies ha
jg0j D .HŒV 0/ .N 0M /= , con adic ing (3.4).
3.5. Almos pe ec ma chings in hype g aphs
I is well known ha hype g aphs ha ha e oughly egula e ex deg ees and small
codeg ees con ain la ge ma chings. This is o en e e ed o as Pippenge ’s Theo em bu
he e a e in ac a amily o simila esul s, all ollowing om he “semi- andom” o
“nibble” me hod (see e.g. [10, Sec ion 4.7]). He e we use he ollowing explici e sion
which ollows di ec ly om a esul o Kos ochka and Rödl [49].
Theo em 3.10. Fo any in ege s 3and K4 he e exis s 0> 0 such ha o all
0 he ollowing holds. I His a -uni o m hype g aph on N e ices such ha
(1) o all e ices 2V.H/, we ha e deg. / D.1 ˙Kp.log /=/;
(2) o all u¤ 2V.H/, we ha e codeg.u; / 1=.2 1/,
hen Hhas a ma ching co e ing all bu a mos 1= N e ices.
P. Mo is 832
iD0; 1. Indeed, we can ind Mg eedily by applying Co olla y 3.5 (3) (wi h WiDU2i
o iD0; 1; 2) epea edly, adding an . 1/-clique S o Mand emo ing i s e ices
om U2a e each applica ion. While jMj  ˛n, we ha e jU2j  ˛n and so we a e
indeed in a posi ion o apply Co olla y 3.5 (3) h oughou he p ocess.
Now once we ha e ound M, o each S2Mand o iD0; 1, le Ni.S/ WDNUi.S/,
ha is, he se o e ices in Uiwhich o m a K wi h S. By cons uc ion we ha e
jN0.S/j  d o each Sin Mand so
j¹. ; S/ 2U0MW 2N0.S/ºj  jMjdD˛nd:
Hence, as jU0jhas size ˛n (as we imposed a he s a o he p oo ), by a e aging, he e
exis s a e ex 02U0and a subse †o dcliques in Msuch ha 0is in N0.S/ o
all S2†. We can now cons uc ou diamond s a g eedily, wi h 0as he image o he
la ge deg ee e ex. Sequen ially, o each clique Sin †, choose a e ex uin N1.S/
which has no been p e iously chosen and add he copy o K
C1on S, 0and u o he
diamond s a (adding u o R). As N1.S/ d o all S2†M, he e is always an
op ion o uand so his p ocess succeeds in building he equi ed diamond s a .
Ou nex lemma ollows he scheme o K i ele ich [51] o cons uc la ge diamond
ees. We adap his p oo o gua an ee ha he diamond ee ob ained is sca e ed.
Lemma 4.5. Fo any 2N3and 0 < ˛ < 1=22 he e exis s an " > 0 such ha he
ollowing holds o any n- e ex .p;ˇ/-bijumbled g aph Gwi h ˇ"p 1n, ixing dWD
˛2p 1n. Fo any 2z˛n and any pai o disjoin e ex subse s U; W V.G/ such
ha jUj;jWj  4˛ n, he e exis s a d-sca e ed K -diamond ee Dsc D.Tsc; Rsc; †sc/
o o de msuch ha zmzCd,Rsc Uand †sc K 1.GŒW / is a ma ching o
. 1/-cliques in GŒW .
P oo . Ou p oo is algo i hmic and wo ks by building a diamond ee o es , ha is, a se
o pai wise e ex disjoin diamond ees. A each s ep o he algo i hm, we will add o
one o he ees in ou o es , boos ing he deg ee o a e ex in he unde lying auxilia y
ee by d, using Lemma 4.4. By disca ding ees when he sum o he o de s o he ees
ge s oo la ge, we will show ha one o he ees in ou o es will e en ually ob ain he
desi ed o de a e ini ely many s eps o he algo i hm. The de ails ollow.
Ini ia e he p ocess by ixing U0U o be an a bi a y subse o ˛n e ices, W0D
;W o be emp y and D1;: : :;D`wi h `D˛n o be he diamond ees which a e de ined
o be he single e ices in U0. Tha is, o i2Œ`, he K -diamond ee DiD.Ti; Ri; †i/
co esponds o an auxilia y ee Tiwhich is jus a single e ex and hus Riis also a
single e ex and †iis emp y. In gene al, a each s ep o he p ocess we will ha e a
amily D1; : : : ; D`( o some `2N) o e ex disjoin K -diamond ees such ha o
each i, he diamond ee DiD.Ti;Ri; †i/is d-sca e ed, has RiU0and †iGŒW0.
Fu he mo e, we will ha e U0DSi2Œ` Riand W0DSi2`V.†i/Wand main ain
h oughou ˛n  jU0j  2˛n and jW0j  2. 1/˛n.
Now a each s ep, gi en such a se U0and amily D1; : : : ; D`, we apply Lemma 4.4
wi h U1DUnU0and U2DWnW0, no ing ha he condi ions on he size o Uand Win

Clique ac o s in pseudo andom g aphs 833
he s a emen o he lemma and he imposed condi ions on he size o U0and W0 h ough-
ou he p ocess indeed allow Lemma 4.4 o be applied. Thus, we ind a K -diamond
s a DD.T ; R; †/o o de dC1wi h cen e 02U0,Rn¹ 0º  UnU0and
†K 1.GŒU2/ a ma ching o . 1/-cliques. As U0is he union o he emo able
e ices o he amily o diamond ees, he e is some i02Œ` such ha 02Ri0. We
hen upda e Di0by adjoining he diamond s a o he ee a 0, we add all he e ices
o R o U0, and all he e ices o he . 1/-cliques in † o W0. Now i he e is a
K -diamond ee among he (new) amily D1; : : : ; D`which has o de a leas z, we ake
such a diamond ee as Dsc and inish he p ocess. I no , hen we look a he size o U0.
I jU0j< 2˛n, we con inue o he nex s ep. I jU0j  2˛n, hen we sequen ially disca d
a bi a y K -diamond ees DjD.Tj; Rj; †j/ om he amily. Tha is, we choose a Dj
in he amily, dele e Rj om U0and dele e he e ices ha belong o . 1/-cliques
in †j om W0. We con inue disca ding diamond ees un il jU0j  2˛n. No e ha as
jRjj  z˛n o all j, he upda ed U0a he end o his disca ding p ocess will ha e
size a leas ˛n as equi ed. We hen mo e o he nex s ep.
All he diamond ees in ou amily a e d-sca e ed h oughou he p ocess and also
W0, as he se o e ices ea u ing in in e io cliques o a amily o K -diamond ees
whose o de s add up o less han 2˛n, has size less han 2. 1/˛n h oughou . I is
also clea ha as he o de o any diamond ee in ou collec ion g ows by a mos d
in each s ep, he o de o he diamond ee which is ound by he algo i hm will be a
mos zCd. I only emains o check ha he algo i hm e mina es bu his is gua an eed
because he numbe o diamond ees is dec easing h oughou he p ocess. Indeed, we
ne e add new diamond ees o he amily and e e y ˛n=ds eps we ha e o disca d a
leas one diamond ee om he amily. I he algo i hm does no e mina e a e inding
an app op ia e Dsc, hen e en ually we will be le wi h jus one diamond ee D1in he
amily, bu a his poin he o de o D1would be a leas ˛n z, con adic ing ha he
algo i hm is s ill unning.
X={ }
Y={ }
XD
YD
Fig. 6. A6-sca e ed K3-diamond ee.
Using Lemmas 4.4 and 4.5 we can now deduce P oposi ion 4.1.
P. Mo is 834
P oo o P oposi ion 4.1.Fix " > 0 small enough o apply Lemmas 4.4 and 4.5 and small
enough o o ce n o be su icien ly la ge in wha ollows. Le us i s deal wi h he case
when zdWD˛2p 1n. He e, we a bi a ily pa i ion Uin o U0and U1o size a leas
˛n, ix U2DWand apply Lemma 4.4 o ge a K -diamond s a DD.T ; R; †/
o o de 1Cdwi h RUand †K 1.GŒW / a ma ching o . 1/-cliques
in W. Le x2Rbe he only non-lea e ex in Rand de ine XD ¹xº. Fu he , le
YRnXbe an a bi a y subse o z1 e ices. Now aking WV .T /!Rand
WE.T /!† o be he de ining bijec i e maps o D, no e ha o any Y0Y, he
se ¹1. / W 2Y0[Xº  V .T /spans a sub ee (o a he a subs a ) o T, say T.
The e o e, aking DD.T; X [Y0; †/ whe e †WD ¹.e/ We2E.T /ºde ines a K -
diamond ee wi h emo able e ices Y0[X. The e o e (1)–(3) o he p oposi ion a e all
sa is ied.
When d< z ˛n, he p oo is simila . We apply Lemma 4.5 o ge a d-sca e ed
K -diamond ee Dsc D.Tsc; Rsc; †sc/as gi en by he lemma and de ine XRsc o
be he non-lea es o Dsc. See Figu e 6 o an example. In o de o bound jXjand p o e
p ope y (2), we appeal o Lemma 4.3 which gi es
jXj  jRscj2
d1zCd2
d12z
d
;
using zdin he inal inequali y.
We no e ha o nla ge (using Fac 3.2) we ha e d4, implying ha jXjz=2. We
ix YRsc nX o be an a bi a y subse o size zjXjand claim ha condi ions (1)–(3)
o he p oposi ion a e all sa is ied. Indeed, i emains only o p o e (3) and his ollows
simila ly o abo e, by aking sub-diamond- ees o Dsc. In de ail, ix some Y0Yand le
RDY0[X. Then i sc WV.Tsc/!Rsc and sc WE.Tsc/!†sc a e he de ining bijec i e
maps o Dsc, hen he se ¹1
sc . / W 2Rºo e ices spans a sub ee TTsc. Indeed,
we simply dele ed lea es om Tsc, namely 1
sc .x/ o x2Rsc nY0. Taking †D¹sc.e/ W
e2E.T /º, we conclude ha DD.T; R; †/ is he desi ed diamond ee.
5. Cascading abso p ion h ough o cha ds
In his sec ion we discuss o cha ds in ou .p; ˇ/-bijumbled g aphs. We begin in Sec-
ion 5.1 by p o ing Lemma 2.4 which de ails condi ions o when one o cha d abso bs
ano he . In Sec ion 5.2, we hen discuss he exis ence o sh inkable o cha ds, add essing
P oposi ion 2.8 which ells us ha we can ind sh inkable o cha ds o all desi ed o de s
in he g aphs we a e in e es ed in. The p oo o P oposi ion 2.8 equi es many ideas and
wo dis inc app oaches. The e o e, we de e he majo i y o he wo k o la e sec ions and
simply educe he p oposi ion he e, spli ing i in o wo ‘subp oposi ions’ which will be
ackled sepa a ely. Recall ha Lemma 2.4 and P oposi ion 2.8 we e he wo ing edien s
we needed o p o e he cascading abso p ion h ough cons an ly many o cha ds in he
p oo o Theo em 1.4.
Clique ac o s in pseudo andom g aphs 835
5.1. Abso bing o cha ds
Recall he de ini ion (De ini ion 2.3) o an o cha d and ha we say a .K; M / -o cha d O
abso bs a.k; m/ -o cha d Ri he e is an .. 1/k; M / -subo cha d O0Osuch ha
he e is a K - ac o in GŒV.R/[V.O0/.
In his sec ion we p o e Lemma 2.4, es a ed below o con enience, which is a gene -
alisa ion o [61, Lemma 3.5]. The lemma gi es some su icien condi ions o an o cha d
o be able o abso b ano he o cha d.
Lemma 2.4 ( es a ed). Fo any 2N3and 0 < ;  < 1 he e exis s an ">0such ha
he ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n. Le O
be a .K; M / -o cha d in Gsuch ha KM n. Then he e exis s a se BV.G/ such
ha jBj  p2 4nand Oabso bs any .k; m/ -o cha d Rin Gwi h
V.R/ .B [V.O// D ;; k K=.8 / and kM mK: (5.1)
Ou p oo scheme ollows ha o [33] which gi es a polynomial ime wo-phase
algo i hm o inding he necessa y K - ac o . The algo i hm is a simple g eedy algo-
i hm and wo ks by abso bing each diamond ee Bin he small o cha d R, one a
a ime. In mo e de ail, o each diamond ee Bin R, we ind 1diamond ees
D1; : : : ; D 12Osuch ha he e is a copy o K a e sing he se s o emo able
e ices o Band he diamond ees D1; : : : ; D 1. This implies ha he e is a K - ac o
in GŒV .B/[V.D1/[[V.D 1/ (see Obse a ion 2.2) and so we can add he Di
o he subo cha d O0, o bid hem om being used again, and mo e o he nex diamond
ee B02R. No e ha ypically, we expec o succeed wi h his p ocess. Indeed, he se
o emo able e ices o diamond ees in Ois linea in size (and emains linea e en
a e o bidding diamond ees D2Oused o p e ious B2R) and so a ypical e ex
has .pn/ neighbou s among his se o emo able e ices. Hence, appealing o Co ol-
la y 3.5 (1)(i) which s a es ha se s o size .pn/ hos copies o K 1, we can expec
o ind a copy o K 1in he neighbou hood o a ypical emo able e ex o B2R
which lies on he emo able e ices o diamond ees in O. As long as his copy o K 1
a e ses se s o emo able e ices o dis inc diamond ees in O, we will succeed. Wi h
a ew ex a ideas and a bi o p ep ocessing ( o example pa i ioning Oin o 1sub-
o cha ds a he s a ), his in ui ion holds ue and we can success ully g eedily s a o
build O0.
In ac , i kM is small compa ed o pn, we can ully o m O0in his way and no
second phase is necessa y. Howe e , i kM is la ge compa ed o pn we may un in o
ouble as wi h his g eedy app oach, i may be he case ha he neighbou hood o a
emo able e ex o a diamond ee B2Rhas oo small a size by he ime we come o
conside ing B. Indeed, as we un his g eedy p ocess, we o bid he diamond ees (and
hei emo able e ices) which we add o O0 om being used again. This could esul
in ha ing much ewe han pn neighbou s in he emo able e ices o diamond ees
in ( he emainde o ) Oand so we ha e no gua an ee o inding a copy o K 1in his
neighbou hood.
P. Mo is 836
We esol e his issue by unning a wo-phase algo i hm and ese ing hal o O o
he second phase. The key poin is ha i a diamond ee B ails in he i s ound hen
i mus be he case ha all o he emo able e ices o Bha e small neighbou hoods
amongs he emo able e ices o diamond ees in O. Gi en ha h oughou he p o-
cess, many diamond ees in Owill emain a ailable o use, pseudo andomness (mo e
p ecisely, Co olla y 3.5 (1)(ii)) ells us ha he numbe o e ices ha do no ha e la ge
enough neighbou hoods is ela i ely small. Hence, as each diamond ee B2Rwhich
ailed in he i s phase has a se o emo able e ices which a e a ypical in his way, we
can uppe bound he numbe o diamond ees in R ha ail in he i s ound. This uppe
bound will hen be used o show ha in he second phase, we a e success ul wi h each
diamond ee, as h oughou he second ound, he numbe o emo able e ices being
o bidden (due o being used o abso b o he diamond ees in R) will be negligible and
so he neighbou hoods o e ices amongs he emo able e ices o diamond ees in he
hal o O ese ed o his second phase will emain la ge.
P oo o Lemma 2.4.We ix ˛; 0<2
23 2and choose " > 0 small enough o apply Lem-
ma 3.3 wi h 3.3 D0and Co olla y 3.5 wi h ˛3.5 D˛. Le OD ¹D1; : : : ; DKºbe he
.K; M / -o cha d wi h each DiD.Ti; Ri; †i/being a K -diamond ee o o de be ween
Mand 2M . We s a by a bi a ily pa i ioning Oin o 2. 1/ subo cha ds o size as
equal as possible so ha ODS2. 1/
jD1Ojand each Ojis a .Kj; M / -o cha d wi h
KjDK
2. 1/ ˙1K
2 . Fo j2Œ2. 1/, we le
YjWD [
iWDi2Oj
Ri
be he se o emo able e ices o he diamond ees which ea u e in he j h subo cha d.
No e ha jYjjKjMKM=.2 / n=.2 / o each j2Œ2. 1/. We de ine B o be
he se o e ices 2VnV .O/such ha o some j2Œ2. 1/, degYj. / < pjYjj=2.
By Lemma 3.3 (i), we ha e
jBj<2. 1/0p2 4n2
minjjYjjp2 4n;
due o ou lowe bound on he size o he jYjjand ou uppe bound on 0.
Now as in he s a emen o he lemma, conside a .k; m/ -o cha d RD¹B1; : : : ; Bkº
o diamond ees whose e ices lie in Vn.B [V.O//. Fo i02Œk, le Qi0be he se
o emo able e ices o he diamond ee Bi0. We will show ha o each i02Œk, he e
exis dis inc indices i1Di1.i0/; : : : ; i 1Di 1.i0/2ŒK such ha he e is a copy o K
which a e ses he se s Qi0and Ri1;: : :;Ri 1, whe e Ri1is he se o emo able e ices
o Di1and likewise o i2; : : : ; i 1. Now, om Obse a ion 2.2, o such an - uple Bi0,
Di1; : : : ; Di 1, he e is a K - ac o in GŒV .Bi0/[V.Di1/[[V.Di 1/. We will
p o e ha one can choose such indices i1; : : : ; i 1 o each i02Œk in such a way ha no
i2ŒK is chosen mo e han once. Tha is, o i0¤j02Œk, he se s ¹i1.i0/; : : : ; i 1.i0/º
and ¹i1.j 0/; : : : ; i 1.j 0/ºa e disjoin . The e o e ou subo cha d O0Ocan simply be
de ined o be he union o all he choices o Dij.i0/ o i02Œk and j2Œ 1.
Clique ac o s in pseudo andom g aphs 837
We now show how o ind he indices i1.i0/; : : : ; i 1.i0/ o each i02Œk. We will
achie e his ia he ollowing simple algo i hm. We ini ia e he i s ound o he algo i hm
wi h O0D ;,IDŒk,PjDOjand ZjDYj o 1j 1. No e ha he Oj o
j2. 1/ do no ea u e in hese de ini ions. This is because we will no use
any diamond ees ha lie in S2. 1/
jD Ojin his i s ound. Now he algo i hm uns as
ollows. Fo i0D1; : : : ; k; we check i he e exis s some se ¹Dij2PjWj2Œ 1º
such ha he e is a K a e sing Qi0and he se s o emo able e ices Ri1; : : : ; Ri 1.
I his is he case hen we dele e Dij om Pjand add i o O0 o j2Œ 1 and we also
dele e Rij om Zj o all j2Œ 1. Fu he mo e, we dele e i0 om Iand mo e o he
nex index i0C1(o inish his ound i i0Dk). I i is no he case ha such diamond
ees exis in he o cha ds Pj, hen we simply lea e i0as a membe o Iand mo e on o
he nex index.
A he end o he i s ound, we ha e some se Io indices emaining. We de ine
WD jIja his poin . We will now use diamond ees in he o cha ds Ojwi h j
2. 1/ o abso b hese emaining diamond ees Bi0wi h i02I. Thus we ese he
p ocess, se ing PjDOjC 1and ZjDYjC 1 o all j2Œ 1. We hen ollow
he same simple p ocess in he second ound as we did in he i s , unning h ough he
( emaining) i02Iin o de and ying o ind an app op ia e se ¹Dij2PjWj2Œ 1º
o diamond ees a each s ep. We claim ha in his second ound, we can ind such a se
o e e y i02Iand so by he end o he second ound, he se Iis emp y and O0is such
ha GŒV .R/[V.O0/ hos s a K - ac o .
In o de o p o e his, ou analysis spli s in o wo cases. Fi s conside when kM
<pn
16 . In his case, he second ound is no e en necessa y as all indices succeeded in
he i s ound. Indeed, no e ha e e y ime we a e success ul o an index i0, we dele e a
mos 2M e ices om each o he Zj. The e o e, a any ins ance in he i s ound o he
p ocess, any e ex which is no in Bhas
degZj. / pjYjj
22kM pn
4 2kM pn
8
o all j2Œ 1, using ou lowe bound on he jYjjand ou uppe bound on kM .
Bu hen, by Co olla y 3.5 (1)(i) (applied in his ins ance wi h Q
Gbeing he emp y g aph
and G0DG), he e exis s a copy o K 1 a e sing he se s NZj. / o 1j 1.
When is any e ex in he emo able se o e ices Qi0 o some diamond ee Bi0in he
p ocess, his gi es a copy o K a e sing Qi0and some se s o emo able e ices Rij
o diamond ees Dij2Pj,j2Œ 1, as desi ed. In his way, we see ha he p ocess
succeeds in e e y s ep o he i s ound o ind a sui able ¹ij.i0/Wj2Œ º o each i02Œk
and Iis emp y (i.e. D0) a he end o he ound. No e ha we ha e used he e he ac
ha he e ices o Qi0a e no in B.
When pn
16 kM mK, he second ound may be neccesa y and we s a wi h es i-
ma ing , he size o Ia e he i s ound. Now no e ha a he end o he i s ound,
be o e we eassign he se s Zj o emo able e ices in diamond ees in OjC 1 o
j2Œ 1, i we ake QDSi02IQi0, hen he e is no K a e sing Qand he se s
Z1; : : : ; Z 1. Indeed, o he wise he e would be an i02Iand a e ex 2Qi0Q

P. Mo is 838
which is con ained in a K wi h a se o e ices ¹ ij2ZjWj2Œ 1º. This con adic s
ha o he index i0we ailed o ind a sui able se o ijin he i s ound. Thus, a he end
o he i s ound, he e is no K a e sing Q, and he Zj,j2Œ 1. Mo eo e ,
jZjj  KM
2 2kM KM
4 n
4 ;
using he uppe bound on k om (5.1) and he ac ha a mos 2M e ices a e dele ed
om Zje e y ime we a e success ul wi h an index i02I. Thus, we can conclude om
Co olla y 3.5 (1)(ii) ha a he end o he i s ound, m < jQj< ˛p2 4n. The e o e
< ˛p2 4n
m˛p2n
m16˛ pK
16˛ pn
M pn
16 M ;
whe e we ha e used ou lowe and uppe bounds on kM o gi e an uppe bound on pn=m
in he hi d inequali y, he ac ha KM nin he ou h inequali y and ou uppe bound
on ˛in he inal inequali y.
We now u n o analyse he second ound. Using ou uppe bound on , we can uppe
bound he numbe o e ices dele ed in each Zj h oughou he second ound, and using
his we ind ha o any e ex no in B, any j2Œ 1 and a any poin in he second
ound,
degZj. / pjYjC 1j
22 M pn
4 pn
8 pn
8 :
Thus we can epea he a gumen used o he case when kM was small, seeing ha a
e e y s ep in he second ound we a e success ul in inding an app op ia e se o ij o
j2Œ 1 o each i02I. This comple es he p oo .
5.2. Sh inkable o cha ds
He e we a e conce ned wi h he exis ence o sh inkable o cha ds in pseudo andom g aphs
and e i ying P oposi ion 2.8, which we es a e below o he con enience o he eade .
We also encou age he eade o emind hemsel es o De ini ions 2.5 and 2.7 as well as
Obse a ion 2.6.
P oposi ion 2.8 ( es a ed). Fo any 2N3and 0 < ˛;  < 1=212 he e exis s an " > 0
such ha he ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n
and any e ex subse UV.G/ wi h jUjn=2. Fo any m2Nwi h 1mn7=8 he e
exis s a -sh inkable .k; m/ -o cha d Oin GŒU  wi h k2Nsuch ha ˛n km 2˛n.
In o de o p o e P oposi ion 2.8, we will appeal o he me hods o Sec ions 3.4
and 3.5. We will use Theo em 3.12 o educe he p oblem o es ablishing he exis ence o
pe ec ac ional ma chings in he app op ia e K -hype g aphs and we will hen employ
Lemmas 3.8 and 3.9 o ind hese pe ec ac ional ma chings. In o de ha ou hype -
g aph has he desi ed p ope ies o apply hese lemmas, we need o choose he diamond
ees which de ine ou o cha d ca e ully.
Clique ac o s in pseudo andom g aphs 839
I u ns ou ha di e en a gumen s a e needed o inding sh inkable o cha ds o
di e en o de s. In Sec ion 6we show how o ind sh inkable o cha ds o small o de ,
es ablishing he ollowing in e media e p oposi ion.
P oposi ion 5.1. Fo any 2N3and 0 < ˛;  < 1=23 he e exis s an ">0such ha
he ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1nand any
e ex subse UV.G/ wi h jUj  n=2. Fo any m2Nwi h
1mmin ¹p 2n12 3; n7=8º;
he e exis s a -sh inkable .k; m/ -o cha d Oin GŒU  wi h k2Nsuch ha ˛n km 
2˛n.
In Sec ion 7we hen add ess sh inkable o cha ds wi h la ge o de , which esul s in he
ollowing.
P oposi ion 5.2. Fo any 2N3and 0 < ˛;  < 1=212 he e exis s an " > 0 such ha
he ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1nand any
e ex subse UV.G/ wi h jUj  n=2. Fo any m2Nwi h
p 1nmn7=8;
he e exis s a -sh inkable .k; m/ -o cha d Oin GŒU  wi h k2Nsuch ha ˛n km
2˛n.
The p oo o P oposi ion 2.8 is basically immedia e om P oposi ions 5.1 and 5.2 bu
we spell i ou none heless.
P oo o P oposi ion 2.8.We spli in o a case analysis based on he densi y po ou
g aph G. Fi s conside pn1=.10 /. Then we claim ha p 2n12 3n7=8 and so he
desi ed -sh inkable o cha d o all o de s up o n7=8 can be de i ed om P oposi ion 5.1.
Indeed, we ha e p 2n12 3n1 2
10 2 3and
1 2
10 2 3 > 1 1
10 1
40 D7=8;
due o ou uppe bound on (and lowe bound on ).
When p < n1=.10 /, we ha e pn2 3again due o ou uppe bound on . Hence
we can apply P oposi ion 5.1 o ind -sh inkable o cha ds o o de s mn7=8 such ha
m<p 1np 2n12 3and apply P oposi ion 5.2 o ind -sh inkable o cha ds wi h
o de s msuch ha p 1nmn7=8. This se les all cases, gi ing he p oposi ion.
In bo h cases, a simple a gumen wo ks o he ex eme cases, ha is, when he o de
is small in P oposi ion 5.1 o when he o de is la ge in P oposi ion 5.2. Ex a ideas a e
hen needed o push he app oaches, ex ending he anges o he wo p oposi ions so ha
hey mee and co e all desi ed o de s. In mo e de ail, an easie o m o P oposi ion 5.1
can co e o de s which ge close o p 1n(see P oposi ion 6.5). Again he sepa a ion
equi ed depends on , explici ly mp 1n1 3. This is al eady enough o co e all
P. Mo is 840
desi ed o cha d o de s when pis la ge. On he o he hand, a basic o m o he a gumen
o la ge o de o cha ds gi es sh inkable o cha ds o o de a leas p 1nwhen pis
la ge and o o de a leas p1 when pis smalle (see P oposi ion 7.3). In e es ingly,
Fac 3.2 implies exac ly ha p1 D.p 2n/ always and so p o es ha when pis small
(close o he lowe bound o .n1=.2 3//) and ou bijumbled g aph is spa se, bo h he
simple a gumen s o small o de s and la ge o de s as well as hei ex ensions a e needed.
Indeed, using he simple e sion, P oposi ion 6.5, o small o de s and he ull powe o
P oposi ion 5.2 lea es a small gap in he o de s, and so does using P oposi ion 5.1 in
conjunc ion wi h he easie P oposi ion 7.3. In o de o help he eade h ough he nex
wo sec ions, in bo h cases we begin by p esen ing he easie weake e sions o he
s a emen s we need. This hen lays he ounda ion o he ull p oo s and allows us o
discuss he mo e echnical aspec s needed o push he anges o which we can p o e he
exis ence o sh inkable o cha ds.
6. Sh inkable o cha ds o small o de
Ou i s a gumen o p o ing he exis ence o sh inkable o cha ds wo ks p o ided he
o de o he o cha d is no oo la ge, es ablishing P oposi ion 5.1. Be o e emba king on
his we ha e o go h ough se e al s eps. Fi s ly, in Sec ion 6.1, we gene alise he heo y
o sh inkable o cha ds buil up in Sec ion 2, allowing sligh ly mo e lexibili y o ou
consequen p oo s. In Sec ion 6.2, we hen use he heo y o pe ec ac ional ma chings
o gi e condi ions ha gua an ee an o cha d is sh inkable. In Sec ion 6.3, we show how
his immedia ely implies he exis ence o sh inkable o cha ds o small o de . Howe e ,
his alls sho o P oposi ion 5.1 and in he es o his sec ion we push he ideas o ex end
he ange o o de s we can co e , showing how o cle e ly choose diamond ees o ou
o cha d in Sec ion 6.4, which allows us o p o e he ull P oposi ion 5.1 in Sec ion 6.5.
6.1. F om o cha ds o sys ems
We begin by gene alising ou de ini ions sligh ly, allowing us o wo k no jus wi h
o cha ds bu also wi h se sys ems.
De ini ion 6.1. Gi en a g aph Gwe say a se ƒ2V.G/ o pai wise disjoin subse s is a
.k; m/-sys em i m jQj  2m o each Q2ƒand jƒj D k. Tha is, a .k; m/-sys em is
jus a amily o kdisjoin e ex se s o size be ween mand 2m.
Now gi en a .k; m/-sys em ƒin a g aph G, he K -hype g aph gene a ed by ƒ,
deno ed HDH.ƒI /, is he -uni o m hype g aph wi h e ex se V.H/ Dƒand wi h
¹Qi1; : : : ; Qi º 2 ƒ
 o ming a hype edge in Hi and only i he e is a copy o K
a e sing he se s Qi1; : : : ; Qi in G.
Finally, o 0 <  < 1, we say a .k; m/-sys em ƒin a g aph Gis -sh inkable (wi h
espec o ) i he e exis s a subsys em ƒo size a leas k such o any subsys em
0, he e is a ma ching in HWD H.ƒ n0I / co e ing all bu k1o he e ices
o H.
Clique ac o s in pseudo andom g aphs 841
No e ha gi en a .k; m/ -o cha d Owe can de ine a .k; m/-sys em ƒas he se s
o emo able e ices o diamond ees in O. Tha is, ƒWD ¹RDWD2Oº. Then he
K -hype g aphs gene a ed by Oand ƒcoincide, i.e. H.ƒI / DH.O/, and Ois -
sh inkable i and only i ƒis -sh inkable. Howe e , De ini ion 6.1 allows us sligh ly
mo e lexibili y, gi ing us he abili y o ocus on subse s o emo able e ices. The nex
obse a ion highligh s his and al hough he esul is i ial, i will be impo an o ou
p oo s.
Obse a ion 6.2. Suppose 3,0<<1and OD¹D1;: : :; Dkºis a .k;m/ -o cha d
in a g aph Gwi h Ribeing he se o emo able e ices o Di o i2Œk. Then i
ƒD ¹Q1; : : : ; Qkºis some .k; m0/-sys em ( o some m0) such ha QiRi o i2Œk
and ƒis -sh inkable (wi h espec o ), hen Ois also -sh inkable.
I will become clea why such a elaxa ion is use ul o us and hus why we make his
swi ch o wo king wi h se sys ems.
6.2. Su icien condi ions o sh inkabili y
We now explo e he condi ions on se sys ems which gua an ee sh inkabili y. We begin by
gi ing some local condi ions on a se sys em which gua an ee ha i is sh inkable gi en
ha i lies in he pseudo andom g aphs we a e in e es ed in.
Lemma 6.3. Fo any 2N3and 0 < ˛;  < 1=.2 2/ he e exis s an ">0such ha
he ollowing holds o any n- e ex .p;ˇ/-bijumbled g aph Gwi h ˇ"p 1n. Suppose
ƒ2V.G/ is a .k; m/-sys em such ha mn7=8,km ˛n,pk nand
(1) he e exis s a subsys em ƒsuch ha jj  k and YWD S¹PWP2ƒnº,
o e e y Q2ƒ he e exis s a e ex 2Qsuch ha
degG
Y. / ˛pkmI
(2) o any u2SP2ƒPand Q2ƒ, we ha e degG
Q.u/ p 1n1 3.
Then ƒis -sh inkable wi h espec o .
Le us make a ew ema ks be o e p o ing he lemma. Fi s ly, no e ha condi ion (1),
despi e he sligh echnicali y necessa y o a oid dependence on se s in , is a na u al
condi ion. Indeed, we a e equi ing ha a leas one e ex in each se is well connec ed o
he o he se s and has a cons an ac ion o he deg ee ha we would expec on a e age.
Condi ion (2) is pe haps mo e mys e ious as i is unclea why ha ing an uppe bound
on he deg ee o a e ex ela i e o ano he se in he sys em is ad an ageous. The poin
is ha his gua an ees ha each o he e ices has a neighbou hood ha is well-sp ead
ac oss he o he se s o he se sys em, wi hou being oo concen a ed on any o he single
se . Wi hin he p oo his necessi y mani es s i sel as we appeal o Theo em 3.12 and
so will need ha when we disallow edges be ween ce ain pai s o se s om being used
(dic a ed by he g aph J), we do no signi ican ly al e he g aph in which we wo k. The
de ails ollow in he p oo .
P. Mo is 848
Le O2be an a bi a y subo cha d o O1wi h jO2j D .1 C/k. Mo eo e , le ƒ0D
¹SDWD2O2ºbe he ..1 C/k; m=4/-sys em de ined by he dis inguished subse s o
emo able e ices o he K -diamond ees in O2. Now due o (6.3), Lemma 6.4 gi es
he exis ence o some -sh inkable (wi h espec o ) subsys em ƒƒ0. Taking OWD
¹D2O2WSD2ƒº hus gi es a -sh inkable .k; m/ -o cha d as equi ed, appealing o
Obse a ion 6.2.
7. Sh inkable o cha ds o la ge o de
In his sec ion, we es ablish he exis ence o sh inkable o cha ds wi h la ge o de , p o ing
P oposi ion 5.2. Ou app oach is o ind an o cha d such ha he K -hype g aph Hgene -
a ed by he o cha d is e y dense. This allows us o apply Lemma 3.8 in many subhype -
g aphs o H. Coupled wi h Theo em 3.12, his will imply ha he o cha d is sh inkable.
As in he p e ious sec ion, we begin in Sec ion 7.1 by using hese esul s on ac ional
ma chings o deduce condi ions on an o cha d which gua an ee sh inkabili y. We will hen
show in Sec ion 7.2 ha we can appeal o P oposi ion 4.1 o gene a e diamond ees whose
emo able e ices a e con ained in many copies o K . This will hen allow us o p o e
he exis ence o sh inkable o cha ds o la ge o de in Sec ion 7.3. As in Sec ion 6, how-
e e , his i s a gumen will all sho o he ange o o de s needed in P oposi ion 5.2.
The es o he sec ion is hus conce ned wi h ex ending ou me hods o cap u e mo e
o de s. This leads us o a p ocess which gene a es an o cha d in wo ounds. The ou come
o he i s ound is discussed in Sec ion 7.4, and building on his, in Sec ion 7.5 we de ail
p ope ies o he o cha d a e a second ound o gene a ion. Finally, in Sec ion 7.6, we
show ha by gene a ing o cha ds ia his wo-phase p ocess, we end up wi h o cha ds
which a e sh inkable. This allows us o comple e he p oo o P oposi ion 5.2.
7.1. A densi y condi ion which gua an ees sh inkabili y
We begin by applying Lemma 3.8 and Theo em 3.12 o gi e a densi y condi ion which we
can use o show ha an o cha d is sh inkable. This ans o ms ou p oblem in o inding
o cha ds which sa is y his condi ion.
Lemma 7.1. Fo all 2N3and 0 <  < 1=.2 3/, he e exis s a k02Nsuch ha
he ollowing holds. Suppose ha Ois a .k; m/ -o cha d in a g aph Gwi h k2Nk0
and m2N. Fo a diamond ee D2O, le RDdeno e i s emo able e ices and o a
subo cha d O0O, le R.O0/WD SD2O0RDdeno e he union o he se s o emo able
e ices o diamond ees in O0. Suppose ha he ollowing condi ion holds:
Fo any D2Oand POn¹Dºsuch ha jPj  k=.4 /, he e exis s
a subo cha d PDP.D;P/Psuch ha jPj  k1 3and o
any disjoin subo cha ds O1; : : : ; O 2PnP, wi h jOij  k1 3
o i2Œ 3 and jO 2j k, he e is a copy o K in G a e sing RD,
R.P/and R.Oi/ o i2Œ 2.
(7.1)
Then Ois -sh inkable.

Clique ac o s in pseudo andom g aphs 849
Le us ake a momen o diges he densi y condi ion (7.1). Fo simplici y, one can
hink o Pbeing a single diamond ee DDD.D;P/. Indeed, his is he se ing ha
we will wo k in i s when applying Lemma 7.1. Simpli ying u he and jus ocusing on
he case ha D3, condi ion (7.1) ansla es as s a ing ha o any K3-diamond ee D
in he o cha d and la ge subo cha d PO, he e is some diamond ee D2Psuch
ha he pai ¹D;Dºhas high deg ee in he K3-hype g aph gene a ed by P. Indeed, o
any small linea sized O1P, he e is a hype edge in H.O/con aining D;Dand a
diamond ee in O1. In gene al, when 4, we need o gua an ee a e sing K s when
some o he se s we look o a e se a e smalle han linea (size k1 3/. Also la e on
we will need he ull powe o Lemma 7.1 which allows us o choose he Pas a small
subo cha d as opposed o a single diamond ee. We now p o e he lemma.
P oo o Lemma 7.1.Le QObe an a bi a y subo cha d o Oo size k. We will
show ha Ois sh inkable wi h espec o Q. So ix some a bi a y subo cha d Q0Q
and le HWD H.OnQ0/be he K -hype g aph gene a ed by OnQ0. We ha e o show
ha Hhas a ma ching co e ing all bu a mos k1 e ices o H.
In o de o show he exis ence o a la ge ma ching in H, as we did in Lemma 6.3, we
appeal o Theo em 3.12. So le us ix ND jV.H/jand no e ha as N.1 /k, by
choosing k0 o be la ge, we can assume ha Nis su icien ly la ge in wha ollows. Now
ix some 2-uni o m g aph Jon V.H/ o maximum deg ee a mos N 2. I we can show
ha HnHJcon ains a pe ec ac ional ma ching, hen we a e done by Theo em 3.12
because, Jbeing a bi a y, he heo em gua an ees a ma ching co e ing all bu a mos
N1k1 e ices o H.
In o de o p o e he exis ence o a pe ec ac ional ma ching in HnHJ, we appeal
o Lemma 3.8, ixing MWD N=.2 /. Thus, we need o show ha gi en any K -diamond
ee D2V.H/ DOnQand subo cha d P0V.H / n¹Dºwi h jP0j  M, he e is
an edge in HnHJcon aining Dand 1 K -diamond ees in P0. So ix such a D
and P0. Le PWD P0nNJ.D/. Then
jPjjP0jjNJ.D/j  N
2 N 2.1 /k
2 k 2k
4
o ksu icien ly la ge. Hence by condi ion (7.1), we ha e he exis ence o some PD
P.D;P/Pas in he hypo hesis. Now we will i e a i ely de ine Oi o 1i 2
as ollows. We begin by ixing P0DPand de ining Q0WD SC2P.N J.C/[ ¹Cº/.
Fo 1i 2, we upda e P0by emo ing any diamond ees in Qi1 om P0
and hen de ine Oi o be an a bi a y subo cha d o P0o size k1 3i i2Œ 3,
and o size k i iD 2. I iD 2we end his p ocess. I i < 2, we de ine
QiWD SC2Oi.N J.C/[¹Cº/and mo e o he nex index.
Le us check ha we a e success ul in each ound. Indeed, his ollows because a he
beginning o s ep iin he p ocess, P0has size
jP0j  k
4 ik1 3.1 CN 2/k
4  k1 3C 2k k1 3
P. Mo is 850
o la ge k. The e o e he e is always space in P0 o choose ou subo cha d Oia each
s ep i. Now condi ion (7.1) gi es a copy o K in G a e sing RD,R.P/and R.Oi/ o
i2Œ 2. This gi es a hype edge ein he K -hype g aph HDH.OnQ0/which has
one e ex D, one e ex in PP0and one e ex in each o he OiP0. Mo eo e ,
his edge elies in HnHJ. Indeed, by ou cons uc ion o Pand he Oi, he e is no
edge in Jbe ween any pai o dis inc se s in he amily ¹¹Dº;P;O1; : : : ; O 2º. We
ha e he e o e es ablished he exis ence o a pe ec ac ional ma ching in HnHJdue
o Lemma 3.8, which implies ha Ois -sh inkable as de ailed abo e.
Lemma 7.1 gi es a ou e o p o ing he exis ence o sh inkable o cha ds. Indeed, i he
se s o e ices which a ise as pools o emo able e ices o subo cha ds a e su icien ly
la ge, hen appealing o Co olla y 3.5 can gi e he equi ed ans e sal copy o K in G,
so ha (7.1) is sa is ied. Howe e , we canno immedia ely de i e such esul s because he
sizes o he se s equi ed in (7.1) a e oo small. In pa icula , (7.1) o ces only one se
(namely R.O 2/) o be linea in size, whils all o he se s ha ea u e can ha e sublinea
size. This is oublesome because he examples we ha e om Co olla y 3.5 o gene a e
ans e sal copies o K equi e a leas wo o he se s in ol ed o be linea . Indeed, i
can be seen om he mo e gene al Lemma 3.4 ha we canno do any be e . Tha is, in
o de o use De ini ion 1.3 and ou condi ion on ˇ o de i e he exis ence o a copy o K
ha a e ses a amily o se s, a leas wo o he se s in he amily mus be linea in size.
The e o e in o de o apply Lemma 7.1 and de i e he exis ence o sh inkable o cha ds, we
ha e o ob ain o cha ds wi h some addi ional s uc u e. We s a by explo ing p ope ies
o singula diamond ess ha we can gua an ee.
7.2. Popula diamond ees
As was he case when we we e in e es ed in p o ing he exis ence o sh inkable o cha ds
wi h small o de , P oposi ion 4.1 gi es a powe ul ool o p o ing he exis ence o dia-
mond ees wi h addi ional desi ed p ope ies. He e we show ha we can choose a dia-
mond ee so ha he e a e many copies o K o med wi h i s emo able e ices.
Lemma 7.2. Fo any 2N3and 0 < ˛ < 1=212 he e exis s an " > 0 such ha he
ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1nand any
e ex subse UV.G/ wi h jUj  n=4. Suppose ha m2Nwi h
max ¹p1 ; p 1nº  mn7=8
and we ha e se amilies W0;W1;:::;W 12V.G/ such ha
(1) jW0j  ˛p 1n o all W02W0;
(2) jWij  ˛pn o all Wi2Wi,1i 3;
(3) jW 2j  ˛n o all W 22W 2;
(4) Q 2
iD0jWij  2m=4.
Clique ac o s in pseudo andom g aphs 851
Then he e exis s a K -diamond ee DD.T; R; †/ in GŒU  o o de a leas mand a
mos 2m such ha o any choice o se s WD.W0; : : : ; W 2/2W0W 2, he e
is a copy o K in G a e sing Rand he se s W0; : : : ; W 2.
P oo . Le us ix ">0small enough o apply P oposi ion 4.1 wi h ˛4.1 D˛0WD 1=23
and Co olla y 3.5 wi h ˛3.5 D˛, as well as being small enough o o ce n o be su icien ly
la ge. No e ha ou lowe bound o .p 1n/ on mand Fac 3.2 imply ha m! 1 as
n! 1 and so we can also assume mis su icien ly la ge in wha ollows. We begin by
spli ing Uin o disjoin subse s U0and W0a bi a ily so ha jU0j;jW0j  n=8 D4˛0 n,
no ing ha his is possible by ou de ini ion o ˛0. We u he ix dWD ˛02p 1n.
Now we apply P oposi ion 4.1 wi h zWD ˛02n=4 Dn=26 C2and ix he se s XU0
and YU0which a e ou pu . No e ha
jXj  max ´2z
dD1
2p 1
1µm
2and jYj D zjXj  z
2Dn
26 C3;
o nla ge.
Now o each choice o WD.W0;: : :;W 2/2W0W 2, we ind some subse
Y.W/Yo size jYj=2 such ha o e e y 2Y.W/, he e is a copy o K 1in he
neighbou hood o which a e ses W0; : : : ; W 2. In o he wo ds, o e e y 2Y.W/,
he e is a copy o K a e sing W0; : : : ; W 2and ¹ º. We can ind Y.W/by epea ed
applica ions o Co olla y 3.5 (2). In mo e de ail, we ini ia e wi h Y0DYand Y.W/emp y
and in each s ep we ind a copy o K a e sing W0;: : :;W 2and Y0. Taking o be he11
e ex o his K ha lies in Y0, we add o Y.W/, dele e i om Y0and mo e o he nex
s ep. We con inue o jYj=2 s eps using he ac ha he condi ions o Co olla y 3.5 (2)
a e sa is ied a each s ep. Indeed, his is due o he lowe bounds on he sizes o Wiin
condi ions (1)–(3) o his lemma and he ac ha jY0j  jYjjY.W/j  jYj=2 ˛n
h oughou , using ou uppe bound on ˛and ou lowe bound on jYjhe e.
Simila ly o he p oo o Lemma 6.6, we now ake Q o be a andom subse o Y
by aking each e ex o Yin o Qindependen ly wi h p obabili y p0WD 5m
4jYj. Thus
EŒjQjD5m=4 and by Theo em 3.6, we ha e m jQj  3m=2 wi h p obabili y a leas
12em=60. Fu he mo e, o any ixed W2W0W 2,
EŒjQ Y.W/jDp0jY.W/j D 5m=8:
Applying Theo em 3.6 again implies ha he p obabili y ha jQ Y.W/j D 0is less
han e5m=16. The e o e using he inequali y Q 2
iD0jWij  2m=4 and appealing o a union
bound, we can conclude ha whp as n(and hence m) ends o in ini y, we see ha
m jQj  3m=2 and Q Y.W/¤ ; o all choices o W2W0W 2. So o
su icien ly la ge nwe can ix such an ins ance QYand aking RWD X[Qwe ha e
11He e we e e o he e ex ha lies in Y0al hough he e may be se e al (i he Wiin e sec he
Y0). Wha we mean he e is he e ex in he copy o K which is assigned o Y0by i ue o he
copy being a e sing.
P. Mo is 852
ha a K -diamond ee DD.T; R; †/ wi h emo able se o e ices Ris gua an eed by
P oposi ion 4.1. We claim ha Dsa is ies all he necessa y condi ions. Indeed, he ac
ha he o de o Dlies be ween mand 2m ollows om he ac ha mjQj3m=2 and
jXj  m=2, whils he ac ha Q Y.W/¤ ; o each choice o WD.W0; : : : ; W 2/
gua an ees ha we ha e a copy o K a e sing QRand he se s W0; : : : ; W 2.
7.3. The exis ence o sh inkable o cha ds o la ge o de
Using Lemma 7.2 o gene a e he diamond ees ha o m ou o cha d, we can p o e ha
he o cha d gene a ed sa is ies he condi ion o Lemma 7.1 and hence is sh inkable. This
gi es he ollowing.
P oposi ion 7.3. Fo any 2N3and 0 < ˛;  < 1=212 he e exis s an " > 0 such ha
he ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1nand any
e ex subse UV.G/ wi h jUj  n=2. Fo any m2Nwi h
max ¹p1 ; p 1nº  mn7=8;
he e exis s a -sh inkable .k; m/ -o cha d Oin GŒU  wi h k2Nsuch ha ˛n km 
2˛n.
P oo . Fix ">0small enough o apply Lemma 7.1 wi h 7.1 Dand Lemma 7.2 wi h
˛7.2 D˛0D˛. Fix some k2Nsuch ha ˛n k2˛n. We also ensu e ha "is small
enough o o ce n(and hence k, due o ou uppe bound on m) o be su icien ly la ge
in wha ollows. Now we begin by no icing ha km=.8 /. Indeed, i pn1=.2 2/,
hen
p1 pnp 1nm;
while i pn1=.2 2/, hen
p 1npnp1 m:
The e o e, o any pwe ha e mpnand k2˛n=m 211 pnm=.8 /.
Now we u n o inding ou .k; m/ -o cha d in GŒU . We do his by inding one dia-
mond ee a a ime as ollows. Fo 1ik, ix UiWD UnSi0<i V.Di0/and no e
ha jUijjUj  2˛ n n=4 h oughou due o ou condi ion on ˛. We hen apply
Lemma 7.2 o ind a diamond ee DiD.Ti; Ri; †i/such ha V.Di/Uiand o any
choice o i02Œi 1 and disjoin subse s I1; : : : ; I 2Œi 1 n ¹i0ºwi h jIjj  pk
o 1j 3, and jI 2j  k, he e is a copy o K a e sing Ri,Ri0and he
se s S`2IjR` o j2Œ 2. The exis ence o such a Di ollows om Lemma 7.2.
Indeed, we de ine W0D ¹Ri0Wi02Œi 1º,WjD ¹S`2I0R`WI0Œi 1; jI0j  pkº
o 1j 3and inally W 2D ¹S`2I0R`WI0Œi 1; jI0j  kº. We need
o check ha condi ions (1)–(4) o Lemma 7.2 a e sa is ied. Indeed, (1) ollows om ou
lowe bound on m, whils (2) and (3) ollow om he ac ha km ˛n and ou de ini-
ion o ˛0. Finally, no e ha each choice o a se in any o he Wjcomes om a subse
o Œi 1. Hence we can uppe bound Q 2
jD0jWjjby .2i/ 12 k. As discussed in he
Clique ac o s in pseudo andom g aphs 853
opening pa ag aph, we ha e km=.8 / and so condi ion (4) o Lemma 7.2 is also sa is-
ied. Thus Lemma 7.2 succeeds in inding he necessa y K -diamond ee a e e y s ep o
his p ocess.
Le OD¹D1; : : :;Dkºbe he o cha d ob ained by his p ocess. We claim ha Ois -
sh inkable and o show his we appeal o Lemma 7.1 and so need o show ha he densi y
condi ion (7.1) is sa is ied by O. So ix Di2Oand POn¹Diºwi h jPj  k=.4 /.
We hen de ine DDD.Di;P/( his plays he ole o Pin (7.1)) o be he diamond
ee in Pwi h he highes index. Tha is, we de ine iWD max ¹i0WDi02Pºand se
DDDi. No e ha we may ha e i< i bu his will no be a p oblem. We claim ha
condi ion (7.1) is sa is ied wi h his choice o D. Indeed, le O1;: : :;O 2Pn¹Dº
be disjoin subo cha ds sa is ying he lowe bounds on he sizes gi en by (7.1). Fo each
j2Œ 2, de ine IjWD ¹i0WDi02Ojº. Then jI 2j  k. Fo 1j 3we ha e
jIjj  k1 3pk. This ollows om he ac ha
k 3k1=2 n1=2 C1n1
8. 1/ p;
whe e we ha e used he uppe bound on in he i s inequali y, he ac ha kpnin
he second inequali y (see he opening pa ag aph o he p oo ), and p 1nmn7=8 in
he las inequali y. Now elabelling ¹i; iºas ¹`0; `1ºso ha `0< `1, we see ha a he
poin o choosing D`1, we gua an eed ha he e was a K a e sing R`1,R`0and he
se s R.Oj/DSi02IjRi0 o j2Œ 2. By Lemma 7.1 his comple es he p oo ha O
is -sh inkable.
P oposi ion 7.3 es ablishes P oposi ion 5.2 when Gis e y dense. Howe e , when
Gis spa se (when pn1=.2 2/ o be speci ic), he lowe bound o mp1 akes
o e and we a e le wi h a gap be ween he ange co e ed by P oposi ion 7.3 and he
desi ed ange o P oposi ion 5.2. T acing he condi ion ha mD.p1 /back h ough
he p oo , we can see ha his was necessa y in o de o p o e Lemma 7.2. The e, we used
ou key P oposi ion 4.1 o gene a e a diamond ee whe e we had a la ge pool Yo e ices
which we e candida es o being emo able e ices. In o de o es ablish he exis ence
o he cliques we need in Lemma 7.2, we needed Y o be linea in size. The s icking
poin hen comes om he ac ha P oposi ion 4.1 can only gua an ee a maximum ac o
o O.p 1n/ be ween he size o he pool o e ices Yand he o de o he diamond
ee ha we gene a e. Indeed, in P oposi ion 4.1 we a e o ced o include he se Xin
he emo able e ices o he diamond ee we gene a e and when Yis linea in size,
Xcould ha e size as la ge as .p1 /. I is unclea how one would imp o e on his and
ind diamond ees wi h smalle o de ha a e s ill con ained in su icien ly many copies
o K .
Thank ully, he e is a way o ci cum en his issue and apply ou me hods o close
he gap in he ange o o de s none heless. The key idea is o eplace he diamond ee
gene a ed by Lemma 7.2 wi h a se o diamond ees, ha is, a small subo cha d. Indeed,
by g ouping oge he diamond ees, we can dec ease hei o de bu gua an ee ha he
collec i e pool o po en ial emo able e ices o he g oup is s ill linea in size. Th ough

P. Mo is 854
ollowing a simila p oo o ha o Lemma 7.2, his has he ou come o being able o gua -
an ee many copies o K which con ain a e ex in he emo able e ices o one o he
diamond ees in he g oup. Mo eo e , in he p oo o P oposi ion 7.3, we c ucially used
he ac ha we could gene a e diamond ees om Lemma 7.2 o es ablish he densi y
condi ion (7.1) o Lemma 7.1. We chose an app op ia e Dand used he ac ha i had
been gene a ed by Lemma 7.2 o p o e he equi ed exis ence o ans e sal copies o K .
Howe e , Lemma 7.1 allows us o use a much la ge subo cha d P o his condi ion
as opposed o a single diamond ee. The e o e he e is hope o inco po a e he idea o
using a subo cha d ins ead o a single diamond ee in Lemma 7.2, whils main aining
he o e all, scheme o he p oo . The e a e some u he di icul ies o o e come, bu on a
high le el, his is he app oach we ollow in he nex sec ions o es ablish P oposi ion 5.2.
7.4. P ep ocessing he o cha d
As discussed abo e, in o de o p o e P oposi ion 5.2 and emo e he condi ion ha mD
.p1 / om P oposi ion 7.3, we need o eplace he ole played by Din he p oo
by a small subo cha d P. This allows us o p o e an analogue o Lemma 7.2, whe e
one now inds an o cha d whose collec i e se o emo able e ices lies in many copies
o K . Ou sh inkable o cha d will hen be o med as he union o many o hese smalle
o cha ds. Indeed, in wha ollows we will spli kas kD` and will aim o ha e smalle
.`; m/ -o cha ds con ibu ing o ou sh inkable o cha d O. Each o he .`; m/ -o cha ds
will ha e s ong connec i i y o he es o he o cha d O.
In o de o wo k wi h he ac ha we a e spli ing kin o se s o size `, we in oduce
a wo-coo dina e index sys em, wi h .i; j / 2Œ  Œ` indica ing ha we a e e e ing o
he j h objec in he i h subse and we will wo k h ough hese indices lexicog aphically.
In mo e de ail, we le <Ldeno e he lexicog aphic o de on he pai s .i; j / 2Œ  Œ`.
Tha is, .i0; j 0/ <L.i; j / i and only i ei he 1i0i1and 1j0`o i0Diand
1j0j1. Fu he mo e, o each 1i and 1j`, we de ine
I<ij WD ¹.i0; j 0/2Œ  Œ` W.i0; j 0/ <L.i; j /º
o be he indices .i0; j 0/which come be o e .i; j / in he lexicog aphic o de .
A hu dle ha a ises wi h ou new app oach is ha we lose he symme y p o ided by
he ac ha bo h Dand Din ou applica ions o Lemma 7.1 we e gi en by singula
diamond ees. Indeed, in ou p oo o P oposi ion 7.3, when e i ying condi ion (7.1)
o Lemma 7.1, we use he ac ha bo h he a bi a y diamond ee DDDiand he
diamond ee DDD.Di;P/ ha we can choose we e gene a ed using Lemma 7.2.
We now hope o gene a e ou subo cha ds Pusing an equi alen o Lemma 7.2, and
his will mean ha we can no longe swi ch he oles o Dand Pwhen appealing o he
conclusion o ( he p oo me hod o ) Lemma 7.2. In pa icula , his places a highe demand
on he p ope ies we need o conclude o ou .`; m/ -subo cha ds.
In mo e de ail, we need o gene a e subo cha ds which a e highly connec ed o all he
o he e ices o he K -hype g aph H.O/. The e o e i no longe su ices o build ou
o cha d in a linea ashion, choosing diamond ees (o indeed subo cha ds) o be well
Clique ac o s in pseudo andom g aphs 855
connec ed (in e ms o he K -hype g aph) wi h p e iously chosen diamond ees. We
will ins ead gene a e ou o cha d in wo ounds. In he i s ound we ix a pa o each
diamond ee and using P oposi ion 4.1, p o ide la ge pools o e ices which can ex end
he pa s o he diamond ees chosen so a , which we will hen do in he second ound.
Lemma 7.4 de ails he ou come we d aw om his p ep ocessing i s ound.
Lemma 7.4. Fo any 2N3and 0 < ˛ < 1=212 he e exis s an " > 0 such ha he
ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n, any e ex
subse UV.G/ wi h jUj  n=2 and any k; m; ; ` 2Nsuch ha
kD `; ˛n km 2˛n and `m p1 :
The e exis e ex se s Zij ; Yij Uand ma chings …ij ; ‡ij K 1.GŒU / o . 1/-
cliques o each i2Œ  and j2Œ` such ha he copies o K 1in each ‡ij WD ¹S W
2Yij ºa e indexed by he e ices in Yij and condi ions .1ij / h ough .5ij /below a e
sa is ied o all 1i and 1j`:
.1ij /jZij j D mand j…ij jDjZij j1.
.2ij /jYij jDj‡ij j D p˛ n=`.
.3ij /The e ex se s Zij ,Yij ,V .…ij /and V .‡ij /a e all disjoin om each o he .
.4ij / A A0D ; o any choice o A2 ¹Zij ; V .…ij /; Yij ; V.‡ij /ºand12
A02 ¹Zi0j0; V.…i0j0/W.i0; j 0/2I<ij º[¹Yij 0; V .‡ij 0/W1j0j1º:
.5ij /Fo any choice o Q
Ysuch ha Q
YYij , he e exis s a K -diamond ee DD
.T; R; †/ such ha RDZij [Q
Yand †D…ij [Q
‡ij , whe e Q
‡ij ‡ij is de ined
o be
Q
‡ij WD ¹SQ W Q 2Q
YYij º:
As men ioned abo e, in his i s ound we pu aside pa o e e y single diamond ee
in he .k; m/ -o cha d we a e going o gene a e, hus pa ially de ining he o cha d. We
also pu aside la ge pools o e ices which will be used o ex end hese diamond ees in
he second ound o gene a ing ou o cha d. The ixed pa s o he diamond ees chosen
in Lemma 7.4 a e he se s Zij and he in e io cliques …ij , whils he pools o po en ial
emo able e ices and in e io cliques ha can be used o ex end he diamond ees cho-
sen a e gi en by he se s Yij and ‡ij , espec i ely. We make su e h ough condi ions .1ij /
ha hese ixed diamond sub ees con ibu e a subs an ial po ion o he inal diamond
ees ha we a e shoo ing o (which will ha e o de be ween mand 2m). We also gua -
an ee h ough condi ions .4ij / ha he pa s o he diamond ees ha we pu aside in
his p ep ocessing ound do no in e e e wi h each o he , in ha hey a e e ex disjoin .
No ice also ha i we ix i2Œ , hen condi ions .4ij / o all j2Œ` gua an ee ha he
12C ucially, we do no equi e ha Ais disjoin om all Yi0j0and V .‡i0j0/, only hose ha a e
in he same sub amily indexed by i.
P. Mo is 856
se s Yij ; V .‡ij /,j2Œ`, do no in e sec each o he . This is impo an because in he sec-
ond ound o gene a ing ou o cha d, we will wan o ex end all he diamond ees in he
i h .`; m/ -subo cha d simul aneously and so we do no wan any in e e ence be ween
he choices o he ex ensions wi hin such a subo cha d. Also no e ha condi ions .2ij /,
o ixed i2Œ  and all j2Œ`, gua an ee ha he collec i e pool o po en ial emo able
e ices o he i h .`; m/ -subo cha d ( he se Sj2Œ` Yij ) is linea in size, as equi ed.
Finally, condi ions .5ij /con ain he hea o P oposi ion 4.1, allowing us o a bi a ily
ex end any o he diamond ees we ha e so a using any subse s o he pools ( he Yij ) o
po en ial emo able e ices and in e io cliques ( he ‡ij ) we ha e pu aside.
Ou inal ema k on he s a emen o Lemma 7.4 is ha we do no equi e e.g. Yij
and Yi0j0 o i¤i0, o be disjoin . Indeed, as we ha e subo cha ds and each has a linea
collec i e pool o po en ial emo able e ices, he e would no be enough space in he
g aph o keep hese pools disjoin . Howe e , by equi ing ha he collec i e pool is much
la ge han all he e ices in ou o cha d ( ha is, much la ge han km), we gua an ee
ha we will be able o p oceed g eedily in ou second ound (Lemma 7.5) o de ining he
o cha d, always ha ing a la ge enough se o po en ial emo able e ices a each s ep.
P oo o Lemma 7.4.Le us ix ">0small enough o apply P oposi ion 4.1 wi h ˛4.1 D
˛0WD1=22 C1. We will ind hese e ex se s and ma chings o . 1/-cliques algo i hmi-
cally wo king h ough he pai s .i; j / 2Œ  Œ` in lexicog aphic o de . So le us ix some
.i; j /2Œ  Œ` and suppose ha we ha e al eady ound Zij ; Yij ; …ij and ‡ij such
ha condi ions .1ij / h ough .5ij /a e sa is ied o all .i; j / 2I<ij. We ix WU o
be
WWD [¹Zij [V .…ij /W.i; j / 2I<ijº
[[¹Yij[V.‡ij/W1jj1º;
and le UWD UnW. We use condi ions .1ij /and .2ij / o uppe bound he size o W
as ollows. We ha e
jWj m..i1/` Cj1/ Cp˛ n
`.j 1/  m ` Cp˛ n .2˛ Cp˛/ n;
using m ` Dmk 2˛n. Hence jUj  n=4 om ou uppe bound on ˛. We will ind
Zij; YijUand …ij; ‡ijK 1.GŒU / and so condi ion (4ij)will
be sa is ied. The equi ed e ex se s Zijand Yija e ound by an applica ion o
P oposi ion 4.1. So le us spli Uin o disjoin subse s U0and W0a bi a ily so ha
jU0j;jW0j  n=8 4˛0 n, no ing ha his is possible by ou de ini ion o ˛0. We u he
ix dWD ˛02p 1nand zWD mCp˛ n=` and no e ha z˛0ndue o he ac ha
m2˛n=k 2˛n and ou uppe bound on ˛.
So P oposi ion 4.1 shows ha he e exis s disjoin e ex subse s X; Y U0U
such ha jXjCjYj D zand jXj D 1mo
jXj  2z=d2m
dC2p˛ n
d`m
2C2p˛
˛02p 1`m;
Clique ac o s in pseudo andom g aphs 857
using ou uppe bound on ˛and lowe bound on `m in he las inequali y. As jXjm, we
can ix some ZijX[Ysuch ha XZijand jZijj D m. The e o e le ing
YijWDYnZij, we ha e jYijjDzmDp˛ n=` and so he size equi emen s on
Zijin (1ij)and on Yijin (2ij)a e bo h sa is ied. Mo eo e , pa o (5ij)is
also sa is ied. Indeed, o some Q
YYij, aking Y0DQ
Y[.ZijnX/, P oposi ion 4.1
implies ha he e is a diamond ee DD.T;R;†/ wi h emo able e ices RDX[Y0D
Zij[Q
Yand †a ma ching o . 1/-cliques in GŒU .
Now in o de o comple e he p oo o he lemma, we need o de ine he ma chings o
. 1/-cliques …ijand ‡ijand eason ha he emaining condi ions o he lemma
a e sa is ied. This comes om ecalling how we p o ed P oposi ion 4.1 in Sec ion 4.1 (see
also Figu e 6). The e, we applied Lemma 4.5 o ind a la ge d-sca e ed K -diamond ee
Dsc D.Tsc; Rsc; †sc/, whe e Rsc DX[Ywas he se o emo able e ices o Dsc and
YRsc was he se o lea es in Dsc. The conclusion o P oposi ion 4.1 hen ollowed
eadily as we could choose which lea es in Y o include in a diamond sub ee Do Dsc.
F om his p oo we see ha we can pa i ion †sc in o †sc DW …ij[‡ijwhe e he
. 1/-cliques …ija e in e io cliques o he K -diamond sub ee o Dsc spanned
by he emo able e ices Zij. Fu he mo e, we can label ‡ijwi h he e ices in
Yijso ha (5ij)is sa is ied. Indeed, each e ex in Yijco esponds o a lea o
he diamond ee Dsc and so he e is an in e io clique S 2†sc such ha any diamond
sub ee which con ains he non-lea es Xo Dsc can be ex ended by adding o he se
o emo able e ices and S o he se o in e io cliques. As Dsc is a well-de ined K -
diamond ee, condi ion (3ij)is also sa is ied and he size cons ain s on …ijand
‡ijin (1ij)and (2ij)a e also immedia e, no ing ha j…ijjDjZijj  1as
he se o in e io cliques o a diamond ee wi h emo able e ices Zij.
7.5. Comple ing he o cha d
We will now use Lemma 7.4 o gene a e ou o cha d. This can be hough o as ex ending
he pa s o he diamond ees ( he Zij and …ij ) which we e ixed in Lemma 7.4. The
s a egy is e y simila o ha o Lemma 7.2 and P oposi ion 7.3. Indeed, we ake andom
subse s o he pools o po en ial e ices in o de o gua an ee ha he K -hype g aph
gene a ed by ou inal o cha d is su icien ly dense. The key di e ence he e is ha , as
opposed o ixing ou o cha d one diamond ee a a ime, we appeal o Lemma 7.4 o ix
pa o all he diamond ees in ou o cha d and hen ca y ou he ex ensions on .`; m/ -
subo cha ds. Tha is, we apply he app oach o Lemma 7.2 on he whole subo cha d as
opposed o a singula K -diamond ee. A e doing his p ocess o all subo cha ds we
end up wi h an o cha d which gene a es a dense K -hype g aph. This is de ailed in he
ollowing lemma.
Lemma 7.5. Fo any 2N3,0 < ˛ < 1=212 and 0 <  < 1 he e exis s an " > 0 such
ha he ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n, any
e ex subse UV.G/ wi h jUj  n=2 and any k; m; ; ` 2Nsuch ha
kD `; m p 1n; `m p1 and ˛n km 2˛n: (7.2)
P. Mo is 864
p ocedu e, appealing o Co olla y 3.5 (3) o ind each S2…(and he co esponding
neighbou hood se XS), one by one.
A e inding …, we hen u n o cons uc ing he .4 ; M /-o cha d J.A/ o he
abso bing s uc u e A. Again, his will be done g eedily, ixing he diamond ees
D2J.A/one a a ime. Le us conside ixing some diamond ee Dj2J.A/. No e
ha as we ix Dj, we immedia ely ge es ic ions on which S2… emain as candida es
o play he ôle o ce ain Si2„.A/. Indeed, i he emo able e ices o Dja e disjoin
om NG.S/ and ij is an edge in he empla e Tde ining A, hen he e is no way Scan
play he ole o Siin „.A/. The e o e as we ix ou diamond ees, we will aim o ha e
hei se s o emo able e ices in e sec as many o he XS(and hence neighbou hoods
NG.S/) o S2…as possible.
In o de o do his, we will use he ollowing lemma, which shows ha we can ind
diamond ees whose emo able e ices in e sec many p esc ibed se s (in ou case his
will be he se s XS). The p oo o his lemma is a simple applica ion o P oposi ion 4.1.
Lemma 8.4. Fo any 2N3and 0 < ˛ < 1=22 , he e exis s an " > 0 such ha he
ollowing holds o any n- e ex .p; ˇ/-bijumbled g aph Gwi h ˇ"p 1n.
Suppose ˛2
2n2=3 `˛n2=3 and we ha e disjoin e ex subse s W; U1; : : : ; U`
such ha jWj  n=4 and jUij  n1=3 o all i2Œ`. Then he e exis s a diamond ee
DD.T; R; †/ in Gsuch ha
(i) †K 1.GŒW / is a ma ching o . 1/-cliques in W;
(ii) RS`
iD1Uiand Rin e sec s `0o he se s Ui o some `0`=.4 /;
(iii) he o de o Dis a mos n2=3;
(i ) o all bu a mos n1=2 o he indices i2Œ`, we ha e jV .D/ Uij  n1=6.
P oo . We begin by ixing WD `=n2=3 so ha ˛2=2 ˛and we ix "small enough
o apply P oposi ion 4.1 wi h ˛4.1 D˛0WD =.4 / and small enough o gua an ee ha
pC n1=.2 3/ wi h CD4=˛0(see Fac 3.2). Now sh ink each se Uiso ha i has
exac ly n1=3 e ices and de ine UWD S`
iD1Ui. Fu he mo e, ix dWD ˛02p 1nand
apply P oposi ion 4.1 wi h U,Wand zD˛0n. So we ge disjoin subse s X; Y Uas in
he ou come o P oposi ion 4.1.
Now i s ly no e ha as jXjCjYj D zD˛0n,jUj D `n1=3 Dn D4 z and he Ui
ha e equal size, X[Ymus in e sec a leas `=.4 / o he se s Ui. We will choose ou
DD.T;R; †/ so ha Rin e sec s all he se s Ui ha X[Yin e sec s, hus gua an eeing
condi ion (ii). Indeed, i we le Y0Ybe he minimal subse o Ysuch ha he e exis s no
i2Œ` wi h Y Ui¤;and Y0 UiD;, P oposi ion 4.1 gi es he exis ence o a diamond
ee DD.T; R; †/ such ha RDX[Y0and †K 1.GŒW / and so condi ions (i)
and (ii) a e sa is ied.
In o de o es ablish condi ion (iii), no e ha jY0j  `n2=3=2 and i jXj> 1 hen
jXj  2z
d2
˛0p 12n. 1/=.2 3/
˛0C 1n2=3
2;

Clique ac o s in pseudo andom g aphs 865
due o ou de ini ion o Cand he ac ha 1
2 32
3 o all 3. Finally, (i ) is a simple
consequence o (iii). Indeed, i (i ) we e no ue, hen as he Uia e pai wise disjoin , D
would ha e o de g ea e han n1=2 n1=6 n2=3, a con adic ion.
Le us e u n o ske ching he p oo o P oposi ion 8.3, conside ing now ha we can
use Lemma 8.4 o ind diamond ees D2J.A/. As discussed abo e, he key p ope y
o diamond ees gene a ed by Lemma 8.4 is (ii), allowing us o ind diamond ees ha
in e sec many o he se s ¹XSWS2…ºwhich we begin he p oo wi h. P ope y (i )
will also be use ul as i shows ha in he p ocess o building J.A/one by one, we do
no des oy many o he se s XSand mos o hem emain la ge and can be used by o he
D2J.A/.
One po en ially oublesome consequence o Lemma 8.4 is ha he diamond ees
i inds a e a oo small; see (iii). Indeed, he diamond ees in ou o cha d J.A/a e
supposed o be o o de MDn7=8. I u ns ou ha his is no such a big hu dle as we
can ind a la ge diamond ee disjoin om all he XSand connec i o he diamond
ee Cou pu by Lemma 8.4. In mo e de ail, we can apply P oposi ion 4.1 o c ea e a la ge
(linea ) pool Yo e ices ha can be emo able e ices o some diamond ee which will
be disjoin om all he e ices in he se s XS. We also conside he la ge (linea ) pool Z
o e ices ha lie in some XSnV.C/wi h S2…such ha he emo able e ices o C
in e sec XS. I is no ha d o show (see o example Co olla y 3.5 (3)) ha he e is a copy
o K
C1wi h one deg ee 1 e ex in Yand he o he in XSZ o some S2….
By also aking Sin o Dand choosing an app op ia e Y0Y o apply he key p ope y
o P oposi ion 4.1, we can ob ain a diamond ee Do he co ec size ha con ains he
diamond ee Cou pu by Lemma 8.4.
Mo e oublesome is he ac ha condi ion (ii), which means ha he emo able
e ices o Cin e sec many o he desi ed se s XS, is, in ac , no s ong enough.
Indeed, conside some ixed i2I o which we wan o ind a copy Sio K 1 o lie
in „.A/. I j; j 02NT.i/ and he se s ¹XSWS2…; RDj XS¤ ;º and ¹XSWS2…;
RDj0 XS¤;ºa e disjoin (he e, as usual, we use RD o deno e he emo able e ices
o D), hen al eady he e a e no candida es o Siin …. To ix his, we ac ually need ha
when we choose a diamond ee D2J.A/, he se RDin e sec s almos all o he se s
¹XSWS2…º. We achie e his by i e a ing Lemma 8.4, c ea ing cons an ly many disjoin
diamond ees C ha oge he hi almos all o he XSwi h hei emo able e ices. We
hen connec all o hese diamond ees Cwi h a la ge diamond ee disjoin om he
se s XS o ob ain he desi ed diamond ee D2J.A/. This connec ing p ocess is simila
o (al hough sligh ly mo e in ol ed han) he connec ing p ocess ou lined in he p e ious
pa ag aph. We now gi e he ull de ails o he p oo o P oposi ion 8.3, concluding his
sec ion and chap e .
P oo o P oposi ion 8.3.We begin by ixing ">0small enough o apply Co olla y 3.5
wi h ˛3.5 D˛0WD˛2=.16 / and o apply P oposi ion 4.1 and Lemma 8.4 each wi h ˛4.1 D
˛8.4 D˛. We also ake "small enough o o ce n o be su icien ly la ge and o gua an ee
ha pC0n1=.2 3/ o C0WD 2=˛02using Fac 3.2. We u he ix some empla e T
P. Mo is 866
wi h e ex se s Iand JDJ1[J2o lexibili y and maximum deg ee 40 which we
know exis s o n(and hence ) su icien ly la ge by Theo em 3.14 o Mon gome y [57].
We will ind an abso bing s uc u e wi h espec o Tand so mus p o e he exis-
ence o a ma ching „.A/D ¹SiWi2Iº  K 1.GŒW / o 3 copies o K 1, and a
.4 ; M /-o cha d JDJ.A/D ¹DjWj2Jºsuch ha he condi ions o De ini ion 8.1
a e sa is ied. We will do his in h ee s ages. In Claim 8.5, we ix some la ge ma ching
…K 1.GŒW / o . 1/-cliques which will be candida es o he . 1/-cliques
which will ea u e in „.A/. We will gua an ee ha he cliques in …a e con ained in
many copies o K which will help as we p oceed o build ou abso bing s uc u e. In
Claim 8.6, we will ix he K -diamond ees which will o m ou o cha d J o ou
K -abso bing s uc u e. We will ca e ully con ol how hese diamond ees in e sec he
cliques in ou candida e se …and hei neighbou hoods. Finally, we will show ha we
can ind a sui able „.A/…so ha we ob ain he desi ed abso bing s uc u e.
Claim 8.5. The e exis s a ma ching …D ¹S1; : : : ; S`º  K 1.GŒW / o `WD ˛n2=3
copies o K 1and se s XhWnV.…/ o each h2Œ` such ha he Xha e pai wise
disjoin , each has size 2n1=3 and o all h2Œ` we ha e XhNG
W.Sh/.
P oo o Claim. We can do his by way o a simple g eedy p ocess choosing such an
. 1/-clique Shand se Xhin o de o hD1; : : : ; `. When choosing Shand Xh, we
look a he se o e ices VhWwhich ha e no been used in p e ious choices o Sh0
o Xh0. We ha e
jVhj  jWjˇˇˇ[
h0<h
.Xh0[Sh0/ˇˇˇn=2 .` 1/. 1C2n1=3/.1=2 2˛/n n=4;
and an applica ion o Co olla y 3.5 (3) wi h W0DW1DW2DVhgi es he desi ed Sh
and Xhin Vhsince
˛02p 1n˛02C0n1. 1/=.2 3/ 2n1=3
due o Fac 3.2.
Nex we u n o ixing ou .4 ; M /-o cha d J.
Claim 8.6. Le Shand Xh o hD1;: : :;` be as in Claim 8.5. Then he e exis s a .4 ;M /-
o cha d JD ¹D1; : : : ; D4 ºsuch ha V.J/Wand he ollowing p ope ies hold o
each DjD.Tj; Rj; †j/wi h j2Œ4 :
(1) he se Rjo emo able e ices in e sec s a leas .1 ˛/` o he se s Xhwi h h2Œ`;
(2) V.Dj/in e sec s a mos CWD log.2
˛/
log.4
4 1/o he Shwi h h2Œ`.
Be o e p o ing he claim, le us see how i implies he p oposi ion. Indeed, aking
he .4 ; M / o cha d J om Claim 8.6 as J.A/, we jus need o choose a ma ching o
. 1/-cliques „.A/D ¹SiWi2Iºso ha Si V.J/D ; o all i2Iand whene e
ij 2E.T/, he e is a e ex in Rjwhich o ms a copy o K wi h Si. We do his g eedily,
Clique ac o s in pseudo andom g aphs 867
showing ha o each iD1; : : : ; 3 in o de , he e is a sui able choice o Siin …. We ini-
ia e by ixing LŒ` o be he indices h2Œ` such ha Sh V.J/D;. By condi ion (2)
in Claim 8.6, o la ge nwe ha e
jLj  `4C .1 ˛/`
a he beginning o his p ocess, ecalling ha `D˛n2=3 and D˛n1=8. Now o iD
1; : : : ; 3 , we ind an index hDh.i/ 2Lsuch ha Sh o ms a copy o K wi h a e ex
in Rj o all jsuch ha ij 2E.T/. We ix SiDShand dele e h om L. I his p ocess
succeeds in inding a sui able hDh.i/ o each i2I hen he esul ing „.A/D ¹SiW
i2Iºalong wi h J o m he desi ed K -abso bing s uc u e.
I emains o check ha we a e success ul a each s ep. So conside s ep i2Œ3 .
We ha e ha jLj  .1 ˛/` .i1/ .1 2˛/` a he beginning o he s ep. Now
o each j2Jwhich is a neighbou o iin he empla e T, by Claim 8.6 (1) he e a e
a mos ˛` indices h2Œ` such ha no e ex o Rj o ms a K wi h Shin G. Indeed,
o almos all choices o h, we ha e Rj Xh¤ ; and XhNG.Sh/. Gi en ha Thas
maximum deg ee 40, his gi es a mos 40˛` indices h2L ha would no be a good
choice o h.i/. The e o e he e a e a leas .1 42˛/` indices h2Lwhich can be
chosen as h.i/and we simply choose one a bi a ily.
This shows ha he algo i hm is success ul in gene a ing he desi ed abso bing s uc-
u e and so i only emains o p o e Claim 8.6, which we do now.
P oo o Claim 8.6.We will ind he diamond ees Dj,jD1; : : : ; 4 , one by one so
ha hey a e e ex disjoin and sa is y he wo condi ions in he s a emen o he claim as
well as he u he ollowing condi ion:
(3) V.Dj/in e sec s all bu a mos C n1=2 o he Xhwi h h2Œ` in mo e han 2C n1=6
e ices.
We will ini ia e he p ocess wi h ƒWD Œ` and UhDXh o all h2Œ`. These se s
Uhwill keep ack o e ices in Xh ha we a e s ill allowed o use, ha is, hose e -
ices which ha e no been used in p e iously chosen diamond ees. Fu he mo e, he se
ƒŒ` will keep ack o all indices which a e ali e. When we choose a Dj o some
j2Œ4 , we kill (and emo e om ƒ) all he indices h2Œ` such ha V.Dj/in e sec s Xh
in mo e han 2C n1=6 e ices. We also kill any index hsuch ha V.Dj/in e sec s Sh. Due
o ou condi ions (2) and (3), h oughou he p ocess we ha e
jƒj  `4 .C CC n1=2/.1 ˛=2/`
o nla ge, ecalling ha `D˛n2=3 and D˛n1=8. Mo eo e , due o condi ion (3), a
any poin in he p ocess, o all ali e indices hin ƒ, he size o UhXhis a leas
jUhjjXhjX
jjV.Dj/ Xhj  2n1=3 8 C n1=6 n1=3
o nsu icien ly la ge. We ema k ha i is c ucial in he p e ious wo calcula ions ha
Dn1=8 and so when choosing ou diamond ees, we do no kill oo many indices o
P. Mo is 868
make oo many o he se s Xh oo small o be used by subsequen diamond ees. In ac ,
any polynomially smalle han n1=6 would su ice o his.
So le us suppose ha we a e a s ep j2Œ4  whe e we look o Djand we ha e
some ixed se ƒo ali e indices and subse s UhXh o h2ƒ. We un a subalgo i hm
ha inds Djin wo phases. We begin by se ing Dƒand CD ;. The i s phase o
he subalgo i hm wo ks by inding a mos Csmall o de diamond ees whose emo able
e ices in e sec many o he Uh o h2ƒ. The amily Cwill collec hese small o de
diamond ees and he se will keep ack o he indices hin ƒ o which we ha e no
ye in e sec ed Uh. In he second phase o he algo i hm, we will o m Djby joining
oge he he diamond ees in Cso ha hey o m one diamond ee. By gua an eeing ha
ou diamond ees in Cha e emo able e ices ha in e sec mos o he se s Uh, we will
gua an ee condi ion (1) o he claim. Be o e s a ing, we also ini ia e by se ing W0W
o be
W0DWn[
h2Œ`
.Sh[Xh/[[
j <j 
V.Dj/:
In wo ds, W0is he subse o e ices o W ha has no been used in any o he s uc u es
ha we ha e ound so a . Finally, we ini ia e a coun e by se ing sD1.
A s ep s, we apply Lemma 8.4 on he se s W0and ¹UhWh2º. We hus ind a
K -diamond ee CsD.T; R; †/ which we add o C, which has he ollowing p ope ies
gua an eed by Lemma 8.4:
(i) †K 1.GŒW 0/ and we dele e V .†/ om W0;
(ii) RSh2Uhand de ining s o be sWD¹h0WR Uh0¤ ;º, we ha e jsj
jj=.4 /; we dele e s om ;
(iii) he o de o Csis a mos n2=3;
(i ) he e is a se ˆssŒ` o a mos n1=2 indices such ha o all h2Œ` nˆs
we ha e jV.Cs/ Uhj  n1=6.
Finding such a Csconcludes s ep s. I jj< ˛`=2, we e mina e his phase and mo e on
o he nex phase. I jj  ˛`=2, we mo e o s ep sC1.
We mus check ha he condi ions o Lemma 8.4 a e sa is ied h oughou his phase
in o de o ind he equi ed diamond ees Csa each s ep. Indeed, his ollows because
˛2
2n2=3 D˛
2` jj  `D˛n2=3
h oughou , and jUhjn1=3 o all h2since ƒis a subse o ali e indices. Finally,
jW0jn=4 h oughou his p ocess. Indeed, no e ha due o condi ion (ii) and he ac ha
we only con inue un il jj  ˛`=2, he p ocess uns o a maximum o Cs eps, ecalling
he de ini ion o C om condi ion (2) o he claim. Tha is, jCj  C h oughou and so
jW0jjWj X
h2Œ`
.jShjCjXhj/X
j <j jV.Dj/j X
C2C
V.C/
n
2`3n1=3 8 M C n2=3 1
2.4 C8 /˛nn
4;(8.2)
Clique ac o s in pseudo andom g aphs 869
ΠS1S2ShSℓ−1Sℓ
X1
X2
Xh
Xℓ−1
Xℓ
U1
U2
Uh
Uℓ−1
Uℓ
C1
C2
X
Y
S′
1S′
2
x1x2
z1z2
Fig. 8. An example o Djand i s componen s. In his case, we ha e cD2,h1D1and h2Dh.
due o ou uppe bound on ˛, o nsu icien ly la ge. This e i ies ha we ind Csa
e e y s ep so his p ocess and so we inish his phase wi h jj< ˛`=2 and some amily
CD ¹C1;:::;Ccºo cC e ex disjoin K -diamond ees.
Now we desc ibe how we gene a e Djwhich will ha e all he diamond ees Cs2C
as sub-diamond- ees. We e e he eade o Figu e 8 o keep ack o he many compo-
nen s ha con ibu e o ou Dj. One hing o no e is ha he sum o he o de s o he
diamond ees in Cis a oo small o us o jus build Dj om he diamond ees in C.
Indeed, he sum o he o de s is O.n2=3/and we wan Dj o ha e o de MDn7=8.
The e o e we will ha e o ind he majo i y o he K -diamond ee Djelsewhe e. In
o de o p epa e o his, we i s spli W0a bi a ily in o U0; W0and Z0o oughly equal
size and no e ha due o ou lowe bound (8.2) on jW0j, each o hese se s has size a leas
n=16. Nex we ix dWD˛2p 1nand zD˛2nand apply P oposi ion 4.1 wi h espec o
he se s U0and W0 o ge disjoin se s X;Y U0as de ailed he e. No e ha jXj2n2=3.
Indeed, i jXj> 1, hen jXj  2z=d2p1 2n2=3 due o Fac 3.2.
Now o 1sc, de ine ZsWD Sh2snˆs.UhnV.Cs//. In wo ds, Zsis he union
o he se s Uhwhich Csin e sec s, a e emo ing he se s Uh0which Csin e sec s in oo
many e ices and hen emo ing he e ices o Cs. Now, o each s2Œc,
jZsj  .jsjjˆsj/.n1=3 n1=6/˛`n1=3
8 2n5=6 ˛2n
16 ˛0n
o nla ge, as he Uha e pai wise disjoin . No e also ha as he sa e pai wise disjoin ,
so a e he Zs o s2Œc. Now o 1sc, apply Co olla y 3.5 (3) o ind an . 1/-
clique S0
sK 1.GŒZ0/ such ha he e is a e ex zs2Zs NG.S0
s/and a e ex

P. Mo is 870
xs2.X [Y / NG.S0
s/. We dele e he S0
s om Z0and mo e o he nex index sC1o
inish i sDc.
Now choose some Y0Ysuch ha xs2X[Y0 o all s2Œc and
jY0jCjXjC X
s2Œc
.jRCsjC1/ DM:
This is easily done as jXjC jYj D ˛2nis linea and jXj;jRCsj  2n2=3 o all s2Œc,
which is much smalle han MDn7=8. By P oposi ion 4.1, he e is a K -diamond ee
Q
DD.Q
T ; Q
R; Q
†/ wi h Q
RDX[Y0and Q
†K 1.GŒW0/ a ma ching o . 1/-cliques
in W0W0. Ou diamond ee Djis hen ob ained by connec ing Q
Dand all he Cs2C.
In mo e de ail, o each s2Œc, he e exis s some hs2ssuch ha zs2UhsXhs. We
de ine
RjWD Q
R[[
s2Œc
.RCs[¹zsº/and †jWD Q
†[[
s2Œc
.†Cs[¹S0
sº[¹Shsº/;
whe e †Csis he se o in e io . 1/-cliques o Cs;S0
s2K 1.GŒZ0/ is he . 1/-
clique which o ms a clique wi h bo h zsand xsde ined abo e; and Shsis he . 1/-
clique co esponding o he se Xhs(which con ains zs) in Claim 8.5. We claim ha he e
exis s a diamond ee Djo o de Mwhich has Rjas a se o emo able e ices
and †jas a se o in e io . 1/-cliques. Indeed, we can o m he de ining auxilia y
ee Tjby s a ing wi h he o es o he disjoin union o Q
Tand he TCs o s2Œc, whe e
TCsdeno es he de ining ee o he K -diamond ee Cs. Fo each s2Œc, we hen add
a pa h o leng h 2 (wi h wo edges) be ween some e ex in V.TCs/and V. Q
T /. The edges
o his pa h co espond exac ly o he in e nal . 1/-cliques Shsand S0
sand hus he
e ices o his pa h co espond o xs,zsand some e ex in RCs Uhs o each s2Œc.
This de ines Djand so we upda e all he Uh o be UhnV.Dj/ o h2Œ` and kill
any indices h2ƒsuch ha ei he V.Dj/in e sec s Sho jXh V.Dj/j  2C n1=6.
We now need o check ha condi ions (1)–(3) hold o Dj. To see (1), no e ha Rj
con ains all he RCs o s2Œc and so in e sec s Xh o all h2Ss2Œc s. Mo eo e ,
aking as de ined a he end o inding he Cs, we ha e j[Ss2Œc sj.1 ˛=2/` and
jj ˛`=2, and so his con i ms (1). To see (2), no e ha he only imes we used e ices
o he Shwi h h2Œ` o cons uc Djwas when we added he Shs o s2Œc o he se
o in e io cliques. Thus we in e sec ed exac ly cCo hese wi h V.Dj/. Finally, (3)
o Djis implied by condi ions (i ) when we ound he Cs. Indeed, Rj Sh2Œ` XhD
Ss2Œc.RCs[¹zsº/and so o any index h ha does no lie in Ss2Œc ƒs(which has size
a mos C n1=2), we ha e
jV.Dj/ Xhj  X
s2Œc j.V .Cs/[¹zsº/ Xhj  C.n1=6 C1/ 2C n1=6:
This concludes he inding o Dj, and doing his o all j2Œ4  gi es he desi ed claim
and hence he p oposi ion.
Clique ac o s in pseudo andom g aphs 871
9. Concluding ema ks
In his pape , we showed ha a condi ion o ˇDo.pkn/ in an n- e ex .p; ˇ/-bijumbled
g aph gua an ees a KkC1- ac o . We conjec u e ha he same condi ion in ac gua an ees
any subg aph wi h maximum deg ee k.
Conjec u e 9.1. Fo any k2N2and c > 0 he e exis s an " > 0 such ha any n- e ex
.p; ˇ/-bijumbled g aph wi h ı.G/ cpn and ˇ"pknis k-uni e sal, ha is, gi en any
g aph Fon a mos n e ices, wi h maximum deg ee a mos k,Gcon ains a copy o F.
No e ha Co olla y 1.5 se les Conjec u e 9.1 o kD2. Fo k3, he bes known
esul comes om he spa se blow-up lemma o Allen, Bö che , Hàn, Kohayakawa and
Pe son [2] which gi es a condi ion o ˇDo.p.3kC1/=2n/ gua an eeing k-uni e sali y in
a.p; ˇ/-bijumbled g aph.
The conjec u e echoes he no ion ha a KkC1- ac o is he ‘ha des ’ maximum
deg ee kg aph o ind. This idea has mani es ed i sel in a ious o he se ings. Fo exam-
ple, we know om he heo em o Hajnal and Szeme édi (Theo em 1.1) ha any n- e ex
g aph Gwi h ı.G/ .k=.k C1//n con ains a KkC1- ac o and ha his is igh . Bollobás
and Eld idge [15], and independen ly Ca lin [19], conjec u ed ha he same minimum
deg ee condi ion ac ually gua an ees k-uni e sali y. This has been p o en o kD2; 3
[1,7,25] bu emains open in gene al. In he case o andom g aphs, Johansson, Kahn and
Vu [39] p o ed ha he h eshold o he appea ance o a KkC1- ac o is o he o de o
p
k.n/ WD n2=.kC1/.log n/2=.k2Ck/:
A ecen b eak h ough esul o F anks on, Kahn, Na ayanan and Pa k [28] implies ha
o any n- e ex g aph Fwi h maximum deg ee k, he h eshold o he appea ance o F
in G.n; p/ is a mos p
k.n/. No e ha his is no implying ha G.n; p/ is k-uni e sal whp
when pD!.p
k.n// as we can only gua an ee ha some ixed Fappea s whp. Howe e ,
he s onge e sion ha p
k.n/ is he h eshold o k-uni e sali y is belie ed o be ue
bu only e i ied o kD2[26].
One hing ha se s aside he pseudo andom se ing in s a k con as o he o he
se ings discussed abo e is ha i migh be possible o eplace a KkC1- ac o as he bench-
ma k o he ‘ha des ’ g aph o ind in he hos g aph, by a single copy o KkC1. Indeed,
a ious au ho s [22,27,53,64] ha e s ipula ed ha n- e ex KkC1- ee .p; ˇ/-bijumbled
g aphs exis wi h ˇD‚.pkn/. Such g aphs would wi ness he igh ness o bo h Theo-
em 1.4 and Conjec u e 9.1 o all alues o k2( aking DkC1in he se ing o
Theo em 1.4). Focusing on op imally pseudo andom g aphs ( ha is, ixing ˇD‚.ppn/
in .p; ˇ/-bijumbled g aphs), we expec o be able o ind KkC1- ee op imally pseudo-
andom g aphs wi h pD.n1=.2k1//. These a e only known o exis when kD2.
Indeed, we discussed he iangle- ee cons uc ion o Alon in he in oduc ion, and o he
cons uc ions [21,48] ha e also been gi en which a e (nea -)op imal. Fo k3, howe e ,
his emains a key challenge in he unde s anding o pseudo andom g aphs, wi h he bes
known gene al cons uc ion coming om a ecen imp o emen o Bishnoi, Ih inge and
Pepe [13] who gi e KkC1- ee op imally pseudo andom g aphs o densi y pD‚.n1=k/.
P. Mo is 872
Fu he in e es in inding dense such g aphs comes om a ecen ema kable connec ion
disco e ed by Mubayi and Ve s aë e [60] ha shows ha i , as we expec , he KkC1-
ee op imally pseudo andom g aphs wi h densi y pD.n1=.2k1//do exis , hen i
is possible o imp o e he lowe bound on he o -diagonal Ramsey numbe s o ma ch
he uppe bound and hus de e mine he asymp o ics o his ex emal unc ion. In de ail,
hey show ha i hese pseudo andom g aphs exis , hen he o -diagonal Ramsey num-
be is R.k C1; / D kCo.1/ as ends o in ini y. In ac , e en a cons uc ion wi h
pD!.n1=.kC1//would imp o e on he cu en bes known lowe bound on o -diagonal
Ramsey numbe s due o Bohman and Kee ash [14].
We conclude by no ing ha Theo em 1.2 is, in some sense, he i s esul o i s
kind, gi ing a igh condi ion on pseudo andomness o gua an ee he exis ence o a span-
ning s uc u e. Indeed, he case o Hamil on cycles emains an in iguing open p oblem.
K i ele ich and Sudako [52] conjec u ed ha a condi ion o Do.d/ is su icien in
.n; d; /-g aphs and p o ed he cu en ly bes known bound o
Do.log log n/2d
log n.log log log n/:
Fo hype g aphs o highe uni o mi y, one can easily gene alise he no ion o bijumbled-
ness in De ini ion 1.3 bu he pic u e becomes conside ably mo e complex. Indeed, i u ns
ou ha he only subg aphs ha one can gua an ee by imposing condi ions on bijumbled-
ness a e linea subg aphs, hose in which pai s o hype edges in e sec in a mos one
e ex. Building on p e ious wo k [23,47,55,56] mainly conce ned wi h dense hype -
g aphs ( he so-called quasi andom egime), Hiê
.p Hàn, Jie Han and he au ho [30,31]
ecen ly ga e he bes -known condi ions on pseudo andomness ha gua an ee di e en
linea subg aphs o hype g aphs. These include all ixed sized linea subg aphs as well
as F- ac o s o linea F(including pe ec ma chings) and loose Hamil on cycles. The
igh ness o hese esul s is unclea as no good cons uc ions a e known o F- ee pseu-
do andom hype g aphs. In gene al, he appea ance o subg aphs in spa se pseudo andom
(hype -)g aphs emains a ascina ing a ea which is a om being unde s ood.
Acknowledgmen s. Much o his wo k was done du ing a isi o he au ho o IMPA, Rio de Janei o,
B azil. I am g a e ul o bo h Ped o A aújo and Robe Mo is wi h whom I discussed many aspec s
o his p ojec , o hei hospi ali y, suppo and en husiasm. I am also g a e ul o my coau ho s om
p e ious p ojec s, Jie Han, Yoshiha u Kohayakawa and Yu y Pe son, o in oducing me o his a ea
and many o he echniques and app oaches used o ackle hese so s o p oblems. Finally, I am
g a e ul o he anonymous e e ee, o Tibo Szabó and again o Robe Mo is o p o iding many
help ul sugges ions aiding he p esen a ion and eadabili y o he pape .
Funding. The au ho was suppo ed by he Deu sche Fo schungsgemeinscha (DFG, Ge man
Resea ch Founda ion) unde Ge many’s Excellence S a egy - The Be lin Ma hema ics Resea ch
Cen e MATH+ (EXC-2046/1, p ojec ID: 390685689) and by a Wal e Benjamin ellowship o he
DFG - p ojec numbe 504502205.
Re e ences
[1] Aigne , M., B and , S.: Embedding a bi a y g aphs o maximum deg ee wo. J. London Ma h.
Soc. (2) 48, 39–51 (1993) Zbl 0796.05029 MR 1223891
Clique ac o s in pseudo andom g aphs 873
[2] Allen, P., Bö che , J., Hàn, H., Kohayakawa, Y., Pe son, Y.: Blow-up lemmas o spa se
g aphs. a Xi :1612.00622 (2016)
[3] Allen, P., Bö che , J., Hàn, H., Kohayakawa, Y., Pe son, Y.: Powe s o Hamil on cycles in
pseudo andom g aphs. Combina o ica 37, 573–616 (2017) Zbl 1399.05118 MR 3694704
[4] Allen, P., Bö che , J., Hladký, J., Pigue , D.: A densi y Co ádi–Hajnal heo em. Canad. J.
Ma h. 67, 721–758 (2015) Zbl 1316.05069 MR 3361011
[5] Alon, N.: Explici Ramsey g aphs and o hono mal labelings. Elec on. J. Combin. 1, a . 12,
8 pp. (1994) Zbl 0814.05056 MR 1302331
[6] Alon, N., Bou gain, J.: Addi i e pa e ns in mul iplica i e subg oups. Geom. Func . Anal. 24,
721–739 (2014) Zbl 1377.11013 MR 3213827
[7] Alon, N., Fische , E.: 2- ac o s in dense g aphs. Disc e e Ma h. 152, 13–23 (1996)
Zbl 0851.05068 MR 1388628
[8] Alon, N., F ankl, P., Huang, H., Rödl, V., Ruci´
nski, A., Sudako , B.: La ge ma chings in
uni o m hype g aphs and he conjec u e o E d˝
os and Samuels. J. Combin. Theo y Se . A
119, 1200–1215 (2012) Zbl 1242.05189 MR 2915641
[9] Alon, N., Kahale, N.: App oxima ing he independence numbe ia he #- unc ion. Ma h.
P og amming 80, 253–264 (1998) Zbl 0895.90169 MR 1603356
[10] Alon, N., Spence , J. H.: The p obabilis ic me hod. 4 h ed., Wiley Se ies in Disc e e Ma he-
ma ics and Op imiza ion, Wiley, Hoboken, NJ (2016) Zbl 1333.05001 MR 3524748
[11] Balogh, J., Lee, C., Samo ij, W.: Co ádi and Hajnal’s heo em o spa se andom g aphs.
Combin. P obab. Compu . 21, 23–55 (2012) Zbl 1241.05130 MR 2900047
[12] Balogh, J., Molla, T., Sha i zadeh, M.: T iangle ac o s o g aphs wi hou la ge independen
se s and o weigh ed g aphs. Random S uc u es Algo i hms 49, 669–693 (2016)
Zbl 1352.05141 MR 3570984
[13] Bishnoi, A., Ih inge , F., Pepe, V.: A cons uc ion o clique- ee pseudo andom g aphs. Com-
bina o ica 40, 307–314 (2020) Zbl 1463.05373 MR 4121148
[14] Bohman, T., Kee ash, P.: The ea ly e olu ion o he H- ee p ocess. In en . Ma h. 181, 291–
336 (2010) Zbl 1223.05270 MR 2657427
[15] Bollobás, B., Eld idge, S. E.: Packings o g aphs and applica ions o compu a ional complex-
i y. J. Combin. Theo y Se . B 25, 105–124 (1978) Zbl 0387.05020 MR 511983
[16] B ode , A. Z., F ieze, A. M., Suen, S., Up al, E.: Op imal cons uc ion o edge-disjoin pa hs
in andom g aphs. SIAM J. Compu . 28, 541–573 (1999) Zbl 0912.05058 MR 1634360
[17] B ouwe , A. E., Haeme s, W. H.: Eigen alues and pe ec ma chings. Linea Algeb a Appl.
395, 155–162 (2005) Zbl 1056.05097 MR 2112881
[18] Cap a a, A., Rizzi, R.: Packing iangles in bounded deg ee g aphs. In o m. P ocess. Le . 84,
175–180 (2002) Zbl 1042.68087 MR 1928953
[19] Ca lin, P. A.: Embedding subg aphs and colo ing g aphs unde ex emal deg ee condi ions.
Ph.D. hesis, Ohio S a e Uni e si y (1976) MR 2626461
[20] Cioab˘
a, S. M.: Pe ec ma chings, eigen alues and expansion. C. R. Ma h. Acad. Sci. Soc. R.
Canada 27, 101–104 (2005) Zbl 1110.05058 MR 2204683
[21] Conlon, D.: A sequence o iangle- ee pseudo andom g aphs. Combin. P obab. Compu . 26,
195–200 (2017) Zbl 1371.05259 MR 3603964
[22] Conlon, D., Fox, J., Zhao, Y.: Ex emal esul s in spa se pseudo andom g aphs. Ad . Ma h.
256, 206–290 (2014) Zbl 1285.05096 MR 3177293
[23] Conlon, D., Hàn, H., Pe son, Y., Schach , M.: Weak quasi- andomness o uni o m hype -
g aphs. Random S uc u es Algo i hms 40, 1–38 (2012) Zbl 1236.05137 MR 2864650
[24] Co adi, K., Hajnal, A.: On he maximal numbe o independen ci cui s in a g aph. Ac a
Ma h. Acad. Sci. Hunga . 14, 423–439 (1963) Zbl 0118.19001 MR 200185
[25] Csaba, B., Shokou andeh, A., Szeme édi, E.: P oo o a conjec u e o Bollobás and Eld idge
o g aphs o maximum deg ee h ee. Combina o ica 23, 35–72 (2003) Zbl 1046.05040
MR 1996626