Clique factors in pseudorandom graphs

© 2023 European Mathematical Society Published by EMS Press and licensed under a CC BY 4.0 license J. Eur. Math. Soc. 27, 801–875 (2025) DOI 10.4171/JEMS/1388 Patrick Morris Clique factors in pseudorandom graphs Received July 2, 2021; revised July 1, 2022 Abstract. An n-vertex graph is said to to be .p; ˇ/-bijumbled if for any vertex sets A; B V.G/, we have e.A; B/ DpjAjjBj˙ˇpjAjjBj: We prove that for any r2N3and c > 0 there exists an ">0such that any n-vertex .p; ˇ/- bijumbled graph with n2rN,p > 0,ı.G/ cpn and ˇ"pr1ncontains a Kr-factor. This implies a corresponding result for the stronger pseudorandom notion of .n; d; /-graphs. For the case of triangle factors, that is, when rD3, this result resolves a conjecture of Krivelevich, Sudakov and Szabó from 2004 and it is tight due to a pseudorandom triangle-free construction of Alon. In fact, in this case even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition of ˇDo.p2n/ actually guarantees that a .p; ˇ/-bijumbled graph Gcontains every graph on nvertices with maximum degree at most 2. Keywords. Pseudorandom graphs, clique factors, extremal graph theory Contents 1. Introduction .................................................... 802 2. Proof of main theorem ............................................. 806 3. Preliminaries .................................................... 817 3.1. Notation ................................................... 817 3.2. Properties of bijumbled graphs .................................... 818 3.3. Concentration of random variables ................................. 823 3.4. Perfect fractional matchings ...................................... 823 3.5. Almost perfect matchings in hypergraphs ............................. 825 3.6. Templates .................................................. 828 4. Diamond trees ................................................... 829 4.1. Scattered diamond trees ......................................... 831 5. Cascading absorption through orchards .................................. 834 5.1. Absorbing orchards ........................................... 835 5.2. Shrinkable orchards ........................................... 838 6. Shrinkable orchards of small order ..................................... 840 6.1. From orchards to systems ....................................... 840 Patrick Morris: Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain; [email protected] Mathematics Subject Classification (2020): Primary 05C35; Secondary 05C48, 05C70 P. Morris 802 6.2. Sufficient conditions for shrinkability ............................... 841 6.3. The existence of shrinkable orchards of small order ...................... 844 6.4. Controlling degrees relative to removable sets of vertices .................. 845 6.5. The existence of shrinkable orchards of larger order ..................... 847 7. Shrinkable orchards of large order ..................................... 848 7.1. A density condition which guarantees shrinkability ...................... 848 7.2. Popular diamond trees .......................................... 850 7.3. The existence of shrinkable orchards of large order ...................... 852 7.4. Preprocessing the orchard ....................................... 854 7.5. Completing the orchard ......................................... 857 7.6. The existence of shrinkable orchards of smaller order .................... 859 8. The final absorption ............................................... 860 8.1. Defining an absorbing structure ................................... 861 8.2. Finding an absorbing structure .................................... 863 9. Concluding remarks ............................................... 871 References ........................................................ 872 1. Introduction We say a graph Gcontains a Kr-factor if there is a collection of vertex disjoint copies of Krthat completely cover the vertex set of G. When rD3, we often refer to a K3-factor as a triangle factor. As a natural generalisation of a perfect matching in a graph, Krfactors are a fundamental object in graph theory with a wealth of results studying various aspects and variants, in particular exploring probabilistic [11,36,39,45,51], extremal [4,12,62,68], and algorithmic [18,42,44,46] considerations. However, unlike perfect matchings, it is not easy to verify whether a graph Gcontains a Kr-factor or not. Certainly it is necessary that the number of vertices of Gmust be divisible by rbut given this, it was proved by Schaeffer [43] (in the case rD3) and by Kirkpatrick and Hell [46] (in general) that determining whether a graph on n2rNvertices contains a Kr-factor is an NP-complete problem. Given that we cannot hope for a nice characterisation of graphs which contain Kr-factors, there has been a focus on providing sufficient conditions which are computationally easy to verify. One classical such theorem is due to Hajnal and Szemerédi [29] who showed that a Kr-factor is guaranteed if the host graph is sufficiently dense. The case of triangle factors was previously shown by Corrádi and Hajnal [24]. Theorem 1.1. If r2N3and Gis a graph on n2rNvertices with minimum degree ı.G/ .1 1=r/n, then Gcontains a Kr-factor. This theorem is tight, as can be seen, for example, by taking Gto be a complete graph with a clique of size n=r C1removed to leave an independent set of vertices, say I. One then has ı.G/ D.1 1=r/n 1and Gdoes not have a Kr-factor. Indeed, any copy of Krin a family of vertex disjoint Krs can use at most one vertex of Ibut a Kr-factor should contain n=r < jIjcopies of Kr. All examples verifying the tightness of Theorem 1.1 share some features with the graph given here. For example they contain much larger independent sets than almost all graphs of this density. Therefore, one might hope to capture more graphs having a Kr-factor by adding a condition that precludes the atypical behaviour of the extremal examples. Clique factors in pseudorandom graphs 803 This naturally leads us to the notion of pseudorandom graphs, which are, roughly speaking, graphs which imitate random graphs of the same density. The study of pseudorandom graphs, initiated in the 1980s by Thomason [65,66], has become a central and vibrant field at the intersection of combinatorics and theoretical computer science. We refer to the excellent survey of Krivelevich and Sudakov [53] for an introduction to the topic. One way of imposing pseudorandomness is through the spectral notion of the eigenvalue gap. This then leads to the study of .n; d; /-graphs Gwhich are d-regular n-vertex graphs with second eigenvalue . By second eigenvalue, what is actually meant is the second largest eigenvalue in absolute value, as follows. Given an n-vertex d-regular graph G, we can look at the eigenvalues of the adjacency matrix Aof Gwhich, as Ais a symmetric 0=1-matrix, are real and can be ordered as 1   n. The second eigenvalue is then defined to be WDmax ¹j2j;jnjº. It turns out that this parameter controls the pseudorandomness of the graph G, with smaller values of giving graphs that have stronger pseudorandom properties. More concretely, the relation is given by the following property of .n;d;/-graphs (see e.g. [53, Theorem 2.1]), which is known as the Expander Mixing Lemma and shows that controls the edge distribution between vertex sets. For any vertex subsets A; B of an .n; d; /-graph G, one has ˇˇˇˇ e.A; B/ d njAjjBjˇˇˇˇpjAjjBj;(1.1) where e.A; B/ WD j¹uv 2E.G/ Wu2A; b 2Bºj denotes the number1of edges in G with one endpoint in Aand the other in B. Note that d=n is the density of the graph G, and hence one would expect to see d njAjjBjedges between the vertex sets Aand Bin a random graph G. The pseudorandom parameter then controls the discrepancy from this paradigm. It follows from simple linear algebra (see e.g. [53]) that for an .n; d; /-graph, one has dalways and moreover, as long as dis not too close to n, say d2n=3, one has D.pd/. Thus, we think of .n; d; /-graphs with D‚.pd/ as being optimally pseudorandom. For example, it is known that random regular graphs are optimally pseudorandom .n; d; /-graphs with high probability2[16,67]. A prominent theme in the study of pseudorandom graphs has been to give conditions on the parameters, n,dand that guarantee certain properties of an .n; d; /-graph. For example, it follows easily from (1.1) that any .n; d; /-graph Gwith <d2=n contains a triangle as there is an edge in the neighbourhood of every vertex. In particular, any optimally pseudorandom graph with dD!.n2=3/must contain a triangle. Moreover, this condition is tight due to a triangle-free construction of an .n; d; /-graph due to Alon [5] with dD‚.n2=3/and D‚.n1=3/. Alon’s construction is optimally pseudorandom and Krivelevich, Sudakov and Szabó [54] generalised it to the whole possible 1Note that edges that lie in A\Bare counted twice. 2Here, and throughout, we say that a property holds with high probability if the probability that it holds tends to 1as the number nof vertices tends to infinity. P. Morris 804 range of densities. That is, for any dDd.n/ such that .n2=3/Ddn, they gave a sequence of infinitely many nand triangle-free .n0; d; /-graphs with n0D‚.n/ and D‚.d2=n/. In general, finding optimal conditions for subgraph appearance in .n;d;/- graphs seems hard. Indeed, the only tight conditions that are known are those for fixed size odd cycles [9,53]. With respect to spanning structures, it is only perfect matchings that have been well understood [17,20,53]. Whilst such questions are interesting in their own right, they also have implications in other areas of mathematics. As an example, we mention the beautiful connection given by Alon and Bourgain [6] (see also [2]) who used the existence of certain subgraphs in pseudorandom graphs to prove the existence of additive patterns in large multiplicative subgroups of finite fields. The purpose of this paper is to answer what has become one of the central problems in this area, by giving a tight condition for an .n; d; /-graph to contain a triangle factor. Theorem 1.2. There exists ">0such that any .n; d; /-graph with n23N,d > 0 and "d2=n contains a triangle factor. Theorem 1.2 was conjectured by Krivelevich, Sudakov and Szabó [54] in 2004. Focusing solely on optimally pseudorandom graphs, that is, setting D‚.pd/, Theorem 1.4 implies that any optimally pseudorandom graph with dD!.n2=3/contains a triangle factor. Comparing this to Theorem 1.1, we see that imposing pseudorandomness, which is easy to compute via the second eigenvalue, allows us to capture much sparser graphs which are guaranteed to contain a triangle factor. Theorem 1.2 (and the more general Theorem 1.4 below) conclude a body of work towards the conjecture of Krivelevich, Sudakov and Szabó, and the proof of the theorem, discussed in Section 2, builds upon the many beautiful ideas of various authors, which have arisen in this study. The first step towards the conjecture was given by Krivelevich, Sudakov and Szabó [54] themselves, who showed that "d3=.n2log n/ for some sufficiently small "is enough to guarantee a triangle factor. This was improved to  "d5=2=n3=2 by Allen, Böttcher, Hàn, Kohayakawa and Person [3] who also proved that the same condition guarantees the appearance of the square of a Hamilton cycle, a supergraph of a triangle factor. Recently, Nenadov [61] got very close to the conjecture, showing that "d2=.n log n/ guarantees a triangle factor. Concentrating solely on optimally pseudorandom graphs, these results imply that having degree dD!.n4=5.log n/2=5/,!.n3=4/ and !..n log n/2=3/respectively, guarantees the existence of a triangle factor. In a different direction, one can fix the condition that "d2=n for some small ">0 and prove the existence of other structures giving evidence for a triangle factor. Again, this was initiated by Krivelevich, Sudakov and Szabó [54] who proved that with this condition, one can guarantee the existence of a fractional triangle factor. That is, they showed that there is a function wwhich assigns a weight w.T / 2Œ0; 1 to each triangle Tin a pseudorandom graph Gand is such that for every vertex v2V.G/, the sum Pv2Tw.T / of the weights of triangles containing vis precisely equal to 1. Imposing ¹0; 1º-weights recovers the notion of a triangle factor and a fractional triangle factor is thus a natural relaxation. Another interesting result of Sudakov, Szabó and Vu [64] showed that when "d2=n, we have many triangles and these are well distributed in the .n;d;/-graph G. Clique factors in pseudorandom graphs 805 Indeed, they proved a Turán-type result showing that any triangle-free subgraph of such a graph Gmust contain at most half the edges of G. A more recent result due to Han, Kohayakawa and Person [34,35] shows that "d2=n guarantees the existence of a near triangle factor: there are vertex disjoint triangles covering all but n647=648 vertices of such an .n; d; /-graph. We will deduce Theorem 1.2 from a more general theorem (Theorem 1.4 below) which deals with Kr-factors for all r3and works with a larger class of pseudorandom graphs where we do not restrict solely to regular graphs. Indeed, we will work with the notion of bijumbledness, whose usage dates back to the original works of Thomason [65,66], and whose definition captures the key property of edge distribution, given for .n; d; /-graphs by (1.1). Definition 1.3. Let n2N,pDp.n/ 2Œ0; 1 and ˇDˇ.n; p/ > 0. An n-vertex graph GD.V; E/ is .p; ˇ/-bijumbled if for every pair of vertex subsets A; B V, one has ˇˇe.A; B/ pjAjjBjˇˇˇpjAjjBj:(1.2) Note that, due to (1.1), .n; d; /-graphs are .d=n; /-bijumbled. As with .n; d; /- graphs, we are interested in finding conditions on the parameters n,pand ˇthat guarantee the existence of certain subgraphs in n-vertex .p;ˇ/-bijumbled graphs. Our main theorem gives conditions for the existence of Kr-factors for all r3in this setting. Theorem 1.4. For every r2N3and c > 0 there exists an " > 0 such that any n-vertex .p; ˇ/-bijumbled graph with n2rN,p > 0,ı.G/ cpn and ˇ"pr1ncontains a Kr-factor. We remark that the condition that ı.G/ cpn is natural. Indeed, Definition 1.3 implies that almost all vertices will have degree at least cpn, and some lower bound on minimum degree is necessary to avoid isolated vertices. Theorem 1.2 follows directly from Theorem 1.4, and much of the context and past results discussed above have analogous statements when r4with many authors also working in the more general setting of .p; ˇ/-bijumbled graphs. In particular, for all r3, a condition of ˇDo.pr1n/ guarantees a copy of Kr, and before Theorem 1.4 the best condition known for ensuring a Kr-factor was ˇDo.pr1n=log n/ due to Nenadov [61]. Another result due to Han, Kohayakawa, Person and the author [32] appeared at roughly the same time as that of Nenadov and gave a condition of ˇDo.prn/ for a Kr-factor, which for r4 gives a stronger result than the previously best known condition of Allen, Böttcher, Hàn, Kohayakawa and Person [3]. Although this condition is weaker than Nenadov’s only when the bijumbled graph is very dense, it turns out that the proof methods of both results will be useful in proving Theorem 1.4. There is one key difference between the pictures for rD3and for r4: the tightness of the condition ˇDo.pr1n/ for both the clique and the clique factor when r4is unknown. We defer a more in-depth discussion of this to our concluding remarks (Section 9) and conclude this introduction by again focusing on the most interesting case of triangle factors where we know that Theorems 1.4 and 1.2 are tight due to the construction of Alon P. Morris 806 (and its generalisation to the whole range of densities by Krivelevich, Sudakov and Szabó) discussed above. Indeed, one of the reasons that the Krivelevich–Sudakov–Szabó conjecture (Theorem 1.2) has attracted so much attention is that it marks a distinct difference between the behaviour of random graphs and that of (optimally) pseudorandom graphs. In random graphs, we know that triangles appear at density roughly pDn1, whilst for triangle factors the threshold is considerably denser, namely pDn2=3.log n/1=3 [39] (see also recent results [37,40,41,63] that imply that this threshold is sharp). On the other hand, there exist triangle-free, optimally pseudorandom graphs with density roughly n1=3, but Theorem 1.4 asserts that any pseudorandom graph whose density is a constant factor larger than this is guaranteed to have not only a triangle but a triangle factor. Furthermore, it follows from Theorem 1.4 and (the proof of) a result of Han, Kohayakawa, Person and the author [33] that even more is true. Corollary 1.5. For every c > 0 there exists an ">0such that any n-vertex .p; ˇ/- bijumbled graph with ı.G/ cpn,p > 0 and ˇ"p2nis 2-universal. That is, given any graph Fon at most nvertices, with maximum degree 2,Gcontains a copy of F. In particular, any .n; d; /-graph Gwith "d2=n is 2-universal. Our proof of Theorem 1.4 incorporates discrete algorithmic techniques, probabilistic methods, fractional relaxations and linear programming duality, and the method of absorption. In the next section we discuss the proof in detail and reduce the problem to proving two intermediate propositions and a lemma. These will then be proven in what follows after developing the necessary theory. Remark. An accompanying conference version [59] of this work deals solely with the setting of Theorem 1.2. More technical parts of the proof are omitted there and we hope that it serves as a gentle introduction to the present paper. 2. Proof of main theorem The proof of Theorem 1.4 rests on the shoulders of the previous results [3,32–35,54,61] working towards the conjecture of Krivelevich, Sudakov and Szabó. Indeed, it is fair to say that the solution of the conjecture would not have been possible without the insights and ideas of the many authors who tackled this problem. In this section, we discuss these as well as our novel ideas and lay out the key concepts and scheme of the proof. In doing so, we will reduce the theorem to several intermediate results, whose proofs will be the subject of the rest of the paper. Our proof, like some of its predecessors [3,32,61], works by the method of absorption. It turns out that finding many vertex disjoint copies of Krin a .p; ˇ/-bijumbled graph G as in Theorem 1.4 is easy. This follows from a simple consequence of Definition 1.3 which guarantees that any small linear sized set of vertices contains a copy of Kr; see e.g. Corollary 3.5 (2) for a precise statement. Therefore we can greedily choose copies of Kr to be in our Kr-factor and continue this process until we are left with some small leftover set of vertices L, where small means of size at most "rn, say. However, at this point we Clique factors in pseudorandom graphs 807 get stuck: we have no way of guaranteeing the existence of a Krin Land so we do not know how to get a larger set of vertex disjoint copies of Kr. The idea of absorption is to put aside an absorbing set of vertices which can absorb the leftover vertices Linto aKr-factor. That is, before running this greedy process to build a Kr-factor, we find some special set of vertices XV.G/ which has the property that for any small set of vertices LV.G/ nX, there is a Kr-factor in GŒX [L (under the trivial divisibility constraint that rj.jXjCjLj/). If we can find such an Xin G, then we can put it to one side and run the greedy argument to cover almost all the vertices which do not lie in X, with vertex disjoint copies of Kr. We can then use the absorbing property to absorb the leftover vertices Land get a full Kr-factor. This leaves the challenge of defining some structure in Gwhich has this absorbing property and finding such a structure (on some vertex set X) in G. The building blocks of our absorbing structure will be subgraphs that we call Kr-diamond trees. In words, a Kr-diamond tree DD.T; R; †/ is the graph obtained by taking a tree Tand replacing each edge e2E.T / by a copy of K rC1whose degree r1vertices are the vertices of e and whose degree rvertices are new and distinct from previous choices; see Figure 1for an example. The following definition formalises this notion. R={ } Σ=  T=D= (T, R, Σ) DD.T; R; †/ T D RD ¹º †D Fig. 1. An example of a K3-diamond tree DD.T; R; †/ of order 9shown on the left. The removable vertices Rare the larger vertices of Dand the interior cliques †are the edges given in grey. The auxiliary tree Tis depicted on the right. Definition 2.1. AKr-diamond tree Dof order min a graph Gis a tuple DD.T; R; †/ where Tis an (auxiliary) tree of order m(i.e. with mvertices), RV.G/ is a subset of mvertices of Gand3†Kr1.G/ is a set of m1copies of Kr1in Gwith the following property. There are bijective maps WV.T / !Rand WE.T / !†such that the copies of Kr1in †are pairwise vertex disjoint in Gand they are also disjoint from R, i.e. V.S/ \V .S0/D ; and V.S/ \RD ;for all S; S02†; for all eDuv 2E.T /, we have V..e// NG..u// \NG..v//, that is, the r1clique .e/ 2Kr1.G/ can be extended to a copy of Krin Gby adding the vertex .u/ and likewise with .v/. 3Here and throughout, we use Kr1.G/ to denote the family of .r 1/-cliques in G. P. Morris 808 We refer to Ras the set of removable vertices of Dand to †as the set of interior cliques of D. We define the vertices of Dto be all the removable vertices and the vertices in interior cliques. That is, V.D/WD.SS2†V .S// [R. Finally, we define the leaves of the diamond tree to be the vertices which are images of leaves in Tunder . Note that a Kr-diamond tree of order mhas exactly .m 1/r C1vertices. Krivelevich [51] used K3-diamond trees in an absorption argument for triangle factors in random graphs which is often cited as one of the first appearances of the absorption method. Nenadov [61] also used this idea in his result that got within a log-factor of Theorem 1.4. The utility of these subgraphs in absorption arguments comes from the following key observation which shows that they can contribute to a Kr-factor in many ways. Observation 2.2. Given a Kr-diamond tree DD.T; R; †/ in G, for any removable vertex v2Rthere is a Kr-factor of GŒV .D/n¹vº. Indeed, consider uD1.v/ in V.T / and the map 'WE.T / !V.T / n¹uºwhich maps each edge eof Tto the vertex in ewhich has the larger distance from uin T. Then 'is a bijection and taking the copies of Kron .e/ [.'.e// for each edge e2E.T / gives the required Kr-factor. See Figure 2for some examples. Fig. 2. Some examples of K3-factors found after removing a removable vertex from the K3diamond tree in Figure 1(see Observation 2.2). Observation 2.2 works for any underlying auxiliary tree T. It turns out that in the .p; ˇ/-bijumbled graphs Gwe are interested in, one can find Kr-diamond trees of any order up to linear size. Indeed, one can use the argument of Krivelevich [51] to construct these or a different argument due to Nenadov [61]. The method of Nenadov gives diamond trees whose auxiliary tree is a path, whilst the argument of Krivelevich gives no control over the underlying auxiliary tree which defines the diamond tree found. As a key part of our argument, we will need to prove the existence of diamond trees which have extra structure, as we discuss shortly. In order to utilise the absorbing power of diamond trees, we need to group them together in collections. The following definition of an orchard captures how we do this. Definition 2.3. We say a collection OD ¹D1; : : : ; Dkºof pairwise vertex disjoint Krdiamond trees in a graph Gis a .k; m/r-orchard if there are kdiamond trees in the Clique factors in pseudorandom graphs 809 collection and each has order at least mand at most 2m. We refer to kas the size of the orchard, and to mas its order.4We denote by V .O/the vertices featuring in diamond trees in O, that is, V.O/DSi2Œk V.Di/. Finally, if O0Ois a subset of diamond trees in an orchard O, we call O0asuborchard of O. The term orchard here is supposed to be instructive, indicating that this is a ‘neat’ collection of diamond trees that all have a similar order and are completely disjoint from one another. As noted in Observation 2.2, a Kr-diamond tree can contribute to a Kr-factor in many ways. By grouping together many vertex disjoint Kr-diamond trees into a .k; m/r-orchard such that km D.n/, we get a structure with a strong absorbing property, as the following lemma shows. We say a .K; M /r-orchard Oabsorbs a .k; m/r-orchard Rif there is an ..r 1/k; M /r-suborchard O0Osuch that there is a Kr-factor in GŒV.R/[V.O0/. Lemma 2.4. For any r2N3and 0 < ; < 1 there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n. Let Obe a .K; M /rorchard in Gsuch that KM n. Then there exists a set BV.G/ such that jBj  p2r4nand Oabsorbs any .k; m/r-orchard Rin Gwith V.R/\.B [V.O// D ;; k K=.8r/ and kM mK: (2.1) Morally, Lemma 2.4 says that large orchards absorb small orchards. Here, by large we refer to both the size and the order of the orchards. Indeed, the second condition in (2.1) shows that the larger orchard has to have a larger size than the smaller orchard. This is the critical condition when we want absorption between orchards of similar order. The third condition shows that the ratio between the orders of the orchards is constrained by the ratio of the sizes. That is, the larger Ois compared to Rwith respect to their sizes, the smaller Rcan be than Owith respect to their orders. This will be the critical condition when we want absorption between orchards of (polynomially) different orders. The first condition in (2.1) simply states that in order for Oto absorb R, we need that Ravoids some small set Bof bad vertices. This will be easy to implement in applications. Lemma 2.4 will be proven in Section 5.1. It provides us with an absorption property between two distinct orchards. We will also need an absorption property within orchards themselves, showing that we can find a large suborchard which hosts a Kr-factor in G. Given Observation 2.2, in order to find Kr-factors on suborchards it suffices to find copies of Krwhich traverse sets of removable vertices. We therefore make the following definition. Definition 2.5. Given a .k; m/r-orchard OD ¹D1; : : : ; Dkºin a graph G, the Krhypergraph generated by O, denoted HDH.O/, is the r-uniform hypergraph with 4Note that we abuse notation slightly here. Indeed, we refer to the order of an orchard although this may not be uniquely defined by the orchard. We take the convention that when we refer to the order of an orchard, we simply fix one of the possible orders arbitrarily, noting that these possible orders differ by a factor of at most 2. P. Morris 816 D ;. Therefore, by Lemma 2.4,Qiabsorbs any suborchard POi1with jPj  k1 i1 if k1 i1k i=.8r/ and k1 i1mik imi1. Now as miDnmi1and n1=.8r/ for sufficiently large n, it suffices to show that k1 i1k in. To see this, note that since ˛n ki1mi1and kimi2˛n, we have ki12˛n mi1D2˛n1C mi2kin2k in ; and using this as a lower bound for k i, it suffices to show that k i12n2 : This is certainly true as ki1kt˛n1=8 > n4= , recalling that 4= D4 from (2.2). This shows that (iv) holds for all iand concludes the proof of the claim and hence the proof of Theorem 1.4. We remark that this proof scheme builds on that of Nenadov [61] (which in turn is influenced by that of Krivelevich [51]), who proved that ˇ"p2n=log nsuffices for a triangle factor in an n-vertex .p; ˇ/-bijumbled graph. Indeed, Nenadov also uses a result akin to Lemma 2.4, albeit between orchards whose orders only differ by a constant factor. His absorbing structure then contains a sequence of ‚.log n/ orchards whose order increases by a constant factor along the sequence. Therefore the last orchard in the sequence contains constantly many diamond trees of large order (of order ‚.n=log n/). These can be fully absorbed because any three large sets host a transversal triangle and so transversal triangles between removable sets can be greedily found, completing a triangle factor in the last step. Similarly, the .k;m/3-orchards used in his argument are not imposed to be shrinkable but can be seen to host a triangle factor on all but o.k/ of the diamond trees by again applying a greedy approach of finding transversal triangles. The necessity of the log nin the condition of Nenadov is thus due to needing ‚.log n/ orchards in the absorbing structure and thus requiring slightly stronger properties of the .p;ˇ/-bijumbled graph, for example the existence of triangles on sets of .n=log n/ vertices. The key challenge in this paper is then to prove Propositions 2.8 and 2.9. Both results rely heavily on a technique we develop to provide the existence of Kr-diamond trees in which we have some control over the set of removable vertices. This control is rather weak; we cannot guarantee that any fixed vertices appear as removable vertices but we can give some flexibility over the choice of removable vertices. See Proposition 4.1 for the technical statement of what we prove. In order to prove Proposition 2.8, we build on the approach of Han, Kohayakawa and Person [34,35]. Indeed, their result showing the existence of a near Kr-factor (covering all but some n1"0vertices) in .n; d; /-graphs can be seen as a step towards proving the existence of shrinkable orchards of order 1. The approach involves showing the existence of a near-perfect matching in a subhypergraph H0of the Kr-hypergraph generated by V.G/. In order to do this, one needs to carefully choose H0and this is done by finding Clique factors in pseudorandom graphs 817 many fractional Kr-factors in Gwhich do not put too much weight on (copies of Krcontaining) any given edge. Therefore, the methods of Krivelevich, Sudakov and Szabó [54], who proved the existence of singular fractional Kr-factors, become pertinent. They use the power of linear programming duality to prove that certain expansion properties guarantee the existence of fractional factors. In our setting, it turns out that we need several distinct arguments to prove the existence of shrinkable orchards of different orders. We follow the scheme of using fractional factors (in fact, fractional perfect matchings in Krhypergraphs) but need to adapt the method for different applications and we rely crucially on probabilistic methods to actually prove the existence of orchards which satisfy the necessary expansion properties. It can be seen that Proposition 2.8 alone (for all orders of orchards) would lead via the same proof scheme to a condition of ˇ"pr1n=.log log n/. In order to close the gap and achieve Theorem 1.4, Proposition 2.9 is necessary. To prove this, we appeal to a different absorption argument whose roots go back to an ingenious argument of Montgomery [57,58] in his work on spanning trees in random graphs. The approach, sometimes called the absorption-reservoir method, uses a bipartite graph, which we call a template (see Section 3.6) as an auxiliary graph to define an absorbing structure. This idea was previously used by Han, Kohayakawa, Person and the author [32] to find clique factors in pseudorandom graphs, and we used this approach again in our result on 2universality [33]. Here we combine this idea with the absorbing power of orchards and prove Proposition 2.9 with a three-stage algorithm which finds the absorbing structure necessary. The rest of this paper is organised as follows. In the next section, we run through the necessary preliminaries, providing the background theory that we will use. This includes properties of bijumbled graphs, the study of perfect fractional matchings via linear programs, probabilistic methods and the absorption-reservoir method of Montgomery [57,58]. In Section 4we then study what kinds of diamond trees we can guarantee in our bijumbled graph. The key result here is Proposition 4.1, which will be crucial at various points in our proof. We then turn to addressing the necessary results for the cascading absorption through the orchards in Section 5. We prove Lemma 2.4 in Section 5.1 and discuss Proposition 2.8 in Section 5.2, reducing it to two intermediate propositions which tackle small and large order shrinkable orchards separately. We go on to prove the existence of shrinkable orchards of small order in Section 6and large order in Section 7. Finally, we prove Proposition 2.9 which provides the final absorption in the proof of Theorem 1.4, in Section 8. 3. Preliminaries 3.1. Notation For a graph Gand r2N, we define Kr.G/ to be the set of copies of Krin G. When referring to (a copy of) a clique S2Kr.G/, we will identify the copy with the set of vertices that hosts it. That is, we think of S2Kr.G/ as a set of rvertices which P. Morris 818 host a clique in Grather than the copy of the clique itself. Given a set †Kr.G/ of r-cliques, we use the notation V.†/ to denote all vertices that feature in cliques in †, i.e. V.†/ WD SS2†S. We call †Kr.G/ amatching of cliques if it is composed of pairwise vertex disjoint cliques, that is, S\S0D ; for any S¤S02†. Now given subsets S; W V.G/ of vertices, we let NG W.S/ denote the common neighbours of the vertices in Swhich lie in W. That is, NG W.S/ WD .Tv2SNG.v// \W. Likewise, we define degG W.S/ WD jNG W.S/jto be the cardinality of this neighbourhood. If the graph Gis clear from context then we drop the superscripts. Also if SD ¹uºis a single vertex, we will drop the set brackets. We say that a clique S2Kr.G/ traverses vertex subsets U1; : : : ; UrV .G/ if there exists some ordering of Sas SD ¹u1; : : : ; urºsuch that ui2Uifor all i2Œr. Note that when the Uiare pairwise disjoint, this simplifies to requiring that Scontains one vertex from each Ui. However, at times we will deal with not necessarily disjoint sets Uiand so this more delicate definition is needed. If His an r-uniform hypergraph for some r2Nand v; u 2V.H /, then degH.v/ denotes the number of edges in Hcontaining v, and codegH.u; v/ denotes the number of edges of Hwhich contain both uand v. If the hypergraph His clear from context, we drop the superscripts. If His an r-uniform hypergraph with r3and Jis a 2-uniform graph on the same vertex set V.H/, then HJdenotes the subhypergraph of Hgiven by all edges of Hthat contain some edge of J. For graphs Q Gand Gon the same vertex set with Q Ga subgraph of G, we let GnQ G denote the graph on V.G/ given by the set of edges that feature in Gbut not in Q G. If H0and Hare r-uniform hypergraphs with H0a subgraph of H, then HnH0is defined similarly. We use xDy˙zto denote that xyCzand xyz, and we say a property holds with high probability (whp, for short) if the probability that it holds tends to 1 with some parameter n(usually the number of vertices of a graph). Finally, we drop ceilings and floors unless necessary, so as not to clutter the arguments. 3.2. Properties of bijumbled graphs Here we collect some properties of bijumbled graphs. These range from simple consequences of Definition 1.3 to more involved statements catered to our purposes. We begin by showing that we can assume that the graphs we consider have an arbitrarily large number of vertices. Fact 3.1. Given any r2N3and n02N, there exists " > 0 such that any n-vertex .p;ˇ/- bijumbled graph Gwith n2rN,p > 0,ı.G/ < .1 1=r/n and ˇ"pr1nmust have nn0. Proof. Let " > 0 be such that " < 1=.2n0r/. Suppose for a contradiction that there exists an n-vertex .p; ˇ/-bijumbled graph with ı.G/ < .1 1=r/n,ˇ"pr1nand n < n0. Then due to the upper bound on the minimum degree of G, there exists a vertex u2V.G/ Clique factors in pseudorandom graphs 819 and a set W2V.G/ n¹uºsuch that jWj D n=r and degG W.u/ D0. However, from Definition 1.3, we have e.¹uº; W / pjWj"pr1nrn rpn r.1 "pnr/ pn 2r > 0; a contradiction. Fact 3.1 shows that by choosing ">0sufficiently small, we guarantee that any bijumbled graph Gwe are interested in either has a large number of vertices or has ı.G/ .1 1=r/n, in which case Theorem 1.1 implies the existence of a Kr-factor and we are done. We will use this at various points in our argument and simply state that we choose ">0sufficiently small to force nto be sufficiently large. The following well known fact states that bijumbled graphs cannot to be too sparse. Fact 3.2. For any r2N3and any C > 0, there exists an " > 0 such that if Gis an n-vertex .p; ˇ/-bijumbled graph with p > 0 and ˇ"pr1n, then pC n1=.2r3/ C n1=3. Proof. Let " > 0 be such that "21=.32C 2r3/and small enough that we can assume that (i) n9; (ii) p1=16. Indeed, from Fact 3.1, we can choose "so that (i) holds and C n1=.2r3/ < 1=16 and so we are done if we are not in case (ii). We will also restrict to the case that (iii) p1=.2n/. To see that we can do this, suppose for a contradiction that there exists a .p; ˇ/-bijumbled graph GD.V; E/ with pn < 1=2. We appeal to Definition 1.3 and upper bound 2e.G/ D e.V; V / by pn2C"pr1n2< n 1. Hence there must be some vertex u2Vwhich is isolated in G. But then defining WWD Vn¹uº, the lower bound of Definition 1.3 gives e.¹uº; W / p.n 1/ "pr1npn1pn.1=2 "pn/ > 0, a contradiction. We now turn to proving the statement in full generality. Our aim is to construct large (disjoint) vertex subsets Uand Wsuch that e.U; W / D0. We do this in the following greedy fashion. We initiate the process by setting UD ; and WDV.G/. Now, whilst jWj3n=4, there exists some u2Wwith degW.u/ 2pjWj2pn. Indeed, this follows from Definition 1.3 because X w2W degW.w/ De.W; W / pjWj2C"pr1jWj  2pjWj2: We then choose such a u, delete it from Wand add it to Uand also remove NW.u/ from W. Let Uand Wbe the resulting sets after this process terminates. It is clear that e.U;W / D0as we have removed all the neighbours of each vertex u2Ufrom Wduring the process. We also claim that jWjn=2 and U1=.16p/. Indeed, the last step removed at P. Morris 820 most 1C2pn vertices from W. Due to our assumptions (i) and (ii), we see that 1C2pn < n=4 and so as Whad size greater than 3n=4 before this step, we indeed have jWj  n=2 as the process terminates. To see the lower bound on the size of U, note that if this was not the case, then jV.G/ nWj D ˇˇˇ[ u2U .¹uº[NG.u//ˇˇˇX u2Uj¹uº[NG.u/jjUj.1 C2pn/ 1 16p Cn 8n 4; using assumption (iii) in the last inequality. This implies that jWj3n=4, a contradiction as the process terminated. Thus jWj  n=2,jUj  1=.16p/ and from Definition 1.3, we have 0De.U; W / pjUjjWj"pr1npjUjjWj; implying that p2r31=.32"2n/. Given our upper bound on ", this implies that p C n1=.2r3/ as required. Our first lemma shows that few vertices have degree much smaller or much larger than expected with respect to a given set. Lemma 3.3. For any r2N3and >0there exists an ">0such that if Gis an n-vertex .p; ˇ/-bijumbled graph with ˇ"pr1nthen for WV .G/: (i) The number of vertices v2V.G/ such that degW.v/ < pjWj=2 is less than p2r4n2 jWj: (ii) For any qsuch that 2p q1, the number of vertices v2V.G/ such that degW.v/ > qjWjis less than p2r2n2 q2jWj: Proof. Fix ">0such that 4"2< . We prove only (ii); the proof of (i) is both similar and simpler. We set Bto be the set of ‘bad’ vertices, i.e. vertices vsuch that degW.v/ > qjWj. Thus we have qjBjjWj< e.B; W / pjBjjWjC"pr1npjBjjWj; using the definition of Band (1.2). Rearranging gives jBj<"2p2r2n2 .q p/2jWj; and using pq=2 gives the desired conclusion with our choice of ". Next, we state some further consequences of Definition 1.3, showing that we can find cliques traversing large enough subsets of vertices. The following lemma is very general Clique factors in pseudorandom graphs 821 and will be used at various points in our argument. Due to its generality, there are some technical features. Whilst these are all necessary for certain parts of our argument, we do not need all of these at once. In fact, for easy reference, we list the consequences of Lemma 3.4 that we will use in Corollary 3.5. This may also serve to digest the statement of Lemma 3.4, seeing how it is applied in practice. Lemma 3.4. For any r2N3and 0 < ˛ < 1=22r there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n. Suppose that there are integers xi,i2Œr C1, such that x1xrC10and for some r2Œr, one has xiCxiC1C2i 2r 2for all 1ir.(3.1) Define yWDmax ¹xiC1CiWi2Œrº. Then for any collection of subsets UiV .G/ such that jUij  ˛pxinfor all i2Œr C1 and for any subgraph Q Gof Gwith maximum degree less than ˛2pyn, defining G0WD GnQ G, there exists a clique S2Kr.G0/traversing U1; : : : ; Ursuch that degG0 Uj.S/ ˛prjUjjfor rC1jrC1. Proof. Fix " > 0 small enough to apply Lemma 3.3 (i) with WD ˛2=.24r r/. Further, fix yand Q Gas in the statement, setting G0WD GnQ G. We will prove inductively that for iD1; : : : ; r, there exists an i-clique Si2Ki.G0/traversing U1; : : : ; Uisuch that degG0 Uj.Si/.p=4/ijUjjfor all jwith iC1jrC1. Note that Sris the desired copy of Krin the statement, using ˛1=4rhere. So fix some i2Œr. If i2, by induction we deduce the existence of Si1as claimed and for ijrC1, define WjUjso that WjWD NG0 Uj.Si/. If iD1, we simply set WjWD Ujfor all j. We thus have jWjj  p 4i1 jUjj  ˛41ipxjCi1n(3.2) for ijrC1. Now we appeal to Lemma 3.3 (i) and conclude that for each jwith iC1jrC1, there is some set BjV.G/ such that degG Wj.v/ pjWjj=2 for all v2V.G/ nBjand jBjj  p2r4n2 jWjj4i1p2r3ixjn ˛˛p2r3ixiC1n 4ir˛pxiCi1n 4irjWij 2r : (3.3) Here, we used (3.2) in the second inequality, the definition of and the fact the xj xiC1in the third, (3.1) in the fourth and (3.2) once again in the final inequality. We can thus conclude from (3.3) that there exists a vertex wi2Wisuch that wi…Bjfor all iC1jr1. We claim that choosing SiDSi1[¹wiºcompletes the inductive step. Indeed, Si2Ki.G0/as wiwas chosen from the common neighbourhood of Si1in G0. Also, fixing some iC1jr1, we see that NG.wi/intersects WjDNG0 Uj.Si1/ in at least pjWjj=2 vertices. Furthermore, at most ˛2pyn˛2pxiC1Cin˛ 22r pxjCinpjWjj=4 P. Morris 822 edges adjacent to wilie in Q G, using the definition of y, the upper bound on ˛, the fact that xjxiC1and (3.2). Therefore we can conclude that for all iC1jr, we have degG0 Uj.Si/degG0 Wj.Si/pjWjj=4 .p=4/ijUjj, as required. This completes the induction and the proof. We now collect some easy consequences of Lemma 3.4 for reference later in the proof. Corollary 3.5. For any r2N3and 0 < ˛ < 1=22r there exists an ">0such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n: (1) Let Q Gbe any subgraph Q Gof Gwith maximum degree less than ˛2pr1n. (i) For any U1; : : : ; Ur1V .G/ such that jUij  ˛pn for i2Œr 1, there exists an .r 1/-clique S2Kr1.G nQ G/ traversing the Ui. (ii) For any U1; : : : ; UrV .G/ such that jU1j  ˛p2r4nand jUij  ˛n for 2 ir, there exists an r-clique S2Kr.G nQ G/ traversing the Ui. (2) For any U1; : : : ; UrV .G/ such that jU1j  ˛pr1n,jUij  ˛pn for 2ir2 and jUr1j;jUrj  ˛n, there exists an r-clique S2Kr.G/, traversing the Ui. (3) For any W0; W1; W2V .G/ such that jW0j;jW1j;jW2j  ˛n, there exists an S2 Kr1.GŒW0/ such that degWi.S/ ˛2pr1nfor jD1; 2. Proof. Fix " > 0 small enough to apply Lemma 3.4. This is predominantly a case of plugging in the values and checking the conditions of Lemma 3.4. For part (1), we let G0D GnQ G. Then for (1)(i), we take rDr2,xiD1for 1irC1and yDr1. We thus see that for i2Œr,xiCxiC1C2i D2C2i 2r 2and xiC1CiD1Cir1 Dy. Therefore taking Uifor 1ir1with jUij˛pn (and defining UrC1DUrD Ur1), Lemma 3.4 gives us an .r 2/-clique S02Kr1.G0/traversing U1; : : : ; Ur2 such that degG0 Ur1.S0/˛2pr1n > 0 (here Fact 3.2 shows positivity). Therefore choosing any vertex v2NG0 Ur1.S0/and fixing SDS0[¹vºgives the required clique. The other cases are similar. For part (1)(ii), we fix rDr1,x1D2r 4,xiD0for 2irC1and yDr1. Again, it is easily checked that the conditions on the xiare all satisfied and so applying Lemma 3.4 (fixing UrC1DUr) gives an .r 1/-clique S0in G0 traversing U1; : : : ; Ur1such that S0has a nonempty G0-neighbourhood in Ur. Therefore adding any vertex in this neighbourhood to S0gives the required r-clique S2Kr.G0/. For part (2), we fix rDr1,x1Dr1,xiD1for all isuch that 2ir2 and xr1DxrDxrC1D0. We also let Q Gbe the empty graph and so GDG0. Now note that for rD3, we have x1D2and x2D0and so x1Cx2C2D4D2r 2, whilst for r4, we have x1Cx2C2DrC22r 2. Conditions (3.1) for 2irDr1 can be similarly checked. Therefore Lemma 3.4 gives an .r 1/-clique S02Kr1.G/ traversing U1; : : : ; Ur1such that NG Ur.S0/¤ ; and so as above, we extend S0to the required r-clique S. Finally, for part (3) we fix rDr1,xiD0for all 1irand define our sets as UiDW0for i2Œr 1 and UrDW1,UrC1DW2. Applying Lemma 3.4 then directly gives the required .r 1/-clique S2Kr1.GŒW0/ (again here Q Gis taken to be empty). Clique factors in pseudorandom graphs 823 3.3. Concentration of random variables We will use the following well-known concentration bounds (see e.g. [38, Theorem 2.1, Corollary 2.4 and Theorem 2.8]). Theorem 3.6 (Chernoff bounds). Let Xbe the sum of a set of mutually independent Bernoulli random variables and let DEŒX. Then for any 0 < ı < 3=2, we have PŒX .1 Cı/ eı2=3 and PŒX .1 ı/ eı2=2: Furthermore, if x7, then PŒX x ex. 3.4. Perfect fractional matchings Given an r-uniform hypergraph H, a fractional matching in His a function fW E.H/ !R0such that PeWv2ef .e/ 1for all v2V .H/. We say the fractional matching is perfect if PeWv2ef .e/ D1for all v2V .H/. The value of a fractional matching f is jfj WD Pe2E.H / f .e/: The maximum value jfjover all choices of fractional matching fof H, we call the fractional matching number of H, which we denote by .H /. Afractional cover of His a function gWV.H / !R0such that for all e2E.H /, one has Pv2eg.v/ 1. The value of a fractional cover gis jgj WD Pv2V.H / g.v/. The fractional cover number of H, denoted .H/, is then the minimum value of a fractional cover gof H. For an r-uniform hypergraph H, the fractional matching number of Hcan be encoded as the optimal solution of a linear program. Taking the dual of this linear program gives another linear program which outputs the fractional cover number as an optimal solution. The duality theorem from linear programming thus tells us that .H/ D.H / for any hypergraph H. Using this, as well as the so called ‘complementary slackness conditions’ that follow from the duality theorem, one can derive the following simple consequences (see e.g. [50, Proposition 2] or [35, Proposition 2.4]). Proposition 3.7. For any r-uniform hypergraph Hon Nvertices, the following hold: (1) .H/ N=r, with equality if and only if there exists a perfect fractional matching in H. (2) .H/ .H/ where .H/ denotes the size of the largest matching in H. (3) If gWV.H/ !R0is a fractional cover and UV.H /, then g0WDgjUWU!R0is a fractional cover of HŒU  and hence jg0jDPu2Ug.u/ .H ŒU / D.HŒU /. (4) If gWV.H/ !R0is an optimal fractional cover, i.e. jgj D .H/, then .H/  jWj=r where WWD ¹v2V .H/ Wg.v/ > 0º. We now give two lemmas, exploring some simple conditions which guarantee the existence of a perfect fractional matching. Lemma 3.8. Suppose His an N-vertex, r-uniform hypergraph such that given any vertex v2V.H/ and any subset WV.H/ n ¹vºof at least N=.2r/ vertices, there exists P. Morris 824 an edge in Hcontaining vand r1vertices of W. Then Hhas a perfect fractional matching. Proof. Suppose for a contradiction that Hdoes not have a perfect fractional matching. Thus, by Proposition 3.7 (1), if we take gWV.H/ !R0to be an optimal fractional cover of Hso that jgj D .H/ D.H / we have jgj< N=r. Hence, if we order the vertices in decreasing weight order according to g, we see by Proposition 3.7 (4) that g.w/ D0, where wis the final vertex in this order. Take WV.H/ n¹wºto be the set of N=.2r/ vertices preceding win the order. Then by the condition of the lemma, there exists an edge using wand r1vertices of W. Since g.w/ D0, there is some vertex w0in W with g.w0/1=.r 1/. Therefore all vertices preceding Win the order (as well as w0) have at least this weight and in total jgj  NN=r r1N=r; a contradiction. Given a vertex subset UVWDV.H / in a hypergraph H, a fan focused at Uin His a subset FE.H/ of edges of Hsuch that je\UjD1for all e2Fand e\e0\.V nU / D;for all e¤e02F. In words, each edge of a fan intersects Uin exactly one vertex and outside of U, the edges in a fan are pairwise disjoint. The size of a fan is simply the number of edges in the fan. If UD¹uºis a single vertex, we simply refer to a fan focused at u. Lemma 3.8 shows that if Hhas the property that the link of every vertex vhas no large independent sets, then it must have a perfect fractional matching. In fact, we do not necessarily need such an expansion property to hold locally at every vertex and can instead focus on subsets of vertices, if we have an added condition that every vertex has a large enough fan focused at it. This is the content of the following lemma. Lemma 3.9. Suppose His an N-vertex, r-uniform hypergraph and there exists rM N=.2r/ such that (i) for all v2V.H/ there is a fan focused at vin Hof size M; (ii) for every subset W0V.G/ with jW0j D Mand every subset W1V.G/ nW0with jW1j  N=.2r/, there exists an edge of Hwith one vertex in W0and the other r1 vertices in W1. Then Hhas a perfect fractional matching. Proof. We start by noticing that (ii) leads to the following two consequences: (a) For all UV.H/ with jUjD.r 1/M , fixing V0WDV .H/ nUwe find that for all U0V0such that jU0jDM, there is a fan of size N=r Mfocused at U0in H ŒV 0. (b) Every subset of at least N=r vertices of Hinduces an edge in H. Indeed, for U0as in (a) we can build the fan FU0focused at U0greedily. Whilst jFU0j  N=r M, we see that WWD V .G/ n.V .FU0/[U0[U / has size at least N.N=r M /.r 1/ M.r 1/M N.2r 1/N=.2r/ N=.2r/; Clique factors in pseudorandom graphs 825 using MN=.2r/ here. Hence we can find an edge using one vertex of U0and r1 vertices of Wwhich extends the fan FU0. Condition (b) also follows easily because taking W0to be a set with N=r vertices, we find that for any W00 W0with jW00j D M, there is an edge containing a vertex in W00 and r1vertices of W0nW00 from (ii). Now we turn to the main proof. We fix gWV.H / !R0to be an optimal fractional cover and suppose for a contradiction that jgj< N=r. We deduce the existence of a vertex w2V.H/ with g.w/ D0and a fan Fwfocused at wof size M. Taking U1WDS¹en¹wºW e2Fwº, we have jU1j D .r 1/M and Pu2U1g.u/ M. Now consider V0WD V.H / nU1. If .HŒV 0/ N=r Mthen we can conclude that Pv2V0g.v/ N=r Mfrom Proposition 3.7 (3), which implies that jgj  N=r, a contradiction. Hence .HŒV 0/ < N rMDN0M r;(3.4) where N0WDjV0jDN.r 1/M . We fix g0WV0!R0to be some optimal fractional cover of HŒV 0with jg0j D .HŒV 0/. By Proposition 3.7 (4), we therefore deduce that there is some set U2V0with jU2jDMand g0.u0/D0for all u02U2. By (a) there exists a fan FU2of size N=r Mfocused at U2in HŒV 0. Taking ZWD S¹eWe2FU2ºnU2, we have jZj D .r 1/.N=r M / and similarly to before, using the fact that for each edge e2FU2we have Pv2eg0.v/ 1and g0.u0/D0for all u02U2, we can conclude that Pz2Zg0.z/  jFU2j D N=r M. Finally, we look at V00 WD V0nZ. We have N00 WD jV00j D N0.r 1/.N=r/ C .r 1/M and using (b) and Proposition 3.7 (2), we find that .HŒV 00/ N00 N=r rDN0C.r 1/M rN r: Hence, by Proposition 3.7 (3), we deduce that Pv002V00 g0.v00/.N 0C.r 1/M /=r N=r. Combining this with the lower bound on the sum of g0values on Zimplies that jg0j D .HŒV 0/ .N 0M /=r, contradicting (3.4). 3.5. Almost perfect matchings in hypergraphs It is well known that hypergraphs that have roughly regular vertex degrees and small codegrees contain large matchings. This is often referred to as Pippenger’s Theorem but there are in fact a family of similar results, all following from the “semi-random” or “nibble” method (see e.g. [10, Section 4.7]). Here we use the following explicit version which follows directly from a result of Kostochka and Rödl [49]. Theorem 3.10. For any integers r3and K4there exists 0> 0 such that for all 0the following holds. If His a r-uniform hypergraph on Nvertices such that (1) for all vertices v2V.H/, we have deg.v/ D.1 ˙Kp.log /=/; (2) for all u¤v2V.H/, we have codeg.u; v/ 1=.2r1/, then Hhas a matching covering all but at most 1=r Nvertices. P. Morris 832 iD0; 1. Indeed, we can find Mgreedily by applying Corollary 3.5 (3) (with WiDU2i for iD0; 1; 2) repeatedly, adding an .r 1/-clique Sto Mand removing its vertices from U2after each application. While jMj  ˛n, we have jU2j  ˛n and so we are indeed in a position to apply Corollary 3.5 (3) throughout the process. Now once we have found M, for each S2Mand for iD0; 1, let Ni.S/ WDNUi.S/, that is, the set of vertices in Uiwhich form a Krwith S. By construction we have jN0.S/j  dfor each Sin Mand so j¹.v; S/ 2U0MWv2N0.S/ºj  jMjdD˛nd: Hence, as jU0jhas size ˛n (as we imposed at the start of the proof), by averaging, there exists a vertex v02U0and a subset †of dcliques in Msuch that v0is in N0.S/ for all S2†. We can now construct our diamond star greedily, with v0as the image of the large degree vertex. Sequentially, for each clique Sin †, choose a vertex uin N1.S/ which has not been previously chosen and add the copy of K rC1on S,v0and uto the diamond star (adding uto R). As N1.S/ dfor all S2†M, there is always an option for uand so this process succeeds in building the required diamond star. Our next lemma follows the scheme of Krivelevich [51] to construct large diamond trees. We adapt his proof to guarantee that the diamond tree obtained is scattered. Lemma 4.5. For any r2N3and 0 < ˛ < 1=22r there exists an " > 0 such that the following holds for any n-vertex .p;ˇ/-bijumbled graph Gwith ˇ"pr1n, fixing dWD ˛2pr1n. For any 2z˛n and any pair of disjoint vertex subsets U; W V.G/ such that jUj;jWj  4˛rn, there exists a d-scattered Kr-diamond tree Dsc D.Tsc; Rsc; †sc/ of order msuch that zmzCd,Rsc Uand †sc Kr1.GŒW / is a matching of .r 1/-cliques in GŒW . Proof. Our proof is algorithmic and works by building a diamond tree forest, that is, a set of pairwise vertex disjoint diamond trees. At each step of the algorithm, we will add to one of the trees in our forest, boosting the degree of a vertex in the underlying auxiliary tree by d, using Lemma 4.4. By discarding trees when the sum of the orders of the trees gets too large, we will show that one of the trees in our forest will eventually obtain the desired order after finitely many steps of the algorithm. The details follow. Initiate the process by fixing U0Uto be an arbitrary subset of ˛n vertices, W0D ;Wto be empty and D1;: : :;D`with `D˛n to be the diamond trees which are defined to be the single vertices in U0. That is, for i2Œ`, the Kr-diamond tree DiD.Ti; Ri; †i/ corresponds to an auxiliary tree Tiwhich is just a single vertex and thus Riis also a single vertex and †iis empty. In general, at each step of the process we will have a family D1; : : : ; D`(for some `2N) of vertex disjoint Kr-diamond trees such that for each i, the diamond tree DiD.Ti;Ri; †i/is d-scattered, has RiU0and †iGŒW0. Furthermore, we will have U0DSi2Œ` Riand W0DSi2`V.†i/Wand maintain throughout ˛n  jU0j  2˛n and jW0j  2.r 1/˛n. Now at each step, given such a set U0and family D1; : : : ; D`, we apply Lemma 4.4 with U1DUnU0and U2DWnW0, noting that the conditions on the size of Uand Win Clique factors in pseudorandom graphs 833 the statement of the lemma and the imposed conditions on the size of U0and W0throughout the process indeed allow Lemma 4.4 to be applied. Thus, we find a Kr-diamond star DD.T ; R; †/of order dC1with centre v02U0,Rn¹v0º  UnU0and †Kr1.GŒU2/ a matching of .r 1/-cliques. As U0is the union of the removable vertices of the family of diamond trees, there is some i02Œ` such that v02Ri0. We then update Di0by adjoining the diamond star to the tree at v0, we add all the vertices of Rto U0, and all the vertices of the .r 1/-cliques in †to W0. Now if there is a Kr-diamond tree among the (new) family D1; : : : ; D`which has order at least z, we take such a diamond tree as Dsc and finish the process. If not, then we look at the size of U0. If jU0j< 2˛n, we continue to the next step. If jU0j  2˛n, then we sequentially discard arbitrary Kr-diamond trees DjD.Tj; Rj; †j/from the family. That is, we choose a Dj in the family, delete Rjfrom U0and delete the vertices that belong to .r 1/-cliques in †jfrom W0. We continue discarding diamond trees until jU0j  2˛n. Note that as jRjj  z˛n for all j, the updated U0at the end of this discarding process will have size at least ˛n as required. We then move to the next step. All the diamond trees in our family are d-scattered throughout the process and also W0, as the set of vertices featuring in interior cliques of a family of Kr-diamond trees whose orders add up to less than 2˛n, has size less than 2.r 1/˛n throughout. It is also clear that as the order of any diamond tree in our collection grows by at most d in each step, the order of the diamond tree which is found by the algorithm will be at most zCd. It only remains to check that the algorithm terminates but this is guaranteed because the number of diamond trees is decreasing throughout the process. Indeed, we never add new diamond trees to the family and every ˛n=dsteps we have to discard at least one diamond tree from the family. If the algorithm does not terminate after finding an appropriate Dsc, then eventually we will be left with just one diamond tree D1in the family, but at this point the order of D1would be at least ˛n z, contradicting that the algorithm is still running. X={ } Y={ } XD YD Fig. 6. A6-scattered K3-diamond tree. Using Lemmas 4.4 and 4.5 we can now deduce Proposition 4.1. P. Morris 834 Proof of Proposition 4.1.Fix " > 0 small enough to apply Lemmas 4.4 and 4.5 and small enough to force nto be sufficiently large in what follows. Let us first deal with the case when zdWD˛2pr1n. Here, we arbitrarily partition Uinto U0and U1of size at least ˛n, fix U2DWand apply Lemma 4.4 to get a Kr-diamond star DD.T ; R; †/ of order 1Cdwith RUand †Kr1.GŒW / a matching of .r 1/-cliques in W. Let x2Rbe the only non-leaf vertex in Rand define XD ¹xº. Further, let YRnXbe an arbitrary subset of z1vertices. Now taking WV .T /!Rand WE.T /!†to be the defining bijective maps for D, note that for any Y0Y, the set ¹1.v/ Wv2Y0[Xº  V .T /spans a subtree (or rather a substar) of T, say T. Therefore, taking DD.T; X [Y0; †/ where †WD ¹.e/ We2E.T /ºdefines a Krdiamond tree with removable vertices Y0[X. Therefore (1)–(3) of the proposition are all satisfied. When d< z ˛n, the proof is similar. We apply Lemma 4.5 to get a d-scattered Kr-diamond tree Dsc D.Tsc; Rsc; †sc/as given by the lemma and define XRsc to be the non-leaves of Dsc. See Figure 6for an example. In order to bound jXjand prove property (2), we appeal to Lemma 4.3 which gives jXj  jRscj2 d1zCd2 d12z d ; using zdin the final inequality. We note that for nlarge (using Fact 3.2) we have d4, implying that jXjz=2. We fix YRsc nXto be an arbitrary subset of size zjXjand claim that conditions (1)–(3) of the proposition are all satisfied. Indeed, it remains only to prove (3) and this follows similarly to above, by taking sub-diamond-trees of Dsc. In detail, fix some Y0Yand let RDY0[X. Then if sc WV.Tsc/!Rsc and sc WE.Tsc/!†sc are the defining bijective maps for Dsc, then the set ¹1 sc .v/ Wv2Rºof vertices spans a subtree TTsc. Indeed, we simply deleted leaves from Tsc, namely 1 sc .x/ for x2Rsc nY0. Taking †D¹sc.e/ W e2E.T /º, we conclude that DD.T; R; †/ is the desired diamond tree. 5. Cascading absorption through orchards In this section we discuss orchards in our .p; ˇ/-bijumbled graphs. We begin in Section 5.1 by proving Lemma 2.4 which details conditions for when one orchard absorbs another. In Section 5.2, we then discuss the existence of shrinkable orchards, addressing Proposition 2.8 which tells us that we can find shrinkable orchards of all desired orders in the graphs we are interested in. The proof of Proposition 2.8 requires many ideas and two distinct approaches. Therefore, we defer the majority of the work to later sections and simply reduce the proposition here, splitting it into two ‘subpropositions’ which will be tackled separately. Recall that Lemma 2.4 and Proposition 2.8 were the two ingredients we needed to prove the cascading absorption through constantly many orchards in the proof of Theorem 1.4. Clique factors in pseudorandom graphs 835 5.1. Absorbing orchards Recall the definition (Definition 2.3) of an orchard and that we say a .K; M /r-orchard O absorbs a.k; m/r-orchard Rif there is an ..r 1/k; M /r-suborchard O0Osuch that there is a Kr-factor in GŒV.R/[V.O0/. In this section we prove Lemma 2.4, restated below for convenience, which is a generalisation of [61, Lemma 3.5]. The lemma gives some sufficient conditions for an orchard to be able to absorb another orchard. Lemma 2.4 (restated). For any r2N3and 0 < ;  < 1 there exists an ">0such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n. Let O be a .K; M /r-orchard in Gsuch that KM n. Then there exists a set BV.G/ such that jBj  p2r4nand Oabsorbs any .k; m/r-orchard Rin Gwith V.R/\.B [V.O// D ;; k K=.8r/ and kM mK: (5.1) Our proof scheme follows that of [33] which gives a polynomial time two-phase algorithm for finding the necessary Kr-factor. The algorithm is a simple greedy algorithm and works by absorbing each diamond tree Bin the small orchard R, one at a time. In more detail, for each diamond tree Bin R, we find r1diamond trees D1; : : : ; Dr12Osuch that there is a copy of Krtraversing the sets of removable vertices of Band the diamond trees D1; : : : ; Dr1. This implies that there is a Kr-factor in GŒV .B/[V.D1/[[V.Dr1/ (see Observation 2.2) and so we can add the Di to the suborchard O0, forbid them from being used again, and move to the next diamond tree B02R. Note that typically, we expect to succeed with this process. Indeed, the set of removable vertices of diamond trees in Ois linear in size (and remains linear even after forbidding diamond trees D2Oused for previous B2R) and so a typical vertex has .pn/ neighbours among this set of removable vertices. Hence, appealing to Corollary 3.5 (1)(i) which states that sets of size .pn/ host copies of Kr1, we can expect to find a copy of Kr1in the neighbourhood of a typical removable vertex of B2R which lies on the removable vertices of diamond trees in O. As long as this copy of Kr1 traverses sets of removable vertices of distinct diamond trees in O, we will succeed. With a few extra ideas and a bit of preprocessing (for example partitioning Ointo r1suborchards at the start), this intuition holds true and we can successfully greedily start to build O0. In fact, if kM is small compared to pn, we can fully form O0in this way and no second phase is necessary. However, if kM is large compared to pn we may run into trouble as with this greedy approach, it may be the case that the neighbourhood of a removable vertex vof a diamond tree B2Rhas too small a size by the time we come to considering B. Indeed, as we run this greedy process, we forbid the diamond trees (and their removable vertices) which we add to O0from being used again. This could result in vhaving much fewer than pn neighbours in the removable vertices of diamond trees in (the remainder of) Oand so we have no guarantee of finding a copy of Kr1in this neighbourhood. P. Morris 836 We resolve this issue by running a two-phase algorithm and reserving half of Ofor the second phase. The key point is that if a diamond tree Bfails in the first round then it must be the case that all of the removable vertices of Bhave small neighbourhoods amongst the removable vertices of diamond trees in O. Given that throughout the process, many diamond trees in Owill remain available to use, pseudorandomness (more precisely, Corollary 3.5 (1)(ii)) tells us that the number of vertices that do not have large enough neighbourhoods is relatively small. Hence, as each diamond tree B2Rwhich failed in the first phase has a set of removable vertices which are atypical in this way, we can upper bound the number of diamond trees in Rthat fail in the first round. This upper bound will then be used to show that in the second phase, we are successful with each diamond tree, as throughout the second round, the number of removable vertices being forbidden (due to being used to absorb other diamond trees in R) will be negligible and so the neighbourhoods of vertices amongst the removable vertices of diamond trees in the half of Oreserved for this second phase will remain large. Proof of Lemma 2.4.We fix ˛; 0<2 23r r2and choose " > 0 small enough to apply Lemma 3.3 with 3.3 D0and Corollary 3.5 with ˛3.5 D˛. Let OD ¹D1; : : : ; DKºbe the .K; M /r-orchard with each DiD.Ti; Ri; †i/being a Kr-diamond tree of order between Mand 2M . We start by arbitrarily partitioning Ointo 2.r 1/ suborchards of size as equal as possible so that ODS2.r1/ jD1Ojand each Ojis a .Kj; M /r-orchard with KjDK 2.r1/ ˙1K 2r . For j2Œ2.r 1/, we let YjWD [ iWDi2Oj Ri be the set of removable vertices of the diamond trees which feature in the jth suborchard. Note that jYjjKjMKM=.2r/ n=.2r/ for each j2Œ2.r 1/. We define Bto be the set of vertices v2VnV .O/such that for some j2Œ2.r 1/, degYj.v/ < pjYjj=2. By Lemma 3.3 (i), we have jBj<2.r 1/0p2r4n2 minjjYjjp2r4n; due to our lower bound on the size of the jYjjand our upper bound on 0. Now as in the statement of the lemma, consider a .k; m/r-orchard RD¹B1; : : : ; Bkº of diamond trees whose vertices lie in Vn.B [V.O//. For i02Œk, let Qi0be the set of removable vertices of the diamond tree Bi0. We will show that for each i02Œk, there exist distinct indices i1Di1.i0/; : : : ; ir1Dir1.i0/2ŒK such that there is a copy of Kr which traverses the sets Qi0and Ri1;: : :;Rir1, where Ri1is the set of removable vertices of Di1and likewise for i2; : : : ; ir1. Now, from Observation 2.2, for such an r-tuple Bi0, Di1; : : : ; Dir1, there is a Kr-factor in GŒV .Bi0/[V.Di1/[[V.Dir1/. We will prove that one can choose such indices i1; : : : ; ir1for each i02Œk in such a way that no i2ŒK is chosen more than once. That is, for i0¤j02Œk, the sets ¹i1.i0/; : : : ; ir1.i0/º and ¹i1.j 0/; : : : ; ir1.j 0/ºare disjoint. Therefore our suborchard O0Ocan simply be defined to be the union of all the choices of Dij.i0/for i02Œk and j2Œr 1. Clique factors in pseudorandom graphs 837 We now show how to find the indices i1.i0/; : : : ; ir1.i0/for each i02Œk. We will achieve this via the following simple algorithm. We initiate the first round of the algorithm with O0D ;,IDŒk,PjDOjand ZjDYjfor 1jr1. Note that the Ojfor rj2.r 1/ do not feature in these definitions. This is because we will not use any diamond trees that lie in S2.r1/ jDrOjin this first round. Now the algorithm runs as follows. For i0D1; : : : ; k; we check if there exists some set ¹Dij2PjWj2Œr 1º such that there is a Krtraversing Qi0and the sets of removable vertices Ri1; : : : ; Rir1. If this is the case then we delete Dijfrom Pjand add it to O0for j2Œr 1 and we also delete Rijfrom Zjfor all j2Œr 1. Furthermore, we delete i0from Iand move to the next index i0C1(or finish this round if i0Dk). If it is not the case that such diamond trees exist in the orchards Pj, then we simply leave i0as a member of Iand move on to the next index. At the end of the first round, we have some set Iof indices remaining. We define tWD jIjat this point. We will now use diamond trees in the orchards Ojwith rj 2.r 1/ to absorb these remaining diamond trees Bi0with i02I. Thus we reset the process, setting PjDOjCr1and ZjDYjCr1for all j2Œr 1. We then follow the same simple process in the second round as we did in the first, running through the (remaining) i02Iin order and trying to find an appropriate set ¹Dij2PjWj2Œr 1º of diamond trees at each step. We claim that in this second round, we can find such a set for every i02Iand so by the end of the second round, the set Iis empty and O0is such that GŒV .R/[V.O0/ hosts a Kr-factor. In order to prove this, our analysis splits into two cases. First consider when kM <pn 16r . In this case, the second round is not even necessary as all indices succeeded in the first round. Indeed, note that every time we are successful for an index i0, we delete at most 2M vertices from each of the Zj. Therefore, at any instance in the first round of the process, any vertex vwhich is not in Bhas degZj.v/ pjYjj 22kM pn 4r 2kM pn 8r for all j2Œr 1, using our lower bound on the jYjjand our upper bound on kM . But then, by Corollary 3.5 (1)(i) (applied in this instance with Q Gbeing the empty graph and G0DG), there exists a copy of Kr1traversing the sets NZj.v/ for 1jr1. When vis any vertex in the removable set of vertices Qi0for some diamond tree Bi0in the process, this gives a copy of Krtraversing Qi0and some sets of removable vertices Rij for diamond trees Dij2Pj,j2Œr 1, as desired. In this way, we see that the process succeeds in every step of the first round to find a suitable ¹ij.i0/Wj2Œrºfor each i02Œk and Iis empty (i.e. tD0) at the end of the round. Note that we have used here the fact that the vertices of Qi0are not in B. When pn 16r kM mK, the second round may be neccesary and we start with estimating t, the size of Iafter the first round. Now note that at the end of the first round, before we reassign the sets Zjto removable vertices in diamond trees in OjCr1for j2Œr 1, if we take QDSi02IQi0, then there is no Krtraversing Qand the sets Z1; : : : ; Zr1. Indeed, otherwise there would be an i02Iand a vertex v2Qi0Q P. Morris 838 which is contained in a Krwith a set of vertices ¹vij2ZjWj2Œr 1º. This contradicts that for the index i0we failed to find a suitable set of ijin the first round. Thus, at the end of the first round, there is no Krtraversing Q, and the Zj,j2Œr 1. Moreover, jZjj  KM 2r 2kM KM 4r n 4r ; using the upper bound on kfrom (5.1) and the fact that at most 2M vertices are deleted from Zjevery time we are successful with an index i02I. Thus, we can conclude from Corollary 3.5 (1)(ii) that at the end of the first round, tm < jQj< ˛p2r4n. Therefore t < ˛p2r4n m˛p2n m16˛rpK 16˛rpn M pn 16rM ; where we have used our lower and upper bounds on kM to give an upper bound on pn=m in the third inequality, the fact that KM nin the fourth inequality and our upper bound on ˛in the final inequality. We now turn to analyse the second round. Using our upper bound on t, we can upper bound the number of vertices deleted in each Zjthroughout the second round, and using this we find that for any vertex vnot in B, any j2Œr 1 and at any point in the second round, degZj.v/ pjYjCr1j 22tM pn 4r pn 8r pn 8r : Thus we can repeat the argument used for the case when kM was small, seeing that at every step in the second round we are successful in finding an appropriate set of ijfor j2Œr 1 for each i02I. This completes the proof. 5.2. Shrinkable orchards Here we are concerned with the existence of shrinkable orchards in pseudorandom graphs and verifying Proposition 2.8, which we restate below for the convenience of the reader. We also encourage the reader to remind themselves of Definitions 2.5 and 2.7 as well as Observation 2.6. Proposition 2.8 (restated). For any r2N3and 0 < ˛;  < 1=212r there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n and any vertex subset UV.G/ with jUjn=2. For any m2Nwith 1mn7=8 there exists a -shrinkable .k; m/r-orchard Oin GŒU  with k2Nsuch that ˛n km 2˛n. In order to prove Proposition 2.8, we will appeal to the methods of Sections 3.4 and 3.5. We will use Theorem 3.12 to reduce the problem to establishing the existence of perfect fractional matchings in the appropriate Kr-hypergraphs and we will then employ Lemmas 3.8 and 3.9 to find these perfect fractional matchings. In order that our hypergraph has the desired properties to apply these lemmas, we need to choose the diamond trees which define our orchard carefully. Clique factors in pseudorandom graphs 839 It turns out that different arguments are needed for finding shrinkable orchards of different orders. In Section 6we show how to find shrinkable orchards of small order, establishing the following intermediate proposition. Proposition 5.1. For any r2N3and 0 < ˛;  < 1=23r there exists an ">0such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1nand any vertex subset UV.G/ with jUj  n=2. For any m2Nwith 1mmin ¹pr2n12r3; n7=8º; there exists a -shrinkable .k; m/r-orchard Oin GŒU  with k2Nsuch that ˛n km  2˛n. In Section 7we then address shrinkable orchards with large order, which results in the following. Proposition 5.2. For any r2N3and 0 < ˛;  < 1=212r there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1nand any vertex subset UV.G/ with jUj  n=2. For any m2Nwith pr1nmn7=8; there exists a -shrinkable .k; m/r-orchard Oin GŒU  with k2Nsuch that ˛n km 2˛n. The proof of Proposition 2.8 is basically immediate from Propositions 5.1 and 5.2 but we spell it out nonetheless. Proof of Proposition 2.8.We split into a case analysis based on the density pof our graph G. First consider pn1=.10r/. Then we claim that pr2n12r3n7=8 and so the desired -shrinkable orchard of all orders up to n7=8 can be derived from Proposition 5.1. Indeed, we have pr2n12r3n1r2 10r 2r3and 1r2 10r 2r3 > 1 1 10 1 40 D7=8; due to our upper bound on (and lower bound on r). When p < n1=.10r/, we have pn2r3again due to our upper bound on . Hence we can apply Proposition 5.1 to find -shrinkable orchards of orders mn7=8 such that m<pr1npr2n12r3and apply Proposition 5.2 to find -shrinkable orchards with orders msuch that pr1nmn7=8. This settles all cases, giving the proposition. In both cases, a simpler argument works for the extreme cases, that is, when the order is small in Proposition 5.1 or when the order is large in Proposition 5.2. Extra ideas are then needed to push the approaches, extending the ranges of the two propositions so that they meet and cover all desired orders. In more detail, an easier form of Proposition 5.1 can cover orders which get close to pr1n(see Proposition 6.5). Again the separation required depends on , explicitly mpr1n1r3. This is already enough to cover all P. Morris 840 desired orchard orders when pis large. On the other hand, a basic form of the argument for large order orchards gives shrinkable orchards of order at least pr1nwhen pis large and of order at least p1rwhen pis smaller (see Proposition 7.3). Interestingly, Fact 3.2 implies exactly that p1rD.pr2n/ always and so proves that when pis small (close to the lower bound of .n1=.2r3//) and our bijumbled graph is sparse, both the simpler arguments for small orders and large orders as well as their extensions are needed. Indeed, using the simpler version, Proposition 6.5, for small orders and the full power of Proposition 5.2 leaves a small gap in the orders, and so does using Proposition 5.1 in conjunction with the easier Proposition 7.3. In order to help the reader through the next two sections, in both cases we begin by presenting the easier weaker versions of the statements we need. This then lays the foundation for the full proofs and allows us to discuss the more technical aspects needed to push the ranges for which we can prove the existence of shrinkable orchards. 6. Shrinkable orchards of small order Our first argument for proving the existence of shrinkable orchards works provided the order of the orchard is not too large, establishing Proposition 5.1. Before embarking on this we have to go through several steps. Firstly, in Section 6.1, we generalise the theory of shrinkable orchards built up in Section 2, allowing slightly more flexibility for our consequent proofs. In Section 6.2, we then use the theory of perfect fractional matchings to give conditions that guarantee an orchard is shrinkable. In Section 6.3, we show how this immediately implies the existence of shrinkable orchards of small order. However, this falls short of Proposition 5.1 and in the rest of this section we push the ideas to extend the range of orders we can cover, showing how to cleverly choose diamond trees of our orchard in Section 6.4, which allows us to prove the full Proposition 5.1 in Section 6.5. 6.1. From orchards to systems We begin by generalising our definitions slightly, allowing us to work not just with orchards but also with set systems. Definition 6.1. Given a graph Gwe say a set ƒ2V.G/ of pairwise disjoint subsets is a .k; m/-system if m jQj  2m for each Q2ƒand jƒj D k. That is, a .k; m/-system is just a family of kdisjoint vertex sets of size between mand 2m. Now given a .k; m/-system ƒin a graph G, the Kr-hypergraph generated by ƒ, denoted HDH.ƒIr/, is the r-uniform hypergraph with vertex set V.H/ Dƒand with ¹Qi1; : : : ; Qirº 2 ƒ rforming a hyperedge in Hif and only if there is a copy of Kr traversing the sets Qi1; : : : ; Qirin G. Finally, for 0 <  < 1, we say a .k; m/-system ƒin a graph Gis -shrinkable (with respect to r) if there exists a subsystem ƒof size at least k such for any subsystem 0, there is a matching in HWD H.ƒ n0Ir/ covering all but k1of the vertices of H. Clique factors in pseudorandom graphs 841 Note that given a .k; m/r-orchard Owe can define a .k; m/-system ƒas the sets of removable vertices of diamond trees in O. That is, ƒWD ¹RDWD2Oº. Then the Kr-hypergraphs generated by Oand ƒcoincide, i.e. H.ƒIr/ DH.O/, and Ois - shrinkable if and only if ƒis -shrinkable. However, Definition 6.1 allows us slightly more flexibility, giving us the ability to focus on subsets of removable vertices. The next observation highlights this and although the result is trivial, it will be important for our proofs. Observation 6.2. Suppose r3,0<<1and OD¹D1;: : :; Dkºis a .k;m/r-orchard in a graph Gwith Ribeing the set of removable vertices of Difor i2Œk. Then if ƒD ¹Q1; : : : ; Qkºis some .k; m0/-system (for some m0) such that QiRifor i2Œk and ƒis -shrinkable (with respect to r), then Ois also -shrinkable. It will become clear why such a relaxation is useful for us and thus why we make this switch to working with set systems. 6.2. Sufficient conditions for shrinkability We now explore the conditions on set systems which guarantee shrinkability. We begin by giving some local conditions on a set system which guarantee that it is shrinkable given that it lies in the pseudorandom graphs we are interested in. Lemma 6.3. For any r2N3and 0 < ˛;  < 1=.2rr2/there exists an ">0such that the following holds for any n-vertex .p;ˇ/-bijumbled graph Gwith ˇ"pr1n. Suppose ƒ2V.G/ is a .k; m/-system such that mn7=8,km ˛n,pk nand (1) there exists a subsystem ƒsuch that jj  k and YWD S¹PWP2ƒnº, for every Q2ƒthere exists a vertex v2Qsuch that degG Y.v/ ˛pkmI (2) for any u2SP2ƒPand Q2ƒ, we have degG Q.u/ pr1n1r3. Then ƒis -shrinkable with respect to r. Let us make a few remarks before proving the lemma. Firstly, note that condition (1), despite the slight technicality necessary to avoid dependence on sets in , is a natural condition. Indeed, we are requiring that at least one vertex in each set is well connected to the other sets and has a constant fraction of the degree that we would expect on average. Condition (2) is perhaps more mysterious as it is unclear why having an upper bound on the degree of a vertex relative to another set in the system is advantageous. The point is that this guarantees that each of the vertices has a neighbourhood that is well-spread across the other sets of the set system, without being too concentrated on any other single set. Within the proof this necessity manifests itself as we appeal to Theorem 3.12 and so will need that when we disallow edges between certain pairs of sets from being used (dictated by the graph J), we do not significantly alter the graph in which we work. The details follow in the proof. P. Morris 848 Let O2be an arbitrary suborchard of O1with jO2j D .1 C/k. Moreover, let ƒ0D ¹SDWD2O2ºbe the ..1 C/k; m=4/-system defined by the distinguished subsets of removable vertices for the Kr-diamond trees in O2. Now due to (6.3), Lemma 6.4 gives the existence of some -shrinkable (with respect to r) subsystem ƒƒ0. Taking OWD ¹D2O2WSD2ƒºthus gives a -shrinkable .k; m/r-orchard as required, appealing to Observation 6.2. 7. Shrinkable orchards of large order In this section, we establish the existence of shrinkable orchards with large order, proving Proposition 5.2. Our approach is to find an orchard such that the Kr-hypergraph Hgenerated by the orchard is very dense. This allows us to apply Lemma 3.8 in many subhypergraphs of H. Coupled with Theorem 3.12, this will imply that the orchard is shrinkable. As in the previous section, we begin in Section 7.1 by using these results on fractional matchings to deduce conditions on an orchard which guarantee shrinkability. We will then show in Section 7.2 that we can appeal to Proposition 4.1 to generate diamond trees whose removable vertices are contained in many copies of Kr. This will then allow us to prove the existence of shrinkable orchards of large order in Section 7.3. As in Section 6, however, this first argument will fall short of the range of orders needed in Proposition 5.2. The rest of the section is thus concerned with extending our methods to capture more orders. This leads us to a process which generates an orchard in two rounds. The outcome of the first round is discussed in Section 7.4, and building on this, in Section 7.5 we detail properties of the orchard after a second round of generation. Finally, in Section 7.6, we show that by generating orchards via this two-phase process, we end up with orchards which are shrinkable. This allows us to complete the proof of Proposition 5.2. 7.1. A density condition which guarantees shrinkability We begin by applying Lemma 3.8 and Theorem 3.12 to give a density condition which we can use to show that an orchard is shrinkable. This transforms our problem into finding orchards which satisfy this condition. Lemma 7.1. For all r2N3and 0 <  < 1=.2r3/, there exists a k02Nsuch that the following holds. Suppose that Ois a .k; m/r-orchard in a graph Gwith k2Nk0 and m2N. For a diamond tree D2O, let RDdenote its removable vertices and for a suborchard O0O, let R.O0/WD SD2O0RDdenote the union of the sets of removable vertices of diamond trees in O0. Suppose that the following condition holds: For any D2Oand POn¹Dºsuch that jPj  k=.4r/, there exists a suborchard PDP.D;P/Psuch that jPj  k1r3and for any disjoint suborchards O1; : : : ; Or2PnP, with jOij  k1r3 for i2Œr 3 and jOr2j k, there is a copy of Krin Gtraversing RD, R.P/and R.Oi/for i2Œr 2. (7.1) Then Ois -shrinkable. Clique factors in pseudorandom graphs 849 Let us take a moment to digest the density condition (7.1). For simplicity, one can think of Pbeing a single diamond tree DDD.D;P/. Indeed, this is the setting that we will work in first when applying Lemma 7.1. Simplifying further and just focusing on the case that rD3, condition (7.1) translates as stating that for any K3-diamond tree D in the orchard and large suborchard PO, there is some diamond tree D2Psuch that the pair ¹D;Dºhas high degree in the K3-hypergraph generated by P. Indeed, for any small linear sized O1P, there is a hyperedge in H.O/containing D;Dand a diamond tree in O1. In general, when r4, we need to guarantee traversing Krs when some of the sets we look to traverse are smaller than linear (size k1r3/. Also later on we will need the full power of Lemma 7.1 which allows us to choose the Pas a small suborchard as opposed to a single diamond tree. We now prove the lemma. Proof of Lemma 7.1.Let QObe an arbitrary suborchard of Oof size k. We will show that Ois shrinkable with respect to Q. So fix some arbitrary suborchard Q0Q and let HWD H.OnQ0/be the Kr-hypergraph generated by OnQ0. We have to show that Hhas a matching covering all but at most k1vertices of H. In order to show the existence of a large matching in H, as we did in Lemma 6.3, we appeal to Theorem 3.12. So let us fix ND jV.H/jand note that as N.1 /k, by choosing k0to be large, we can assume that Nis sufficiently large in what follows. Now fix some 2-uniform graph Jon V.H/ of maximum degree at most Nr2. If we can show that HnHJcontains a perfect fractional matching, then we are done by Theorem 3.12 because, Jbeing arbitrary, the theorem guarantees a matching covering all but at most N1k1vertices of H. In order to prove the existence of a perfect fractional matching in HnHJ, we appeal to Lemma 3.8, fixing MWD N=.2r/. Thus, we need to show that given any Kr-diamond tree D2V.H/ DOnQand suborchard P0V.H / n¹Dºwith jP0j  M, there is an edge in HnHJcontaining Dand r1 Kr-diamond trees in P0. So fix such a D and P0. Let PWD P0nNJ.D/. Then jPjjP0jjNJ.D/j  N 2r Nr2.1 /k 2r kr2k 4r for ksufficiently large. Hence by condition (7.1), we have the existence of some PD P.D;P/Pas in the hypothesis. Now we will iteratively define Oifor 1ir2 as follows. We begin by fixing P0DPand defining Q0WD SC2P.N J.C/[ ¹Cº/. For 1ir2, we update P0by removing any diamond trees in Qi1from P0 and then define Oito be an arbitrary suborchard of P0of size k1r3if i2Œr 3, and of size k if iDr2. If iDr2we end this process. If i < r 2, we define QiWD SC2Oi.N J.C/[¹Cº/and move to the next index. Let us check that we are successful in each round. Indeed, this follows because at the beginning of step iin the process, P0has size jP0j  k 4r ik1r3.1 CNr2/k 4r rk1r3Cr2k k1r3 P. Morris 850 for large k. Therefore there is always space in P0to choose our suborchard Oiat each step i. Now condition (7.1) gives a copy of Krin Gtraversing RD,R.P/and R.Oi/for i2Œr 2. This gives a hyperedge ein the Kr-hypergraph HDH.OnQ0/which has one vertex D, one vertex in PP0and one vertex in each of the OiP0. Moreover, this edge elies in HnHJ. Indeed, by our construction of Pand the Oi, there is no edge in Jbetween any pair of distinct sets in the family ¹¹Dº;P;O1; : : : ; Or2º. We have therefore established the existence of a perfect fractional matching in HnHJdue to Lemma 3.8, which implies that Ois -shrinkable as detailed above. Lemma 7.1 gives a route to proving the existence of shrinkable orchards. Indeed, if the sets of vertices which arise as pools of removable vertices of suborchards are sufficiently large, then appealing to Corollary 3.5 can give the required transversal copy of Krin G, so that (7.1) is satisfied. However, we cannot immediately derive such results because the sizes of the sets required in (7.1) are too small. In particular, (7.1) forces only one set (namely R.Or2/) to be linear in size, whilst all other sets that feature can have sublinear size. This is troublesome because the examples we have from Corollary 3.5 to generate transversal copies of Krrequire at least two of the sets involved to be linear. Indeed, it can be seen from the more general Lemma 3.4 that we cannot do any better. That is, in order to use Definition 1.3 and our condition on ˇto derive the existence of a copy of Kr that traverses a family of sets, at least two of the sets in the family must be linear in size. Therefore in order to apply Lemma 7.1 and derive the existence of shrinkable orchards, we have to obtain orchards with some additional structure. We start by exploring properties of singular diamond tress that we can guarantee. 7.2. Popular diamond trees As was the case when we were interested in proving the existence of shrinkable orchards with small order, Proposition 4.1 gives a powerful tool for proving the existence of diamond trees with additional desired properties. Here we show that we can choose a diamond tree so that there are many copies of Krformed with its removable vertices. Lemma 7.2. For any r2N3and 0 < ˛ < 1=212r there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1nand any vertex subset UV.G/ with jUj  n=4. Suppose that m2Nwith max ¹p1r; pr1nº  mn7=8 and we have set families W0;W1;:::;Wr12V.G/ such that (1) jW0j  ˛pr1nfor all W02W0; (2) jWij  ˛pn for all Wi2Wi,1ir3; (3) jWr2j  ˛n for all Wr22Wr2; (4) Qr2 iD0jWij  2m=4. Clique factors in pseudorandom graphs 851 Then there exists a Kr-diamond tree DD.T; R; †/ in GŒU  of order at least mand at most 2m such that for any choice of sets WD.W0; : : : ; Wr2/2W0Wr2, there is a copy of Krin Gtraversing Rand the sets W0; : : : ; Wr2. Proof. Let us fix ">0small enough to apply Proposition 4.1 with ˛4.1 D˛0WD 1=23r and Corollary 3.5 with ˛3.5 D˛, as well as being small enough to force nto be sufficiently large. Note that our lower bound of .pr1n/ on mand Fact 3.2 imply that m! 1 as n! 1 and so we can also assume mis sufficiently large in what follows. We begin by splitting Uinto disjoint subsets U0and W0arbitrarily so that jU0j;jW0j  n=8 D4˛0rn, noting that this is possible by our definition of ˛0. We further fix dWD ˛02pr1n. Now we apply Proposition 4.1 with zWD ˛02n=4 Dn=26rC2and fix the sets XU0 and YU0which are output. Note that jXj  max ´2z dD1 2pr1 1µm 2and jYj D zjXj  z 2Dn 26rC3; for nlarge. Now for each choice of WD.W0;: : :;Wr2/2W0Wr2, we find some subset Y.W/Yof size jYj=2 such that for every v2Y.W/, there is a copy of Kr1in the neighbourhood of vwhich traverses W0; : : : ; Wr2. In other words, for every v2Y.W/, there is a copy of Krtraversing W0; : : : ; Wr2and ¹vº. We can find Y.W/by repeated applications of Corollary 3.5 (2). In more detail, we initiate with Y0DYand Y.W/empty and in each step we find a copy of Krtraversing W0;: : :;Wr2and Y0. Taking vto be the11 vertex of this Krthat lies in Y0, we add vto Y.W/, delete it from Y0and move to the next step. We continue for jYj=2 steps using the fact that the conditions of Corollary 3.5 (2) are satisfied at each step. Indeed, this is due to the lower bounds on the sizes of Wiin conditions (1)–(3) of this lemma and the fact that jY0j  jYjjY.W/j  jYj=2 ˛n throughout, using our upper bound on ˛and our lower bound on jYjhere. Similarly to the proof of Lemma 6.6, we now take Qto be a random subset of Y by taking each vertex of Yinto Qindependently with probability p0WD 5m 4jYj. Thus EŒjQjD5m=4 and by Theorem 3.6, we have m jQj  3m=2 with probability at least 12em=60. Furthermore, for any fixed W2W0Wr2, EŒjQ\Y.W/jDp0jY.W/j D 5m=8: Applying Theorem 3.6 again implies that the probability that jQ\Y.W/j D 0is less than e5m=16. Therefore using the inequality Qr2 iD0jWij  2m=4 and appealing to a union bound, we can conclude that whp as n(and hence m) tends to infinity, we see that m jQj  3m=2 and Q\Y.W/¤ ; for all choices of W2W0Wr2. So for sufficiently large nwe can fix such an instance QYand taking RWD X[Qwe have 11Here we refer to the vertex that lies in Y0although there may be several (if the Wiintersect the Y0). What we mean here is the vertex vin the copy of Krwhich is assigned to Y0by virtue of the copy being traversing. P. Morris 852 that a Kr-diamond tree DD.T; R; †/ with removable set of vertices Ris guaranteed by Proposition 4.1. We claim that Dsatisfies all the necessary conditions. Indeed, the fact that the order of Dlies between mand 2m follows from the fact that mjQj3m=2 and jXj  m=2, whilst the fact that Q\Y.W/¤ ; for each choice of WD.W0; : : : ; Wr2/ guarantees that we have a copy of Krtraversing QRand the sets W0; : : : ; Wr2. 7.3. The existence of shrinkable orchards of large order Using Lemma 7.2 to generate the diamond trees that form our orchard, we can prove that the orchard generated satisfies the condition of Lemma 7.1 and hence is shrinkable. This gives the following. Proposition 7.3. For any r2N3and 0 < ˛;  < 1=212r there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1nand any vertex subset UV.G/ with jUj  n=2. For any m2Nwith max ¹p1r; pr1nº  mn7=8; there exists a -shrinkable .k; m/r-orchard Oin GŒU  with k2Nsuch that ˛n km  2˛n. Proof. Fix ">0small enough to apply Lemma 7.1 with 7.1 Dand Lemma 7.2 with ˛7.2 D˛0D˛. Fix some k2Nsuch that ˛n k2˛n. We also ensure that "is small enough to force n(and hence k, due to our upper bound on m) to be sufficiently large in what follows. Now we begin by noticing that km=.8r/. Indeed, if pn1=.2r2/, then p1rpnpr1nm; while if pn1=.2r2/, then pr1npnp1rm: Therefore, for any pwe have mpnand k2˛n=m 211r pnm=.8r/. Now we turn to finding our .k; m/r-orchard in GŒU . We do this by finding one diamond tree at a time as follows. For 1ik, fix UiWD UnSi0<i V.Di0/and note that jUijjUj  2˛rn n=4 throughout due to our condition on ˛. We then apply Lemma 7.2 to find a diamond tree DiD.Ti; Ri; †i/such that V.Di/Uiand for any choice of i02Œi 1 and disjoint subsets I1; : : : ; Ir2Œi 1 n ¹i0ºwith jIjj  pk for 1jr3, and jIr2j  k, there is a copy of Krtraversing Ri,Ri0and the sets S`2IjR`for j2Œr 2. The existence of such a Difollows from Lemma 7.2. Indeed, we define W0D ¹Ri0Wi02Œi 1º,WjD ¹S`2I0R`WI0Œi 1; jI0j  pkº for 1jr3and finally Wr2D ¹S`2I0R`WI0Œi 1; jI0j  kº. We need to check that conditions (1)–(4) of Lemma 7.2 are satisfied. Indeed, (1) follows from our lower bound on m, whilst (2) and (3) follow from the fact that km ˛n and our definition of ˛0. Finally, note that each choice of a set in any of the Wjcomes from a subset of Œi 1. Hence we can upper bound Qr2 jD0jWjjby .2i/r12rk. As discussed in the Clique factors in pseudorandom graphs 853 opening paragraph, we have km=.8r/ and so condition (4) of Lemma 7.2 is also satisfied. Thus Lemma 7.2 succeeds in finding the necessary Kr-diamond tree at every step of this process. Let OD¹D1; : : :;Dkºbe the orchard obtained by this process. We claim that Ois - shrinkable and to show this we appeal to Lemma 7.1 and so need to show that the density condition (7.1) is satisfied by O. So fix Di2Oand POn¹Diºwith jPj  k=.4r/. We then define DDD.Di;P/(this plays the role of Pin (7.1)) to be the diamond tree in Pwith the highest index. That is, we define iWD max ¹i0WDi02Pºand set DDDi. Note that we may have i< i but this will not be a problem. We claim that condition (7.1) is satisfied with this choice of D. Indeed, let O1;: : :;Or2Pn¹Dº be disjoint suborchards satisfying the lower bounds on the sizes given by (7.1). For each j2Œr 2, define IjWD ¹i0WDi02Ojº. Then jIr2j  k. For 1jr3we have jIjj  k1r3pk. This follows from the fact that kr3k1=2rn1=2rC1n1 8.r1/ p; where we have used the upper bound on in the first inequality, the fact that kpnin the second inequality (see the opening paragraph of the proof), and pr1nmn7=8 in the last inequality. Now relabelling ¹i; iºas ¹`0; `1ºso that `0< `1, we see that at the point of choosing D`1, we guaranteed that there was a Krtraversing R`1,R`0and the sets R.Oj/DSi02IjRi0for j2Œr 2. By Lemma 7.1 this completes the proof that O is -shrinkable. Proposition 7.3 establishes Proposition 5.2 when Gis very dense. However, when Gis sparse (when pn1=.2r2/ to be specific), the lower bound of mp1rtakes over and we are left with a gap between the range covered by Proposition 7.3 and the desired range of Proposition 5.2. Tracing the condition that mD.p1r/back through the proof, we can see that this was necessary in order to prove Lemma 7.2. There, we used our key Proposition 4.1 to generate a diamond tree where we had a large pool Yof vertices which were candidates for being removable vertices. In order to establish the existence of the cliques we need in Lemma 7.2, we needed Yto be linear in size. The sticking point then comes from the fact that Proposition 4.1 can only guarantee a maximum factor of O.pr1n/ between the size of the pool of vertices Yand the order of the diamond tree that we generate. Indeed, in Proposition 4.1 we are forced to include the set Xin the removable vertices of the diamond tree we generate and when Yis linear in size, Xcould have size as large as .p1r/. It is unclear how one would improve on this and find diamond trees with smaller order that are still contained in sufficiently many copies of Kr. Thankfully, there is a way to circumvent this issue and apply our methods to close the gap in the range of orders nonetheless. The key idea is to replace the diamond tree generated by Lemma 7.2 with a set of diamond trees, that is, a small suborchard. Indeed, by grouping together diamond trees, we can decrease their order but guarantee that the collective pool of potential removable vertices for the group is still linear in size. Through P. Morris 854 following a similar proof to that of Lemma 7.2, this has the outcome of being able to guarantee many copies of Krwhich contain a vertex in the removable vertices of one of the diamond trees in the group. Moreover, in the proof of Proposition 7.3, we crucially used the fact that we could generate diamond trees from Lemma 7.2 to establish the density condition (7.1) of Lemma 7.1. We chose an appropriate Dand used the fact that it had been generated by Lemma 7.2 to prove the required existence of transversal copies of Kr. However, Lemma 7.1 allows us to use a much larger suborchard Pfor this condition as opposed to a single diamond tree. Therefore there is hope to incorporate the idea of using a suborchard instead of a single diamond tree in Lemma 7.2, whilst maintaining the overall, scheme of the proof. There are some further difficulties to overcome, but on a high level, this is the approach we follow in the next sections to establish Proposition 5.2. 7.4. Preprocessing the orchard As discussed above, in order to prove Proposition 5.2 and remove the condition that mD .p1r/from Proposition 7.3, we need to replace the role played by Din the proof by a small suborchard P. This allows us to prove an analogue of Lemma 7.2, where one now finds an orchard whose collective set of removable vertices lies in many copies of Kr. Our shrinkable orchard will then be formed as the union of many of these smaller orchards. Indeed, in what follows we will split kas kD`t and will aim to have tsmaller .`; m/r-orchards contributing to our shrinkable orchard O. Each of the .`; m/r-orchards will have strong connectivity to the rest of the orchard O. In order to work with the fact that we are splitting kinto tsets of size `, we introduce a two-coordinate index system, with .i; j / 2Œt Œ` indicating that we are referring to the jth object in the ith subset and we will work through these indices lexicographically. In more detail, we let <Ldenote the lexicographic order on the pairs .i; j / 2Œt Œ`. That is, .i0; j 0/ <L.i; j / if and only if either 1i0i1and 1j0`or i0Diand 1j0j1. Furthermore, for each 1itand 1j`, we define I<ij WD ¹.i0; j 0/2Œt Œ` W.i0; j 0/ <L.i; j /º to be the indices .i0; j 0/which come before .i; j / in the lexicographic order. A hurdle that arises with our new approach is that we lose the symmetry provided by the fact that both Dand Din our applications of Lemma 7.1 were given by singular diamond trees. Indeed, in our proof of Proposition 7.3, when verifying condition (7.1) of Lemma 7.1, we use the fact that both the arbitrary diamond tree DDDiand the diamond tree DDD.Di;P/that we can choose were generated using Lemma 7.2. We now hope to generate our suborchards Pusing an equivalent to Lemma 7.2, and this will mean that we can no longer switch the roles of Dand Pwhen appealing to the conclusion of (the proof method of) Lemma 7.2. In particular, this places a higher demand on the properties we need to conclude of our .`; m/r-suborchards. In more detail, we need to generate suborchards which are highly connected to all the other vertices of the Kr-hypergraph H.O/. Therefore it no longer suffices to build our orchard in a linear fashion, choosing diamond trees (or indeed suborchards) to be well Clique factors in pseudorandom graphs 855 connected (in terms of the Kr-hypergraph) with previously chosen diamond trees. We will instead generate our orchard in two rounds. In the first round we fix a part of each diamond tree and using Proposition 4.1, provide large pools of vertices which can extend the parts of the diamond trees chosen so far, which we will then do in the second round. Lemma 7.4 details the outcome we draw from this preprocessing first round. Lemma 7.4. For any r2N3and 0 < ˛ < 1=212r there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n, any vertex subset UV.G/ with jUj  n=2 and any k; m; t; ` 2Nsuch that kDt`; ˛n km 2˛n and `m p1r: There exist vertex sets Zij ; Yij Uand matchings …ij ; ‡ij Kr1.GŒU / of .r 1/- cliques for each i2Œt and j2Œ` such that the copies of Kr1in each ‡ij WD ¹SvW v2Yij ºare indexed by the vertices in Yij and conditions .1ij /through .5ij /below are satisfied for all 1itand 1j`: .1ij /jZij j D mand j…ij jDjZij j1. .2ij /jYij jDj‡ij j D p˛ n=`. .3ij /The vertex sets Zij ,Yij ,V .…ij /and V .‡ij /are all disjoint from each other. .4ij / A \A0D ; for any choice of 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 /For any choice of Q Ysuch that Q YYij , there exists a Kr-diamond tree DD .T; R; †/ such that RDZij [Q Yand †D…ij [Q ‡ij , where Q ‡ij ‡ij is defined to be Q ‡ij WD ¹SQvW Qv2Q YYij º: As mentioned above, in this first round we put aside part of every single diamond tree in the .k; m/r-orchard we are going to generate, thus partially defining the orchard. We also put aside large pools of vertices which will be used to extend these diamond trees in the second round of generating our orchard. The fixed parts of the diamond trees chosen in Lemma 7.4 are the sets Zij and the interior cliques …ij , whilst the pools of potential removable vertices and interior cliques that can be used to extend the diamond trees chosen are given by the sets Yij and ‡ij , respectively. We make sure through conditions .1ij / that these fixed diamond subtrees contribute a substantial portion of the final diamond trees that we are shooting for (which will have order between mand 2m). We also guarantee through conditions .4ij /that the parts of the diamond trees that we put aside in this preprocessing round do not interfere with each other, in that they are vertex disjoint. Notice also that if we fix i2Œt, then conditions .4ij /for all j2Œ` guarantee that the 12Crucially, we do not require that Ais disjoint from all Yi0j0and V .‡i0j0/, only those that are in the same subfamily indexed by i. P. Morris 856 sets Yij ; V .‡ij /,j2Œ`, do not intersect each other. This is important because in the second round of generating our orchard, we will want to extend all the diamond trees in the ith .`; m/r-suborchard simultaneously and so we do not want any interference between the choices of the extensions within such a suborchard. Also note that conditions .2ij /, for fixed i2Œt and all j2Œ`, guarantee that the collective pool of potential removable vertices for the ith .`; m/r-suborchard (the set Sj2Œ` Yij ) is linear in size, as required. Finally, conditions .5ij /contain the heart of Proposition 4.1, allowing us to arbitrarily extend any of the diamond trees we have so far using any subsets of the pools (the Yij ) of potential removable vertices and interior cliques (the ‡ij ) we have put aside. Our final remark on the statement of Lemma 7.4 is that we do not require e.g. Yij and Yi0j0for i¤i0, to be disjoint. Indeed, as we have tsuborchards and each has a linear collective pool of potential removable vertices, there would not be enough space in the graph to keep these pools disjoint. However, by requiring that the collective pool is much larger than all the vertices in our orchard (that is, much larger than km), we guarantee that we will be able to proceed greedily in our second round (Lemma 7.5) of defining the orchard, always having a large enough set of potential removable vertices at each step. Proof of Lemma 7.4.Let us fix ">0small enough to apply Proposition 4.1 with ˛4.1 D ˛0WD1=22rC1. We will find these vertex sets and matchings of .r 1/-cliques algorithmically working through the pairs .i; j / 2Œt Œ` in lexicographic order. So let us fix some .i; j /2Œt Œ` and suppose that we have already found Zij ; Yij ; …ij and ‡ij such that conditions .1ij /through .5ij /are satisfied for all .i; j / 2I<ij. We fix WUto be WWD [¹Zij [V .…ij /W.i; j / 2I<ijº [[¹Yij[V.‡ij/W1jj1º; and let UWD UnW. We use conditions .1ij /and .2ij /to upper bound the size of W as follows. We have jWj rm..i1/` Cj1/ Cp˛ rn `.j 1/ rmt` Cp˛ rn .2˛ Cp˛/rn; using mt` Dmk 2˛n. Hence jUj  n=4 from our upper bound on ˛. We will find Zij; YijUand …ij; ‡ijKr1.GŒU / and so condition (4ij)will be satisfied. The required vertex sets Zijand Yijare found by an application of Proposition 4.1. So let us split Uinto disjoint subsets U0and W0arbitrarily so that jU0j;jW0j  n=8 4˛0rn, noting that this is possible by our definition of ˛0. We further fix dWD ˛02pr1nand zWD mCp˛ n=` and note that z˛0ndue to the fact that m2˛n=k 2˛n and our upper bound on ˛. So Proposition 4.1 shows that there exists disjoint vertex subsets X; Y U0U such that jXjCjYj D zand jXj D 1mor jXj  2z=d2m dC2p˛ n d`m 2C2p˛ ˛02pr1`m; Clique factors in pseudorandom graphs 857 using our upper bound on ˛and lower bound on `m in the last inequality. As jXjm, we can fix some ZijX[Ysuch that XZijand jZijj D m. Therefore letting YijWDYnZij, we have jYijjDzmDp˛ n=` and so the size requirements on Zijin (1ij)and on Yijin (2ij)are both satisfied. Moreover, part of (5ij)is also satisfied. Indeed, for some Q YYij, taking Y0DQ Y[.ZijnX/, Proposition 4.1 implies that there is a diamond tree DD.T;R;†/ with removable vertices RDX[Y0D Zij[Q Yand †a matching of .r 1/-cliques in GŒU . Now in order to complete the proof of the lemma, we need to define the matchings of .r 1/-cliques …ijand ‡ijand reason that the remaining conditions of the lemma are satisfied. This comes from recalling how we proved Proposition 4.1 in Section 4.1 (see also Figure 6). There, we applied Lemma 4.5 to find a large d-scattered Kr-diamond tree Dsc D.Tsc; Rsc; †sc/, where Rsc DX[Ywas the set of removable vertices of Dsc and YRsc was the set of leaves in Dsc. The conclusion of Proposition 4.1 then followed readily as we could choose which leaves in Yto include in a diamond subtree Dof Dsc. From this proof we see that we can partition †sc into †sc DW …ij[‡ijwhere the .r 1/-cliques …ijare interior cliques of the Kr-diamond subtree of Dsc spanned by the removable vertices Zij. Furthermore, we can label ‡ijwith the vertices in Yijso that (5ij)is satisfied. Indeed, each vertex vin Yijcorresponds to a leaf of the diamond tree Dsc and so there is an interior clique Sv2†sc such that any diamond subtree which contains the non-leaves Xof Dsc can be extended by adding vto the set of removable vertices and Svto the set of interior cliques. As Dsc is a well-defined Krdiamond tree, condition (3ij)is also satisfied and the size constraints on …ijand ‡ijin (1ij)and (2ij)are also immediate, noting that j…ijjDjZijj  1as the set of interior cliques of a diamond tree with removable vertices Zij. 7.5. Completing the orchard We will now use Lemma 7.4 to generate our orchard. This can be thought of as extending the parts of the diamond trees (the Zij and …ij ) which were fixed in Lemma 7.4. The strategy is very similar to that of Lemma 7.2 and Proposition 7.3. Indeed, we take random subsets of the pools of potential vertices in order to guarantee that the Kr-hypergraph generated by our final orchard is sufficiently dense. The key difference here is that, as opposed to fixing our orchard one diamond tree at a time, we appeal to Lemma 7.4 to fix part of all the diamond trees in our orchard and then carry out the extensions on .`; m/rsuborchards. That is, we apply the approach of Lemma 7.2 on the whole suborchard as opposed to a singular Kr-diamond tree. After doing this process for all suborchards we end up with an orchard which generates a dense Kr-hypergraph. This is detailed in the following lemma. Lemma 7.5. For any r2N3,0 < ˛ < 1=212r and 0 <  < 1 there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n, any vertex subset UV.G/ with jUj  n=2 and any k; m; t; ` 2Nsuch that kDt`; m pr1n; `m p1rand ˛n km 2˛n: (7.2) P. Morris 864 procedure, appealing to Corollary 3.5 (3) to find each S2…(and the corresponding neighbourhood set XS), one by one. After finding …, we then turn to constructing the .4t; M /-orchard J.A/for the absorbing structure A. Again, this will be done greedily, fixing the diamond trees D2J.A/one at a time. Let us consider fixing some diamond tree Dj2J.A/. Note that as we fix Dj, we immediately get restrictions on which S2…remain as candidates to play the rôle of certain Si2„.A/. Indeed, if the removable vertices of Djare disjoint from NG.S/ and ij is an edge in the template Tdefining A, then there is no way Scan play the role of Siin „.A/. Therefore as we fix our diamond trees, we will aim to have their sets of removable vertices intersect as many of the XS(and hence neighbourhoods NG.S/) for S2…as possible. In order to do this, we will use the following lemma, which shows that we can find diamond trees whose removable vertices intersect many prescribed sets (in our case this will be the sets XS). The proof of this lemma is a simple application of Proposition 4.1. Lemma 8.4. For any r2N3and 0 < ˛ < 1=22r , there exists an " > 0 such that the following holds for any n-vertex .p; ˇ/-bijumbled graph Gwith ˇ"pr1n. Suppose ˛2 2n2=3 `˛n2=3 and we have disjoint vertex subsets W; U1; : : : ; U` such that jWj  n=4 and jUij  n1=3 for all i2Œ`. Then there exists a diamond tree DD.T; R; †/ in Gsuch that (i) †Kr1.GŒW / is a matching of .r 1/-cliques in W; (ii) RS` iD1Uiand Rintersects `0of the sets Uifor some `0`=.4r/; (iii) the order of Dis at most n2=3; (iv) for all but at most n1=2 of the indices i2Œ`, we have jV .D/\Uij  n1=6. Proof. We begin by fixing WD `=n2=3 so that ˛2=2 ˛and we fix "small enough to apply Proposition 4.1 with ˛4.1 D˛0WD =.4r/ and small enough to guarantee that pC n1=.2r3/ with CD4=˛0(see Fact 3.2). Now shrink each set Uiso that it has exactly n1=3 vertices and define UWD S` iD1Ui. Furthermore, fix dWD ˛02pr1nand apply Proposition 4.1 with U,Wand zD˛0n. So we get disjoint subsets X; Y Uas in the outcome of Proposition 4.1. Now firstly note that as jXjCjYj D zD˛0n,jUj D `n1=3 Dn D4rz and the Ui have equal size, X[Ymust intersect at least `=.4r/ of the sets Ui. We will choose our DD.T;R; †/ so that Rintersects all the sets Uithat X[Yintersects, thus guaranteeing condition (ii). Indeed, if we let Y0Ybe the minimal subset of Ysuch that there exists no i2Œ` with Y\Ui¤;and Y0\UiD;, Proposition 4.1 gives the existence of a diamond tree DD.T; R; †/ such that RDX[Y0and †Kr1.GŒW / and so conditions (i) and (ii) are satisfied. In order to establish condition (iii), note that jY0j  `n2=3=2 and if jXj> 1 then jXj  2z d2 ˛0pr12n.r1/=.2r3/ ˛0Cr1n2=3 2; Clique factors in pseudorandom graphs 865 due to our definition of Cand the fact that r1 2r32 3for all r3. Finally, (iv) is a simple consequence of (iii). Indeed, if (iv) were not true, then as the Uiare pairwise disjoint, D would have order greater than n1=2 n1=6 n2=3, a contradiction. Let us return to sketching the proof of Proposition 8.3, considering now that we can use Lemma 8.4 to find diamond trees D2J.A/. As discussed above, the key property of diamond trees generated by Lemma 8.4 is (ii), allowing us to find diamond trees that intersect many of the sets ¹XSWS2…ºwhich we begin the proof with. Property (iv) will also be useful as it shows that in the process of building J.A/one by one, we do not destroy many of the sets XSand most of them remain large and can be used by other D2J.A/. One potentially troublesome consequence of Lemma 8.4 is that the diamond trees it finds are far too small; see (iii). Indeed, the diamond trees in our orchard J.A/are supposed to be of order MDn7=8. It turns out that this is not such a big hurdle as we can find a large diamond tree disjoint from all the XSand connect it to the diamond tree Coutput by Lemma 8.4. In more detail, we can apply Proposition 4.1 to create a large (linear) pool Yof vertices that can be removable vertices of some diamond tree which will be disjoint from all the vertices in the sets XS. We also consider the large (linear) pool Z of vertices that lie in some XSnV.C/with S2…such that the removable vertices of C intersect XS. It is not hard to show (see for example Corollary 3.5 (3)) that there is a copy of K rC1with one degree r1vertex in Yand the other in XSZfor some S2…. By also taking Sinto Dand choosing an appropriate Y0Yto apply the key property of Proposition 4.1, we can obtain a diamond tree Dof the correct size that contains the diamond tree Coutput by Lemma 8.4. More troublesome is the fact that condition (ii), which means that the removable vertices of Cintersect many of the desired sets XS, is, in fact, not strong enough. Indeed, consider some fixed i2Ifor which we want to find a copy Siof Kr1to lie in „.A/. If j; j 02NT.i/ and the sets ¹XSWS2…; RDj\XS¤ ;º and ¹XSWS2…; RDj0\XS¤;ºare disjoint (here, as usual, we use RDto denote the removable vertices of D), then already there are no candidates for Siin …. To fix this, we actually need that when we choose a diamond tree D2J.A/, the set RDintersects almost all of the sets ¹XSWS2…º. We achieve this by iterating Lemma 8.4, creating constantly many disjoint diamond trees Cthat together hit almost all of the XSwith their removable vertices. We then connect all of these diamond trees Cwith a large diamond tree disjoint from the sets XSto obtain the desired diamond tree D2J.A/. This connecting process is similar to (although slightly more involved than) the connecting process outlined in the previous paragraph. We now give the full details for the proof of Proposition 8.3, concluding this section and chapter. Proof of Proposition 8.3.We begin by fixing ">0small enough to apply Corollary 3.5 with ˛3.5 D˛0WD˛2=.16r/ and to apply Proposition 4.1 and Lemma 8.4 each with ˛4.1 D ˛8.4 D˛. We also take "small enough to force nto be sufficiently large and to guarantee that pC0n1=.2r3/ for C0WD 2=˛02using Fact 3.2. We further fix some template T P. Morris 866 with vertex sets Iand JDJ1[J2of flexibility tand maximum degree 40 which we know exists for n(and hence t) sufficiently large by Theorem 3.14 of Montgomery [57]. We will find an absorbing structure with respect to Tand so must prove the existence of a matching „.A/D ¹SiWi2Iº  Kr1.GŒW / of 3t copies of Kr1, and a .4t; M /-orchard JDJ.A/D ¹DjWj2Jºsuch that the conditions of Definition 8.1 are satisfied. We will do this in three stages. In Claim 8.5, we fix some large matching …Kr1.GŒW / of .r 1/-cliques which will be candidates for the .r 1/-cliques which will feature in „.A/. We will guarantee that the cliques in …are contained in many copies of Krwhich will help as we proceed to build our absorbing structure. In Claim 8.6, we will fix the Kr-diamond trees which will form our orchard Jfor our Kr-absorbing structure. We will carefully control how these diamond trees intersect the cliques in our candidate set …and their neighbourhoods. Finally, we will show that we can find a suitable „.A/…so that we obtain the desired absorbing structure. Claim 8.5. There exists a matching …D ¹S1; : : : ; S`º  Kr1.GŒW / of `WD ˛n2=3 copies of Kr1and sets XhWnV.…/ for each h2Œ` such that the Xhare pairwise disjoint, each has size 2n1=3 and for all h2Œ` we have XhNG W.Sh/. Proof of Claim. We can do this by way of a simple greedy process choosing such an .r 1/-clique Shand set Xhin order for hD1; : : : ; `. When choosing Shand Xh, we look at the set of vertices VhWwhich have not been used in previous choices of Sh0 or Xh0. We have jVhj  jWjˇˇˇ[ h0<h .Xh0[Sh0/ˇˇˇn=2 .` 1/.r 1C2n1=3/.1=2 2˛/n n=4; and an application of Corollary 3.5 (3) with W0DW1DW2DVhgives the desired Sh and Xhin Vhsince ˛02pr1n˛02C0n1.r1/=.2r3/ 2n1=3 due to Fact 3.2. Next we turn to fixing our .4t; M /-orchard J. Claim 8.6. Let Shand Xhfor hD1;: : :;` be as in Claim 8.5. Then there exists a .4t;M /- orchard JD ¹D1; : : : ; D4t ºsuch that V.J/Wand the following properties hold for each DjD.Tj; Rj; †j/with j2Œ4t: (1) the set Rjof removable vertices intersects at least .1 ˛/` of the sets Xhwith h2Œ`; (2) V.Dj/intersects at most CWD log.2 ˛/ log.4r 4r1/of the Shwith h2Œ`. Before proving the claim, let us see how it implies the proposition. Indeed, taking the .4t; M /rorchard Jfrom Claim 8.6 as J.A/, we just need to choose a matching of .r 1/-cliques „.A/D ¹SiWi2Iºso that Si\V.J/D ; for all i2Iand whenever ij 2E.T/, there is a vertex in Rjwhich forms a copy of Krwith Si. We do this greedily, Clique factors in pseudorandom graphs 867 showing that for each iD1; : : : ; 3t in order, there is a suitable choice for Siin …. We initiate by fixing LŒ` to be the indices h2Œ` such that Sh\V.J/D;. By condition (2) in Claim 8.6, for large nwe have jLj  `4C t .1 ˛/` at the beginning of this process, recalling that `D˛n2=3 and tD˛n1=8. Now for iD 1; : : : ; 3t, we find an index hDh.i/ 2Lsuch that Shforms a copy of Krwith a vertex in Rjfor all jsuch that ij 2E.T/. We fix SiDShand delete hfrom L. If this process succeeds in finding a suitable hDh.i/ for each i2Ithen the resulting „.A/D ¹SiW i2Iºalong with Jform the desired Kr-absorbing structure. It remains to check that we are successful at each step. So consider step i2Œ3t. We have that jLj  .1 ˛/` .i1/ .1 2˛/` at the beginning of the step. Now for each j2Jwhich is a neighbour of iin the template T, by Claim 8.6 (1) there are at most ˛` indices h2Œ` such that no vertex of Rjforms a Krwith Shin G. Indeed, for almost all choices of h, we have Rj\Xh¤ ; and XhNG.Sh/. Given that Thas maximum degree 40, this gives at most 40˛` indices h2Lthat would not be a good choice for h.i/. Therefore there are at least .1 42˛/` indices h2Lwhich can be chosen as h.i/and we simply choose one arbitrarily. This shows that the algorithm is successful in generating the desired absorbing structure and so it only remains to prove Claim 8.6, which we do now. Proof of Claim 8.6.We will find the diamond trees Dj,jD1; : : : ; 4t, one by one so that they are vertex disjoint and satisfy the two conditions in the statement of the claim as well as the further following condition: (3) V.Dj/intersects all but at most C n1=2 of the Xhwith h2Œ` in more than 2C n1=6 vertices. We will initiate the process with ƒWD Œ` and UhDXhfor all h2Œ`. These sets Uhwill keep track of vertices in Xhthat we are still allowed to use, that is, those vertices which have not been used in previously chosen diamond trees. Furthermore, the set ƒŒ` will keep track of all indices which are alive. When we choose a Djfor some j2Œ4t, we kill (and remove from ƒ) all the indices h2Œ` such that V.Dj/intersects Xh in more than 2C n1=6 vertices. We also kill any index hsuch that V.Dj/intersects Sh. Due to our conditions (2) and (3), throughout the process we have jƒj  `4t.C CC n1=2/.1 ˛=2/` for nlarge, recalling that `D˛n2=3 and tD˛n1=8. Moreover, due to condition (3), at any point in the process, for all alive indices hin ƒ, the size of UhXhis at least jUhjjXhjX jjV.Dj/\Xhj  2n1=3 8tC n1=6 n1=3 for nsufficiently large. We remark that it is crucial in the previous two calculations that tDn1=8 and so when choosing our diamond trees, we do not kill too many indices or P. Morris 868 make too many of the sets Xhtoo small to be used by subsequent diamond trees. In fact, any tpolynomially smaller than n1=6 would suffice for this. So let us suppose that we are at step j2Œ4t where we look for Djand we have some fixed set ƒof alive indices and subsets UhXhfor h2ƒ. We run a subalgorithm that finds Djin two phases. We begin by setting Dƒand CD ;. The first phase of the subalgorithm works by finding at most Csmall order diamond trees whose removable vertices intersect many of the Uhfor h2ƒ. The family Cwill collect these small order diamond trees and the set will keep track of the indices hin ƒfor which we have not yet intersected Uh. In the second phase of the algorithm, we will form Djby joining together the diamond trees in Cso that they form one diamond tree. By guaranteeing that our diamond trees in Chave removable vertices that intersect most of the sets Uh, we will guarantee condition (1) of the claim. Before starting, we also initiate by setting W0W to be W0DWn[ h2Œ` .Sh[Xh/[[ j <j  V.Dj/: In words, W0is the subset of vertices of Wthat has not been used in any of the structures that we have found so far. Finally, we initiate a counter by setting sD1. At step s, we apply Lemma 8.4 on the sets W0and ¹UhWh2º. We thus find a Kr-diamond tree CsD.T; R; †/ which we add to C, which has the following properties guaranteed by Lemma 8.4: (i) †Kr1.GŒW 0/ and we delete V .†/ from W0; (ii) RSh2Uhand defining sto be sWD¹h0WR\Uh0¤ ;º, we have jsj jj=.4r/; we delete sfrom ; (iii) the order of Csis at most n2=3; (iv) there is a set ˆssŒ` of at most n1=2 indices such that for all h2Œ` nˆs we have jV.Cs/\Uhj  n1=6. Finding such a Csconcludes step s. If jj< ˛`=2, we terminate this phase and move on to the next phase. If jj  ˛`=2, we move to step sC1. We must check that the conditions for Lemma 8.4 are satisfied throughout this phase in order to find the required diamond trees Csat each step. Indeed, this follows because ˛2 2n2=3 D˛ 2` jj  `D˛n2=3 throughout, and jUhjn1=3 for all h2since ƒis a subset of alive indices. Finally, jW0jn=4 throughout this process. Indeed, note that due to condition (ii) and the fact that we only continue until jj  ˛`=2, the process runs for a maximum of Csteps, recalling the definition of Cfrom condition (2) of the claim. That is, jCj  Cthroughout and so jW0jjWj X h2Œ` .jShjCjXhj/X j <j jV.Dj/j X C2C V.C/ n 2`3n1=3 8trM C n2=3 1 2.4 C8r/˛nn 4;(8.2) Clique factors in pseudorandom graphs 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 of Djand its components. In this case, we have cD2,h1D1and h2Dh. due to our upper bound on ˛, for nsufficiently large. This verifies that we find Csat every step sof this process and so we finish this phase with jj< ˛`=2 and some family CD ¹C1;:::;Ccºof cCvertex disjoint Kr-diamond trees. Now we describe how we generate Djwhich will have all the diamond trees Cs2C as sub-diamond-trees. We refer the reader to Figure 8to keep track of the many components that contribute to our Dj. One thing to note is that the sum of the orders of the diamond trees in Cis far too small for us to just build Djfrom the diamond trees in C. Indeed, the sum of the orders is O.n2=3/and we want Djto have order MDn7=8. Therefore we will have to find the majority of the Kr-diamond tree Djelsewhere. In order to prepare for this, we first split W0arbitrarily into U0; W0and Z0of roughly equal size and note that due to our lower bound (8.2) on jW0j, each of these sets has size at least n=16. Next we fix dWD˛2pr1nand zD˛2nand apply Proposition 4.1 with respect to the sets U0and W0to get disjoint sets X;Y U0as detailed there. Note that jXj2n2=3. Indeed, if jXj> 1, then jXj  2z=d2p1r2n2=3 due to Fact 3.2. Now for 1sc, define ZsWD Sh2snˆs.UhnV.Cs//. In words, Zsis the union of the sets Uhwhich Csintersects, after removing the sets Uh0which Csintersects in too many vertices and then removing the vertices of Cs. Now, for each s2Œc, jZsj  .jsjjˆsj/.n1=3 n1=6/˛`n1=3 8r 2n5=6 ˛2n 16r ˛0n for nlarge, as the Uhare pairwise disjoint. Note also that as the sare pairwise disjoint, so are the Zsfor s2Œc. Now for 1sc, apply Corollary 3.5 (3) to find an .r 1/- clique S0 sKr1.GŒZ0/ such that there is a vertex zs2Zs\NG.S0 s/and a vertex P. Morris 870 xs2.X [Y / \NG.S0 s/. We delete the S0 sfrom Z0and move to the next index sC1or finish if sDc. Now choose some Y0Ysuch that xs2X[Y0for all s2Œc and jY0jCjXjC X s2Œc .jRCsjC1/ DM: This is easily done as jXjC jYj D ˛2nis linear and jXj;jRCsj  2n2=3 for all s2Œc, which is much smaller than MDn7=8. By Proposition 4.1, there is a Kr-diamond tree Q DD.Q T ; Q R; Q †/ with Q RDX[Y0and Q †Kr1.GŒW0/ a matching of .r 1/-cliques in W0W0. Our diamond tree Djis then obtained by connecting Q Dand all the Cs2C. In more detail, for each s2Œc, there exists some hs2ssuch that zs2UhsXhs. We define RjWD Q R[[ s2Œc .RCs[¹zsº/and †jWD Q †[[ s2Œc .†Cs[¹S0 sº[¹Shsº/; where †Csis the set of interior .r 1/-cliques of Cs;S0 s2Kr1.GŒZ0/ is the .r 1/- clique which forms a clique with both zsand xsdefined above; and Shsis the .r 1/- clique corresponding to the set Xhs(which contains zs) in Claim 8.5. We claim that there exists a diamond tree Djof order Mwhich has Rjas a set of removable vertices and †jas a set of interior .r 1/-cliques. Indeed, we can form the defining auxiliary tree Tjby starting with the forest of the disjoint union of Q Tand the TCsfor s2Œc, where TCsdenotes the defining tree for the Kr-diamond tree Cs. For each s2Œc, we then add a path of length 2 (with two edges) between some vertex in V.TCs/and V. Q T /. The edges of this path correspond exactly to the internal .r 1/-cliques Shsand S0 sand thus the vertices of this path correspond to xs,zsand some vertex in RCs\Uhsfor each s2Œc. This defines Djand so we update all the Uhto be UhnV.Dj/for h2Œ` and kill any indices h2ƒsuch that either V.Dj/intersects Shor jXh\V.Dj/j  2C n1=6. We now need to check that conditions (1)–(3) hold for Dj. To see (1), note that Rj contains all the RCsfor s2Œc and so intersects Xhfor all h2Ss2Œc s. Moreover, taking as defined at the end of finding the Cs, we have j[Ss2Œc sj.1 ˛=2/` and jj ˛`=2, and so this confirms (1). To see (2), note that the only times we used vertices of the Shwith h2Œ` to construct Djwas when we added the Shsfor s2Œc to the set of interior cliques. Thus we intersected exactly cCof these with V.Dj/. Finally, (3) for Djis implied by conditions (iv) when we found the Cs. Indeed, Rj\Sh2Œ` XhD Ss2Œc.RCs[¹zsº/and so for any index hthat does not lie in Ss2Œc ƒs(which has size at most C n1=2), we have jV.Dj/\Xhj  X s2Œc j.V .Cs/[¹zsº/\Xhj  C.n1=6 C1/ 2C n1=6: This concludes the finding of Dj, and doing this for all j2Œ4t gives the desired claim and hence the proposition. Clique factors in pseudorandom graphs 871 9. Concluding remarks In this paper, we showed that a condition of ˇDo.pkn/ in an n-vertex .p; ˇ/-bijumbled graph guarantees a KkC1-factor. We conjecture that the same condition in fact guarantees any subgraph with maximum degree k. Conjecture 9.1. For any k2N2and c > 0 there exists an " > 0 such that any n-vertex .p; ˇ/-bijumbled graph with ı.G/ cpn and ˇ"pknis k-universal, that is, given any graph Fon at most nvertices, with maximum degree at most k,Gcontains a copy of F. Note that Corollary 1.5 settles Conjecture 9.1 for kD2. For k3, the best known result comes from the sparse blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa and Person [2] which gives a condition of ˇDo.p.3kC1/=2n/ guaranteeing k-universality in a.p; ˇ/-bijumbled graph. The conjecture echoes the notion that a KkC1-factor is the ‘hardest’ maximum degree kgraph to find. This idea has manifested itself in various other settings. For example, we know from the theorem of Hajnal and Szemerédi (Theorem 1.1) that any n-vertex graph Gwith ı.G/ .k=.k C1//n contains a KkC1-factor and that this is tight. Bollobás and Eldridge [15], and independently Catlin [19], conjectured that the same minimum degree condition actually guarantees k-universality. This has been proven for kD2; 3 [1,7,25] but remains open in general. In the case of random graphs, Johansson, Kahn and Vu [39] proved that the threshold for the appearance of a KkC1-factor is of the order of p k.n/ WD n2=.kC1/.log n/2=.k2Ck/: A recent breakthrough result of Frankston, Kahn, Narayanan and Park [28] implies that for any n-vertex graph Fwith maximum degree k, the threshold for the appearance of F in G.n; p/ is at most p k.n/. Note that this is not implying that G.n; p/ is k-universal whp when pD!.p k.n// as we can only guarantee that some fixed Fappears whp. However, the stronger version that p k.n/ is the threshold for k-universality is believed to be true but only verified for kD2[26]. One thing that sets aside the pseudorandom setting in stark contrast to the other settings discussed above is that it might be possible to replace a KkC1-factor as the benchmark for the ‘hardest’ graph to find in the host graph, by a single copy of KkC1. Indeed, various authors [22,27,53,64] have stipulated that n-vertex KkC1-free .p; ˇ/-bijumbled graphs exist with ˇD‚.pkn/. Such graphs would witness the tightness of both Theorem 1.4 and Conjecture 9.1 for all values of k2(taking rDkC1in the setting of Theorem 1.4). Focusing on optimally pseudorandom graphs (that is, fixing ˇD‚.ppn/ in .p; ˇ/-bijumbled graphs), we expect to be able to find KkC1-free optimally pseudorandom graphs with pD.n1=.2k1//. These are only known to exist when kD2. Indeed, we discussed the triangle-free construction of Alon in the introduction, and other constructions [21,48] have also been given which are (near-)optimal. For k3, however, this remains a key challenge in the understanding of pseudorandom graphs, with the best known general construction coming from a recent improvement of Bishnoi, Ihringer and Pepe [13] who give KkC1-free optimally pseudorandom graphs of density pD‚.n1=k/. P. Morris 872 Further interest in finding denser such graphs comes from a recent remarkable connection discovered by Mubayi and Verstraëte [60] that shows that if, as we expect, the KkC1free optimally pseudorandom graphs with density pD.n1=.2k1//do exist, then it is possible to improve the lower bound on the off-diagonal Ramsey numbers to match the upper bound and thus determine the asymptotics of this extremal function. In detail, they show that if these pseudorandom graphs exist, then the off-diagonal Ramsey number is R.k C1; t/ DtkCo.1/ as ttends to infinity. In fact, even a construction with pD!.n1=.kC1//would improve on the current best known lower bound on off-diagonal Ramsey numbers due to Bohman and Keevash [14]. We conclude by noting that Theorem 1.2 is, in some sense, the first result of its kind, giving a tight condition on pseudorandomness to guarantee the existence of a spanning structure. Indeed, the case of Hamilton cycles remains an intriguing open problem. Krivelevich and Sudakov [52] conjectured that a condition of Do.d/ is sufficient in .n; d; /-graphs and proved the currently best known bound of Do.log log n/2d log n.log log log n/: For hypergraphs of higher uniformity, one can easily generalise the notion of bijumbledness in Definition 1.3 but the picture becomes considerably more complex. Indeed, it turns out that the only subgraphs that one can guarantee by imposing conditions on bijumbledness are linear subgraphs, those in which pairs of hyperedges intersect in at most one vertex. Building on previous work [23,47,55,56] mainly concerned with dense hypergraphs (the so-called quasirandom regime), Hiê .p Hàn, Jie Han and the author [30,31] recently gave the best-known conditions on pseudorandomness that guarantee different linear subgraphs of hypergraphs. These include all fixed sized linear subgraphs as well as F-factors for linear F(including perfect matchings) and loose Hamilton cycles. The tightness of these results is unclear as no good constructions are known for F-free pseudorandom hypergraphs. In general, the appearance of subgraphs in sparse pseudorandom (hyper-)graphs remains a fascinating area which is far from being understood. Acknowledgments. Much of this work was done during a visit of the author to IMPA, Rio de Janeiro, Brazil. I am grateful to both Pedro Araújo and Robert Morris with whom I discussed many aspects of this project, for their hospitality, support and enthusiasm. I am also grateful to my coauthors from previous projects, Jie Han, Yoshiharu Kohayakawa and Yury Person, for introducing me to this area and many of the techniques and approaches used to tackle these sorts of problems. Finally, I am grateful to the anonymous referee, to Tibor Szabó and again to Robert Morris for providing many helpful suggestions aiding the presentation and readability of the paper. Funding. The author was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689) and by a Walter Benjamin fellowship of the DFG - project number 504502205. References [1] Aigner, M., Brandt, S.: Embedding arbitrary graphs of maximum degree two. J. London Math. Soc. (2) 48, 39–51 (1993) Zbl 0796.05029 MR 1223891 Clique factors in pseudorandom graphs 873 [2] Allen, P., Böttcher, J., Hàn, H., Kohayakawa, Y., Person, Y.: Blow-up lemmas for sparse graphs. arXiv:1612.00622 (2016) [3] Allen, P., Böttcher, J., Hàn, H., Kohayakawa, Y., Person, Y.: Powers of Hamilton cycles in pseudorandom graphs. Combinatorica 37, 573–616 (2017) Zbl 1399.05118 MR 3694704 [4] Allen, P., Böttcher, J., Hladký, J., Piguet, D.: A density Corrádi–Hajnal theorem. Canad. J. Math. 67, 721–758 (2015) Zbl 1316.05069 MR 3361011 [5] Alon, N.: Explicit Ramsey graphs and orthonormal labelings. Electron. J. Combin. 1, art. 12, 8 pp. (1994) Zbl 0814.05056 MR 1302331 [6] Alon, N., Bourgain, J.: Additive patterns in multiplicative subgroups. Geom. Funct. Anal. 24, 721–739 (2014) Zbl 1377.11013 MR 3213827 [7] Alon, N., Fischer, E.: 2-factors in dense graphs. Discrete Math. 152, 13–23 (1996) Zbl 0851.05068 MR 1388628 [8] Alon, N., Frankl, P., Huang, H., Rödl, V., Ruci´ nski, A., Sudakov, B.: Large matchings in uniform hypergraphs and the conjecture of Erd˝ os and Samuels. J. Combin. Theory Ser. A 119, 1200–1215 (2012) Zbl 1242.05189 MR 2915641 [9] Alon, N., Kahale, N.: Approximating the independence number via the #-function. Math. Programming 80, 253–264 (1998) Zbl 0895.90169 MR 1603356 [10] Alon, N., Spencer, J. H.: The probabilistic method. 4th ed., Wiley Series in Discrete Mathematics and Optimization, Wiley, Hoboken, NJ (2016) Zbl 1333.05001 MR 3524748 [11] Balogh, J., Lee, C., Samotij, W.: Corrádi and Hajnal’s theorem for sparse random graphs. Combin. Probab. Comput. 21, 23–55 (2012) Zbl 1241.05130 MR 2900047 [12] Balogh, J., Molla, T., Sharifzadeh, M.: Triangle factors of graphs without large independent sets and of weighted graphs. Random Structures Algorithms 49, 669–693 (2016) Zbl 1352.05141 MR 3570984 [13] Bishnoi, A., Ihringer, F., Pepe, V.: A construction for clique-free pseudorandom graphs. Combinatorica 40, 307–314 (2020) Zbl 1463.05373 MR 4121148 [14] Bohman, T., Keevash, P.: The early evolution of the H-free process. Invent. Math. 181, 291– 336 (2010) Zbl 1223.05270 MR 2657427 [15] Bollobás, B., Eldridge, S. E.: Packings of graphs and applications to computational complexity. J. Combin. Theory Ser. B 25, 105–124 (1978) Zbl 0387.05020 MR 511983 [16] Broder, A. Z., Frieze, A. M., Suen, S., Upfal, E.: Optimal construction of edge-disjoint paths in random graphs. SIAM J. Comput. 28, 541–573 (1999) Zbl 0912.05058 MR 1634360 [17] Brouwer, A. E., Haemers, W. H.: Eigenvalues and perfect matchings. Linear Algebra Appl. 395, 155–162 (2005) Zbl 1056.05097 MR 2112881 [18] Caprara, A., Rizzi, R.: Packing triangles in bounded degree graphs. Inform. Process. Lett. 84, 175–180 (2002) Zbl 1042.68087 MR 1928953 [19] Catlin, P. A.: Embedding subgraphs and coloring graphs under extremal degree conditions. Ph.D. thesis, Ohio State University (1976) MR 2626461 [20] Cioab˘ a, S. M.: Perfect matchings, eigenvalues and expansion. C. R. Math. Acad. Sci. Soc. R. Canada 27, 101–104 (2005) Zbl 1110.05058 MR 2204683 [21] Conlon, D.: A sequence of triangle-free pseudorandom graphs. Combin. Probab. Comput. 26, 195–200 (2017) Zbl 1371.05259 MR 3603964 [22] Conlon, D., Fox, J., Zhao, Y.: Extremal results in sparse pseudorandom graphs. Adv. Math. 256, 206–290 (2014) Zbl 1285.05096 MR 3177293 [23] Conlon, D., Hàn, H., Person, Y., Schacht, M.: Weak quasi-randomness for uniform hypergraphs. Random Structures Algorithms 40, 1–38 (2012) Zbl 1236.05137 MR 2864650 [24] Corradi, K., Hajnal, A.: On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14, 423–439 (1963) Zbl 0118.19001 MR 200185 [25] Csaba, B., Shokoufandeh, A., Szemerédi, E.: Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three. Combinatorica 23, 35–72 (2003) Zbl 1046.05040 MR 1996626