Perfectly packing graphs with bounded degeneracy and many leaves
Peter Allen Julia Böttcher Dennis Clemens Anusch Taraz
 

  






verbose,tmargin=3.2cm,bmargin=3.2cm,lmargin=3cm,rmargin=3cm




 





theoremTheorem
lemma[theorem]Lemma
claim[theorem]Claim
proposition[theorem]Proposition
corollary[theorem]Corollary
fact[theorem]Fact
conjecture[theorem]Conjecture
observation[theorem]Observation
setup[theorem]Setup
setting[theorem]Setting


definition[theorem]Definition
problem[theorem]Problem

remark
remark[theorem]Remark
question[theorem]Question



claimproof[1][Proof]
  
  
  

  
  
 



 
itemsep=2pt,parsep=1pt,topsep=3pt,partopsep=0pt  
leftmargin=*,labelindent= 

style=sameline,leftmargin=.7cm,itemsep=2pt







 
#1(#1) 
#1#1  
* 
*
**
* 
#1
#1













































































P. Allen]Peter Allen
(PA) London School of Economics, Department of Mathematics, Houghton
  Street, London WC2A 2AE, UK
PA was partially supported by the EPSRC, grant number EP/P032125/1.
p.d.allen@lse.ac.uk

J. Böttcher]Julia Böttcher
(JB) London School of Economics, Department of Mathematics, Houghton Street, London WC2A 2AE, UK
j.boettcher@lse.ac.uk
JB was partially supported by the EPSRC, grant number EP/R00532X/1.
PA and JB were partially supported by a STICERD grant.

D. Clemens]Dennis Clemens
(DC) Technische Universitt Hamburg, Institut für Mathematik, Am Schwarzenberg-Campus 3, 21073 Hamburg, Germany 
dennis.clemens@tuhh.de
A. Taraz]Anusch Taraz
(AT) Technische Universitt Hamburg, Institut für Mathematik, Am Schwarzenberg-Campus 3, 21073 Hamburg, Germany 
taraz@tuhh.de






 We prove that one can perfectly pack degenerate graphs into complete or dense n-vertex quasirandom graphs, provided that all the degenerate graphs have maximum degree o(nlog n), and in addition Ω(n) of them have at most (1-Ω(1))n vertices and Ω(n) leaves. This proves Ringel's conjecture and the Gyárfás Tree Packing Conjecture for all but an exponentially small fraction of trees (or sequences of trees, respectively).


Perfectly packing graphs with bounded degeneracy and many leaves
    [
    December 30, 2023
================================================================





§ INTRODUCTION


Let ={G_1,G_2,…,G_s} be a collection of graphs, and H be a graph.
We say that  packs into H if we can find pairwise edge-disjoint
copies in H of the graphs G_1,…,G_s. If in addition we have
∑_i∈[s]e(G_i)=e(H), we call the packing perfect: in this case,
each edge of H is used in a copy of exactly one G_i.










The study of perfect packings in graphs has a long history, beginning with
Plücker <cit.>, who in 1835 showed that for certain values of n
there is a perfect packing of copies of K_3 into K_n. Steiner <cit.>
in 1853 asked, more generally, when one can perfectly pack the n-vertex
k-uniform complete hypergraph with cliques on r vertices. He phrased the
question as a problem in set theory, and gave some obvious divisibility-based
necessary conditions on n; today such perfect packings are called
combinatorial designs. In 1846 Kirkman <cit.> asked for a
strengthening of Plücker's ideas: when can one have a perfect packing of
spanning K_3-factors (that is, n3 vertex disjoint copies of K_3)
into K_n? Again, he showed that for specific values of n such a thing is
possible. Generalising this in the direction of Steiner one obtains the concept
of a resolvable design; again, it is easy to find divisibility-based
necessary conditions on n.

Despite their simple statement, these problems turned out to be difficult.
Kirkman gave explicit constructions showing that one can perfectly pack K_n
with copies of K_3 if and only if n is congruent to 1 or 3 modulo 6.
But it took more than a century until, in 1975 Wilson <cit.> proved the
(much harder) statement that the necessary divisibility conditions are also
sufficient for cliques of any fixed size in large enough (2-uniform) graphs.
Ray-Chaudhuri and Wilson <cit.> in 1971 solved Kirkman's problem. There was
then another pause, till 2014—up to which time, despite significant work, not
a single example of a non-trivial hypergraph perfect packing for uniformity at
least 6 was discovered—when Keevash <cit.>, in a major breakthrough,
proved that the necessary divisibility conditions are also sufficient for any
fixed clique size and hypergraph uniformity, provided n is large enough. The
problem was re-solved, by a rather different method, by Glock, Kühn, Lo and
Osthus <cit.>, who also solved the problem of perfect
packings with general fixed hypergraphs in place of cliques. In <cit.>,
Keevash made the beautiful observation that a resolvable design is equivalent to
a perfect packing in an auxiliary well-structured hypergraph, and established
the existence of such a packing. Hence, he proved that resolvable designs
exist whenever the obvious necessary conditions are satisfied and n is large
enough.

When one moves away from packings with fixed-size objects (or statements which
can be reduced to such packings), the first positive result is due to Walecki in
the 1800s (see <cit.>), who proved that K_n can be perfectly packed with
Hamilton cycles whenever n is odd. In the 1960s and 70s, interest in this area
was renewed, in particular due to conjectures of Ringel <cit.> and
Gyárfás <cit.> on packings of trees. These conjectures state,
respectively, that K_2n-1 can be packed with 2n-1 copies of any given
n-vertex tree, and that if T_2,…,T_n is any sequence of trees such that
v(T_i)=i, then {T_2,…,T_n} packs into K_n. In both cases, the
packing is necessarily perfect, which makes these conjectures difficult. It is
not too hard to prove either conjecture for stars or paths, and a considerable
amount of effort was put into solving special cases of both cases (for the
former, see the survey of Gallian <cit.>). However until rather
recently, there were no proofs of either conjecture for any reasonably large
family of trees. Then Joos, Kim, Kühn and Osthus <cit.> proved (among
other things) that both conjectures hold when the trees have constant maximum
degree Δ and n is large enough. The proof of this result is very hard,
using a variety of powerful techniques from modern extremal graph theory.

Broadly, the recent solutions to perfect packing conjectures (both, in the case
of combinatorial designs and in the case of tree packing) depend on two
advances: randomised packing methods, and the absorbing method.
The idea is that, rather than
deterministically specifying how to pack, one gives a randomised packing
algorithm and argues that it is likely to succeed. Here `succeed' means packing
almost all (not all) of the graphs, and there will be some edges remaining. This
leftover is dealt with by the absorption method: one should begin by cleverly
choosing an `absorbing packing' of the first few graphs which has the property
that whatever the remaining edges from the randomised algorithm turn out to be,
one can modify the absorbing packing in order to incorporate the leftover to a
perfect packing. In the work of Keevash, roughly this template is followed
(though there are some mild conditions on the leftover), and an intricate algebraic
structure is used to obtain the absorbing packing. In the work of Joos et al.,
the iterative absorption method (originating in <cit.>) is used:
here one packs in a way that uses all the edges adjacent to most vertices and
almost no edges among the remaining few vertices, and then iterates this
process, until all the difficulty has been pushed into a set of vertices so tiny
that a relatively simple absorber suffices.




The idea of randomised packing dates back to Rödl's celebrated nibble
  method <cit.> in which he solved the Erdős-Hanani problem, of
showing that if n is large enough then one can pack most of the edges of the
complete k-uniform n-vertex hypergraph with cliques of size r, solving
Steiner's problem approximately. Note that for this problem there is no
divisibility restriction on n. The nibble method was brought to tree packing
by Böttcher, Hladký, Piguet and Taraz <cit.>, who showed that one can
pack most of the edges of K_n with bounded degree trees, provided the trees
are not too close to spanning. This was the trigger for a sequence of
generalisations: Messuti, Rödl and Schacht <cit.> showed that one can
replace trees with graphs from any non-trivial minor-closed family; Ferber, Lee
and Mousset <cit.> showed that one can additionally allow spanning graphs;
Kim, Kühn, Osthus and Tyomkyn <cit.> discarded the structural assumption
entirely, packing most of the edges of K_n with arbitrary bounded degree
graphs. All these results work in more generality than just for packings in K_n.
In particular, we should note that the results of <cit.> work in the
Szemerédi regularity setting, which was necessary for the proof strategy
of <cit.>.

All the results mentioned so far deal with bounded degree graphs; the first
result to handle growing degrees is due to Ferber and Samotij <cit.>, who
showed that one can pack most of the edges of K_n with trees of maximum degree
O(nlog n) (for almost-spanning trees) or
O(nlog n)^1/6 (for spanning trees). In <cit.> it was proved that one can pack most of the edges of K_n
with arbitrary D-degenerate graphs with maximum degree O(nlog
  n). Finally, recently Montgomery, Pokrovskiy and Sudakov <cit.> were able to deal with trees of unbounded degree, at least in the setting of Ringel's conjecture: they proved an approximate version of Ringel's conjecture, proving that K_2n-1 can be packed with 2n-1 copies of any tree T with n-o(n) vertices.

One might be tempted to think that, while a randomised
strategy is very good for packing most of the edges, one cannot hope for a
perfect packing: After all, at some point one has to pack the
last few graphs, or at least somehow use the last few edges; at this point the
packing is very constrained and any mistake will cause the packing to fail (and
there cannot be many choices left, so that one cannot hope for strong
concentration bounds), but a randomised algorithm will probably make a mistake
(at least, unless it does a good deal of `looking ahead' which will be hard to
analyse). In this paper, however, we show that this thinking is flawed and
a rather natural, simple randomised algorithm can succeed
in giving a perfect packing. Using this algorithm, we prove the following.



 §.§ Main result


A graph G is D-degenerate if every subgraph of G has a vertex of
degree at most D.


  We say that a sequence (G_i)_i∈[m] of graphs is a
  D-degenerate (μ,n)-graph sequence with maximum degree Δ if 
  
  
  * G_i is D-degenerate and Δ(G_i)≤Δ for each i∈[m],
  
  * v(G_i)=n   for each 1≤ i≤ m-⌊μ n⌋, and
  
  * v(G_i)=n-⌊μ n⌋ and G_i has at least ⌊μ n⌋
    leaves for each i with m-⌊μ n⌋<i≤ m.
  
  We also call the G_i with m-⌊μ n⌋<i≤ m the
  special graphs of the sequence.


An n-vertex graph H is (α,k)-quasirandom with density p if
e(H)=pn2 and for every ℓ∈[k] and every set
{v_1,…,v_ℓ} of vertices of H we have

    |N_H(v_1,…,v_ℓ)|=(1±α)p^ℓ n .


Our main result states that a 
D-degenerate (μ,n)-sequence (G_i)_i∈[t] of guest graphs with
maximum degree of order at most n/log n can be perfectly
packed into a sufficiently quasirandom graph H.


  For every D and μ,p̂_0>0 there are n_0 and ξ,c>0 such that for
  every p̂≥p̂_0, every n≥ n_0, and every m, the following holds
  for every n-vertex graph H which is (ξ,4D+7)-quasirandom
  with density p̂. Every D-degenerate (μ,n)-graph sequence
  (G_i)_i∈[m] with maximum degree cn/log n such that
  ∑_i∈ me(G_i)≤ e(H) packs into H.


It is easy to see (and proved for completeness in Proposition <ref>)
that if
T is a uniform random labelled n-vertex tree, then for each c>0, with probability
1-e^-O(n) the tree T will have at least n/100 leaves and maximum degree
at most cnlog n. In particular, we have the following corollary to
Theorem <ref>, proving almost all cases of Ringel's conjecture and the
Gyárfás Tree Packing Conjecture.


  Let T be a uniform random n-vertex tree. With probability 1-e^-O(n),
  there is a packing of 2n-1 copies of T into K_2n-1.
 
  Let T_2,…,T_n be chosen independently and uniformly at random such that
  T_i is an i-vertex tree for each 2≤ i≤ n. With probability at least 
  1-e^-O(n), there is a packing of {T_2,…,T_n} into K_n.

We should briefly compare these results to the earlier result of Joos, Kim,
Kühn and Osthus <cit.>. On the one hand, we cannot handle trees with few
leaves, so our result does not contain theirs. Furthermore, as far as
Corollary <ref> goes, packing bounded degree trees `almost' covers a
typical uniform random tree, whose maximum degree is likely to be
Θ(log nloglog n), and most likely the approach
of <cit.> could be pushed to allow for a few vertices of logarithmic
degree: this would prove something like Corollary <ref>, though the failure probability would be polynomial rather than exponential in n (the probability of having a vertex of at least logarithmic degree is only polynomially small). On the other hand, the method of <cit.> heavily
relies on the structure of trees, and in particular that one can embed them
effectively in a Szemerédi partition; handling general degenerate graphs with
high maximum degree would be rather challenging with their approach.

Finally, we discuss which conditions in Theorem <ref> are needed.
It is easy to see that a typical graph H on n vertices with density 1/2 will be
quasirandom. However such a graph will typically not
contain any 110log n-set S of vertices such that each other vertex
has a neighbour in S.
In particular, if G is an n-vertex graph which is the vertex
disjoint union of 110log n stars, each with the same number of leaves
(up to an error 1), then G has maximum degree less than 20nlog
  n but does not embed into H. Thus the maximum degree
bound in our theorem is optimal up to a constant factor.

One can allow D to grow with n. Examination of our proof shows it can grow
roughly as logloglog n, but this is presumably not optimal. On the other
hand, D cannot be as big as 10log n, since a typical random graph is
unlikely to contain any given graph with 9nlog n edges.

We cannot allow all graphs to be spanning in Theorem <ref>, as an
example in <cit.> shows. However we expect one can do better than needing
linearly many graphs to be linearly far from spanning.

We do not believe that it is necessary to have many graphs with many leaves. We
should note that one cannot simply omit this condition, because for example no
collection of cycles can perfectly pack K_2n, due to a parity obstruction:
cycles use an even number of edges at each vertex, but K_2n has odd degree
vertices. However for the case D=1 (i.e. forests) we believe one can omit the
condition entirely (as the leaves should allow for parity correction). Work on
this problem is work in progress with Hladký and Piguet.



 §.§ Proof outline


This paper builds on <cit.>, so we begin by outlining the randomised algorithm
 described there (and repeated here later). In
, we embed graphs one-by-one into H. To embed a
given graph, we take the vertices in the degeneracy order, and one by one embed
them: at each step, we choose from the set of all vertices to embed to which do
not immediately break our packing (either by re-using a vertex already used in
the current embedding or by re-using an edge already used for a previous graph)
uniformly at random. We do this until almost the entire graph is embedded; then
we choose arbitrarily a way of completing the embedding to a spanning
embedding. (This is a slight simplification, but the simplification does
  not affect the point.) Note that here we certainly do not `look ahead' in any
way at what we will embed in the future, and the algorithm is essentially purely
random. 

To prove our main theorem, we will begin by removing some
of the leaves from each special graph in a given (μ,n)-graph sequence. We
will then use  to pack all the non-special graphs
and all the special graphs minus the removed leaves into
H. It
remains to embed these removed leaves into the graph H consisting of the
unused edges of H. We say a removed leaf is dangling at a
vertex v∈ V(H) if its parent is embedded to v. We will show that at each
vertex of H, it is likely that there are about twice as many edges as dangling
leaves. In order to decide where to embed the dangling leaves, we first orient
the edges of H randomly, then `correct' this orientation (by reversing a few
carefully chosen directed paths of length 2) such that the out-degree of each
vertex is equal to the number of dangling leaves. This is the only step in our algorithm
where we
`look ahead' and prepare for the future.

We then complete the packing by going through H vertex-by-vertex, and for each
vertex choosing a uniform random assignment of the dangling leaves to the
out-neighbours which preserves having a packing. We should note that this last
step has some similarity to the approach of <cit.>, where the
authors also complete their perfect packing by assigning dangling leaves to
out-neighbours, but in a small set of vertices. However in their setting, they
only need to assign one dangling leaf per tree, and no other vertices of that
tree are embedded to the small vertex set. As they already did all the hard work
to reach this point, it is not hard for them to make such an assignment. In our
setting, we need to embed linearly many dangling leaves per tree, which dangle
on many different vertices, and the previously embedded images of these trees
can cover most of the vertices to which we want to embed dangling leaves. It is
already non-trivial that we can even assign the dangling leaves at the first
vertex of H, and this assignment affects what we can do at later vertices.

In order to understand how it can be that this random process succeeds in
obtaining a perfect packing, one should note that when we embed the dangling
leaves at the first vertex of H, we have no choice over the set of edges we
use (these are fixed as the out-neighbours) but the set of assignments, from
which we choose uniformly, is rather large. This property is preserved right
through to the last vertex of H—even in the last step, we have not one but
many possible assignments to choose from, so that even in the last steps we have
quite a lot of randomness.



 §.§ Organisation


In Section <ref> we fix notation and collect some concentration
inequalities and facts about degenerate graphs. In Section <ref> we
state our main technical theorem, show that it implies Theorem <ref>,
and formalise our random packing process. In Section <ref> we fix the
constants we will use throughout our proofs. In Section <ref> we
provide our main lemmas which analyse what happens in the different phases of
our packing process: the almost perfect packing lemma, the orientation
lemma, and the matching lemma. In Section <ref> we show that these
lemmas imply our main technical theorem.  Section <ref> proves the
orientation lemma, Section <ref> the matching lemma, and
Section <ref> the almost perfect packing lemma. The latter takes up the
(technical) bulk of the paper. Concluding remarks are given in Section <ref>.



§ PRELIMINARIES





 §.§ Notation



For a graph G we write V(G) for the vertices of G, and E(G) for its
edges, v(G) for the number of vertices in G, and e(G) for the number
of edges.
For disjoint vertex sets X,Y⊂ V(G) we write G[X] for the subgraph
of G induced by X, and G[X,Y] for the bipartite subgraph of G on
vertex set X∪ Y and with all edges of G with one end in X and the
other in Y. For a set S of vertices of G, we write N_G(S) for the common neighbourhood {u∈ V(G):su∈ E(G) for each s∈ S}. We write _G(S):=|N_G(S)| for the common degree of S in G. When S={v_1,…,v_ℓ} we will omit the set braces and simply write N_G(v_1,…,v_ℓ) and _G(v_1,…,v_ℓ). We will not use joint neighbourhoods of sets of vertices in this paper.

Given a graph G and a set of vertices X, if X⊂ V(G) we write G-X for the graph obtained by removing the vertices X from V(G), i.e. G[V(G)∖ X]. If X is disjoint from V(G), we write G+X for the graph obtained by adding X as a set of isolated vertices, i.e. the graph on vertex set V(G)∪ X whose edge set is E(G). Given graphs G_1 and G_2 with V(G_2)⊂ V(G_1), we write G_1-G_2 for the graph obtained by removing the edges of G_2 from G_1, i.e. the graph on vertex set V(G_1) whose edge set is E(G_1)∖ E(G_2).

Given an ordering V(G)={v_1,…,v_n} of the vertices of a graph G, we write _G(v_i) for the left-neighbourhood of v_i, i.e. the set

    _G(v_i):=N_G(v_i)∩{x_k:  k∈ [i-1]} .

We write _G(v_i):=|_G(v_i)| for the left-degree of
  v_i, and say the order is a D-degenerate order if for each
i∈[n] we have _G(v_i)≤ D.

An orientation of a graph H=(V,E) is an oriented graph on V
which contains, for each undirected edge uv∈
E, exactly one directed edge, either u⃗v⃗ or v⃗u⃗.
The outdegree ^+_H⃗(v) of a vertex v in an oriented
graph H⃗ is the number of vertices u in H⃗ such that v⃗u⃗
is an edge of H⃗; the set of these vertices u is the
outneighbourhood N^+_H⃗(v) of v.



Let
  Ω be a finite probability space. A filtration ℱ_0,
  ℱ_1,…, ℱ_n is a sequence of partitions of Ω
  such that ℱ_i refines ℱ_i-1 for all i∈[n]. In
  our application, the partition ℱ_i is given by all possible
  histories of the run of one of our algorithms up to time i. (For more
  explanation see <cit.>.) We say that a function f:Ω→ℝ is ℱ_i-measurable if f is constant on each
  part of ℱ_i. Further, for any random variable
  YΩ→ℝ the conditional expectation
  (Y|ℱ_i)Ω→ℝ and the
  conditional variance (Y|ℱ_i)Ω→ℝ
  of Y with respect to ℱ_i are defined
  by
  
    (Y|ℱ)(x)   =(Y|X),
    (Y|ℱ)(x)   =(Y|X),
            where X∈ℱ is such that x∈ X .


Suppose that we have an algorithm which proceeds in m rounds using a new
source of randomness Ω_i in each round i. Then the probability space
underlying the run of the algorithm is ∏_i=1^mΩ_i. By
history up to time t we mean a set of the form
{ω_1}×⋯×{ω_t}×Ω_t+1×⋯Ω_m, where ω_i∈Ω_i. We shall use the
symbol _t to denote any particular history of such a form. By a
history ensemble up to time t we mean any union of histories up to time
t; we shall use the symbol  to denote any one such. Observe that
there are natural filtrations associated to such a probability space: given
times t_1<t_2<… we let ℱ_t_i denote the partition of
Ω into the histories up to time t_i.



 §.§ Probabilistic tools


  
   
  Suppose
  X is a random variable which is the sum of a collection of independent Bernoulli random variables.
  Then we have for δ∈(0,3/2)
 
    [X>(1+δ)  X]<e^-δ^2 X/3  and  [X<(1-δ)  X]<e^-δ^2 X/3 .

  

  We use the following consequence of Freedman's inequality <cit.>,
  derived in <cit.>, for analysing our random embedding algorithms. 

  
    
    Let Ω be a finite probability space, and (ℱ_0,
    ℱ_1,…,ℱ_n) be a filtration. Suppose that we
    have R>0, and for each 1≤ i≤ n we have an ℱ_i-measurable
    non-negative random variable Y_i,
    nonnegative real numbers ,  and
    , and an event . Suppose that almost surely, either  does
    not occur or we have
    ∑_i=1^n[Y_i|ℱ_i-1]=±, and
    ∑_i=1^n[Y_i|ℱ_i-1]≤^2, and 0≤
    Y_i≤ R for each 1≤ i≤ n. Then for each >0 we have
    
    [ and ∑_i=1^nY_i≠±(+)]≤2exp(-^2/2^2+2R) .

    Furthermore, if we assume only that either  does not occur or we have
    ∑_i=1^n[Y_i|ℱ_i-1]≤+, and
    ∑_i=1^n[Y_i|ℱ_i-1]≤^2, and 0≤
    Y_i≤ R for each 1≤ i≤ n, then for each >0 we have
    
    [ and ∑_i=1^nY_i>++]≤exp(-^2/2^2+2R) .



A special case is the following corollary.


  Let Ω be a finite probability space, and (ℱ_0,
  ℱ_1,…,ℱ_n) be a filtration. Suppose that we have
  R>0, and for each 1≤ i≤ n we have an ℱ_i-measurable
  non-negative random variable Y_i, nonnegative real numbers , and
  an event .
  
  
  *  Suppose that either  does not occur or
    we have ∑_i=1^n[Y_i|ℱ_i-1]≤,
    and 0≤ Y_i≤ R for each 1≤ i≤ n. Then
    
    [ and
            ∑_i=1^nY_i >2] ≤exp(-/4R) .

  
  *  Suppose that either  does not occur or we
    have ∑_i=1^n[Y_i|ℱ_i-1]=±,
    and 0≤ Y_i≤ R for each 1≤ i≤ n. Then for each >0 we have
    
    [ and
            ∑_i=1^nY_i≠±(+)] ≤2exp(-^2/2R(++)) .

    In particular, if ==>0 and ≤1/2, then
    
    [ and
            ∑_i=1^nY_i≠(1± 2)] ≤2exp(-^2/4R) .

  


Both parts follow from Lemma <ref> with
^2=R(+); for
the first part we also set =0 and
=. Observe that

    [Y_i|ℱ_i-1]≤[Y_i^2|ℱ_i-1]≤ R·[Y_i|ℱ_i-1] ,

so that

    ∑_i=1^n[Y_i|ℱ_i-1]≤ R∑_i=1^n[Y_i|ℱ_i-1]≤ R(+)

when  holds, justifying the choice of ^2.


We conclude this subsection by proving maximum degree and leaf statistics for random labelled trees.

 Let T_n be a tree chosen uniformly at random from the set of n-vertex labelled trees. Then

 
  *  With probability at most exp(-n500) the number of leaves in T_n is less than n100.
 
  *  Given c>0, if n is sufficiently large then with probability at most e^-cn/2 there is a vertex in T_n with degree greater than cnlog n.



 To prove both probability bounds, we use the well-known Prüfer code bijection between labelled n-vertex trees and sequences of n-2 vertex labels.
 
 For <ref>, we note that a vertex is a leaf if and only if its label does not appear in the corresponding Prüfer code, and hence the Prüfer code of a tree with less than n100 leaves has at least 49n50 distinct labels. Consider generating the first n2 terms of a Prüfer code. If there are less than n4 distinct labels, then the full code has less than 3n4 distinct labels and hence corresponds to a tree with at least n100 leaves. Otherwise, there are at least n4 distinct labels among the first n2 terms. We now count the number of times that these labels are used in the subsequent n2-2 terms. Each term is chosen uniformly at random from the set of all n vertex labels, hence has probability at least 14 of repeating a label used in the first n2 terms. Thus the expected number of repeated labels is at least 14(n2-2)≥n16. By the Chernoff bound, Theorem <ref>, with δ=12 the probability that less than n32 repeated labels occur is at most exp(-n500).
 
 For <ref>, we note that a vertex has degree equal to one plus the number of its appearances in the Prüfer code. Thus a vertex has degree exceeding cnlog n only if its label appears cnlog n times in the Prüfer code. For a given vertex label and choice of cnlog n terms of the Prüfer code, the probability that each of the chosen terms is equal to the given label is n^-cnlog n=e^-cn. Taking the union bound over the choices of vertex label and terms of the code, the probability that some vertex label appears at least cnlog n times is at most
 
    n·n-2cnlog n· e^-cn≤ n·(nlog ncn)^cnlog ne^-cn=exp(log n+cnlog(c^-1log n)log n-cn)≤ e^-cn/2 ,

 where the final inequality is valid for all sufficiently large n.


We should point out that much more precise statistics are known; we give these rough and simple bounds for completeness.



 §.§ Degenerate graphs


It is easy to show that degenerate graphs contain large independent sets all of whose vertices have the same degree.


  Let G be a D-degenerate n-vertex graph. Then there exists an integer
  0≤ d≤ 2D and a set I⊆ V(G) with |I|≥ (2D+1)^-3n which is
  independent, and all of whose vertices have the same degree d in G.


In <cit.> this was used to show that one can modify a degeneracy order
slightly to move such an independent set to the end of the order while not
increasing the degeneracy by much. We repeat the straightforward argument here
for completeness.


  
  Let G be a D-degenerate n-vertex graph. Then there
  exists an integer
  0≤ d≤ 2D
  and a 2D-degenerate order of V(G) such that the last ⌈(2D+1)^-3n⌉
  vertices in this order form an independent set and all have degree d.


  By Lemma <ref> there is an independent set I in G of ⌈
  (2D+1)^-3n⌉ vertices, each of which has degree d. Now pick a
  D-degenerate order of G and then modify this order by moving all vertices
  of I to the end (in an arbitrary order). Since all vertices in I have
  degree d≤ 2D the resulting order is 2D-degenerate.

  
Further, we shall use the following auxiliary lemma, which given an arbitrary family of
graphs we want to pack produces a family with at most 3/2 n members and
the same bound on maximum degree and degeneracy by combining graphs with many
isolated vertices in the family. Obtaining such a family with at most 3/2
n members needs some argument; while obtaining a family with at most 2n
members instead is straightforward. In <cit.> we only used the latter, and
the reason why we use the smaller family here is that it allows us to
stay consistent with the constants used in <cit.>. More precisely, the
constant α_2n that will be defined in (<ref>) is not small
enough for our analysis here, while α_7n/4 is small enough.


  
  Let (G_i)_i∈[m] be a family of D-degenerate graphs
  with maximum degree at most Δ, with ∑_i=1^m
  e(G_i)≤n2 and v(G_i)≤ n for all i∈[m]. Then there is a
  family of graphs (Ǧ_i)_i∈[m̌] with m̌≤3/2 n
  such that ∑_i=1^m̌ e(Ǧ_i)≤n2, such that for
  each i∈[m̌] we have v(Ǧ_i)≤ n, Δ(Ǧ_i)≤max{2,Δ}, and Ǧ_i is max{2,D}-degenerate, and
  such that (Ǧ_i) is a packing of (G_i).


  Given the family (G_i), repeatedly perform the following operation,
  packing two members of the family into one graph.
  If the current family contains two graphs G, G' which have at most
  2/3 n vertices of degree at least 1 and at most 1/3 n
  vertices of degree at least 2 then pack G and G' into a graph G”
  as follows and then remove G, G' from the family and add G” instead.

  To define an embedding ϕ of G' into G̅, let A,B,C⊂
  V(G) be a partition of V(G) into sets of size either ⌊n3⌋ or ⌈n3⌉, such that |A|=|C|, and such that 
  _G(x)=0 for all x∈ A and _G(x)≤ 1 for all x∈ B,
  which is possible by our assumptions on G.
  Analogously, let A',B',C'⊂
  V(G') be  a partition of V(G') into sets of size either ⌊n3⌋ or ⌈n3⌉, such that |A'|=|C'| and such that
  _G'(x)=0 for all x∈ A' and _G'(x)≤ 1 for all x∈ B'.
  We construct ϕ by first finding
  a packing of G[B] and G'[B'] (which is easy since these two graphs
  are matchings and |B|≥3) and then extending this by arbitrarily mapping A' to C
  and C' to A. Note that by construction |A|=|A'|=|C|=|C'|. Clearly, this indeed gives a packing of G and G'
  since vertices in A have degree 0 in G and vertices in A' have
  degree 0 in G'. Moreover, Δ(G”)≤max{2,Δ}, and G” is
  max{2,D}-degenerate by construction.

  We stop combining graphs in this way when at most one graph with at most 
  2/3 n vertices of degree at least 1 and at most 1/3 n
  vertices of degree at least 2 remains; we call the resulting family (Ǧ_i)_i∈[m̌].
  In this family, all graphs Ǧ_i but possibly one graph satisfy at least
  one of the following conditions:
  
    
  * Ǧ_i has more than 2/3 n vertices of degree at least 1,
    
  * Ǧ_i has more than 1/3 n vertices of degree at least 2.
  
  In either case e(Ǧ_i)≥1/3 n, and therefore we conclude from
  ∑_i=1^m̌ e(Ǧ_i)=∑_i=1^m e(G_i)≤n2 that
  
    m̌≤ 1+n2/1/3 n≤3/2 n .






§ MAIN TECHNICAL THEOREM AND THE PACKING ALGORITHM


In this section we detail our packing algorithm, introduce the definitions
necessary for this algorithm, and outline the proof of why this algorithm succeeds.
We deduce Theorem <ref> from the following technical result.


  For every D and μ,p̂_0>0 with μ≤1/4 there are n_0 and ξ,c>0 such that for
  every p̂≥p̂_0 and every n≥ n_0 the following holds. Suppose that H is a
  (ξ,2D+3)-quasirandom graph with n vertices and density p̂.
  Suppose that s^*≤7/4 n and that the graph sequence (G_s)_s∈[s^*]
  is a D-degenerate (μ,n)-graph sequence with maximum degree
  Δ≤cnlog n, such that for each s∈[s^*] there is a
  D-degenerate order of G_s such that
  the last ⌈(D+1)^-3n⌉ vertices
  form an independent set in G_s, and all have the same
  degree d_s in G_s. Suppose further that
  ∑_s∈[s^*]e(G_s)=e(H). Then (G_s)_s∈
    [s^*] packs into H.


Before sketching the proof of Theorem <ref>, we show that it
implies Theorem <ref>.
 

  Given D, μ, p̂_0, let n'_0, ξ, c be as given by
  Theorem <ref> for input D'=2max{2,D},
  μ'=min{μ,1/4}, and p̂_0. Choose n_0=max{n_0',10c^-2}.
  Next,
  let p̂ and n as well as the graphs H and (G_i)_i∈[m] be
  given.

  Now we first add new graphs G_i with i>m consisting of single edges to our
  graph sequence until ∑ e(G_i)=e(H). Assume that the resulting
  sequence has m' graphs and reorder the sequence so that the ⌊μ n
  ⌋ special graphs come last.
  In a second step we apply the compression lemma, Lemma <ref>, to
  the non-special graphs (G_i)_i∈[m'-⌊μ' n⌋] to obtain a
  family (Ǧ_i)_i∈[m̌] with m̌≤3/2 that is a
  packing of (G_i)_i∈[m']. In a third
  step, we add
  the remaining special graphs to this compressed family, that is, for 1≤ i≤⌊μ' n⌋ we let Ǧ_m̌+i=G_m'-⌊μ'
      n⌋+i. We obtain a family (Ǧ_s)_s∈[s^*] of
  max{2,D}-degenerate graphs with maximum degree at most cn/log n, where
  s^*≤3/2 n+⌊μ' n⌋≤7/4 n. In a fourth step, we apply
  Lemma <ref> to obtain a D'-degenerate order of each Ǧ_s
  such that the last ⌈ (D+1)^-3n ⌉≥⌈ (D'+1)^-3n ⌉ vertices
  form an independent set in Ǧ_s, and all have the same
  degree d_s in Ǧ_s. Hence the family (Ǧ_s)_s∈[s^*] satisfies
  all conditions required by Theorem <ref> with the above chosen
  constants. Since H is (ξ,4D+7)-quasirandom, it is also (ξ,2D'+3)-quasirandom as required for Theorem <ref>. Applying this theorem, we obtain a perfect packing of  (Ǧ)_s∈[s^*] into
  H, which gives a packing of (G_i)_i∈[m] since (Ǧ)_s∈[s^*]
  is a packing of (G_i)_i∈[m] (plus possibly some additional edges).


We now sketch the proof of Theorem <ref>. We start by creating an almost perfect packing, which omits linearly many leaves
in the linearly many special graphs G_s, by packing only the following
subgraph sequence omitting ℓ=⌊ν n⌋ leaves.


  For a D-degenerate (μ,n)-graph sequence (G_s)_s∈[s^*] with
  maximum degree Δ, we say that (G'_s)_s∈[s^*] is a
  corresponding subgraph sequence omitting ℓ leaves if
  
    
  *  for each s≤ s^*-⌊μ n⌋ we have G'_s=G_s, and
    
  *  for each s>s^*-⌊μ n⌋ we have G'_s=G_s-V_s+I_s
      for an independent set V_s of leaves in G_s with |V_s|=ℓ, and a set
      I_s of new and independent vertices with |I_s|=ℓ.
  


We remark that the addition of the independent set I_s
in <ref> is purely for technical reasons: it guarantees that
the special G'_s have n-⌊μ n⌋ vertices, which makes the
statement of some of our later lemmas easier (in particular Lemma <ref>). The restriction that the set V_s is independent simply says that if there is a component of G_s which contains exactly one edge, both endpoints are leaves but only one may be in V_s.

The subgraph sequence (G'_s) is packed with the help of the following
, which uses an algorithm  that we shall
describe thereafter. This  was introduced and analysed
in <cit.>, and it requires n-vertex graphs with a degeneracy ordering
whose last vertices form an independent set as input. To that end, for each
s∈[s^*] with s>s^*-⌊μ n ⌋, we do the following. We let I'_s be a set of n-v(G'_s) new
isolated vertices and we obtain G”_s by adding I'_s to G'_s. Each
non-special graph G'_s, with s≤ s^*-⌊μ n⌋, already has n
vertices and so we simply set G”_s=G'_s. For the special graphs G'_s, with
s>s^*-⌊μ n⌋, we fix a D-degenerate order of G”_s such that
the ⌊μ n⌋>δ n isolated vertices in I'_s come last. We
then relabel vertices, so that again V(G”_s)=[n] and the fixed D-degenerate
order is the natural order on [n].





For describing  we need the following definitions. We shall use the symbol  to denote embeddings produced by . We write G H to indicate that the graph G is to be embedded into H. Also, if t∈ V(G), v∈ V(H) and A⊂ V(H) then t v means that t is embedded on v, and t A means that t is embedded on a vertex of A.


  Let G be a graph with vertex set [v(G)], and H be a graph with
  v(H)≥ v(G).
  Further, assume ψ_j[j]→ V(H) is a partial embedding
  of G into H for j∈[v(G)], that is, ψ_j is a graph embedding
  of G[[j]] into H. Finally, let t∈[v(G)] be such that _G(t)⊂[j].
  Then the candidate set of t (with respect to ψ_j) is the
  common neighbourhood in H of the already embedded neighbours of t,
  that is,
  
    _G H^j(t)=N_H(ψ_j(_G(t))) .



 (see Algorithm <ref>) randomly embeds most of a guest graph G into a host
graph H. The algorithm is simple: we
iteratively embed the first (1-δ)n vertices of G randomly to one
of the vertices of their candidate set which was not used for embedding
another vertex already.

  

If successful,  returns the packing
(ϕ^*_s)_s∈[s^*] of (G”_s)_s∈[s^*] and a leftover graph
H. For each s∈[s^*], we obtain an embedding ϕ'_s of G'_s into
H from the embedding ϕ^*_s of G”_s into H
by ignoring the vertices of G”_s which are not in G'_s. Recall that
all these vertices are isolated vertices. It follows that the
(ϕ'_s)_s∈[s^*] give a packing of (G'_s)_s∈[s^*] into
H which leaves unused exactly the edges of H. 
In <cit.> it was shown that  is indeed a.a.s.successful.
We shall use the techniques developed there
to show in Lemma <ref> that moreover  
returns a packing of (G'_s)_s∈[s^*] and a leftover graph with suitable properties for the
following steps.
  
It remains to pack all the leaves
we omitted from (G_s)_s∈[s^*]. For this we shall proceed vertex by vertex of the remaining
host graph H, and when
considering r∈ V(H) we shall randomly embed all leaves dangling at r, that is, the leaves of all guest
graphs such that the neighbour of the leaf is already embedded to r.
For describing this process in more detail, we will need the following
definitions.
  
  
    Let (G_s)_s∈[s^*] be a (μ,n)-graph sequence, and (G'_s)_s∈[s^*] be a
    corresponding subgraph sequence, H be an n-vertex graph, and
    ϕ'_s V(G'_s)→ V(H) be an injection for each s∈[s^*]. For
    s^*-⌊μ n⌋<s≤ s^* we define for each x∈ V(G_s) the weight 
    
    w_s(x)=|{y∈ N_G_s(x) y  is a leaf of G_s in G_s-G'_s}| ,

    and for each v∈ V(H) the weight
    
    w_s(v)=w_s(ϕ'_s^-1(v)) .

    Further, for each v∈ V(H) we define
    
    w(v)=∑_s^*-⌊μ n⌋<s≤ s^*w_s(v) .

  
  Note that since each set V_s of omitted leaves is an independent set in G_s, the weight of an omitted leaf is 0. Thus the entire weight of G_s (which is ℓ, the number of omitted leaves) is on the vertices in G'_s embedded by ϕ'_s.
  We next choose an orientation  of H such that N^+_(r)=w(r)
  for each r∈ V(H). We shall show in Lemma <ref> that we can
  choose an orientation with this property which is moreover random-like
  (in the sense that it suitably inherits the properties guaranteed by Lemma <ref>).
  The idea now is to embed the remaining leaves dangling at r by  using only edges directed away from r.
  We define the following auxiliary graphs, which encode the ways in which
  we can embed the dangling leaves.
  
  
   Given r∈ V(), we define the leaves at r to be the set
   
    L_r:={x∃ s such that  x∈ V(G_s)∖
         V(G'_s)  and  xϕ'^-1_s(r)∈ E(G_s)}

   Let the leaf matching graph F_r be the bipartite graph with parts L_r and N^+_(r), and edges xu with x∈ L_r and u∈ N^+_(r)
   whenever u∉ϕ'_s for the s such that x∈ V(G'_s).
  

  Observe that a perfect matching in F_r defines an assignment of the
  leaves at (all preimages of) r to N^+_(r) which extends the packing of (G'_s)_s∈[s^*]. We will see that each F_r is a graph whose parts have size roughly 12pn and whose density is roughly μ. If we simply chose a perfect matching in each F_r to embed all the leaves ⋃_rL_r, then we would almost have a perfect packing—each edge of K_n would be used exactly once—but it could be the case that multiple leaves of some G_s (not in the same L_r) are embedded to a single u∈ V(H). To avoid this, we find perfect matchings in each F_r one at a time and update the leaf matching graphs by removing edges which are no longer useable. In order that not too many edges are removed from any one vertex in any F_r, we choose perfect matchings uniformly at random. Making this precise, assume V()={1,…,n}, and set F_r^(0):=F_r for each r∈ V(). We use the following algorithm.
  
  
  We shall show that, throughout, the graphs F_k^(r) satisfy a certain
  degree-codegree condition. We shall show in
  Lemma <ref> that under this degree-codegree condition we can
  find a perfect matching in F_r^(r-1). Further, the same lemma asserts that a perfect matching σ_r chosen
  uniformly at random in F_r^(r-1) uses edges almost uniformly, which is
  important for maintaining the degree-codegree condition.

  We will then, for each s∈[s^*] and each x∈ V(G_s) set
  
    ϕ_s(x)=ϕ'_s(x)     if x∈(ϕ'_s)
    σ_r(x)     if x∈ L_r .

 This is a perfect packing of (G_s)_s∈[s^*] into H since
 (ϕ'_s)_s∈[s^*] is a packing of the subgraph sequence
 (G'_s)_s∈[s^*] into H and we chose matchings in the leaf
 matching graphs F_r^(r-1) to embed the remaining leaves and updated
 the subsequent leaf matching graphs accordingly.

Summing up, our packing algorithm proceeds as described in Algorithm <ref>.

  



 §.§ Graphs and maps used in the algorithm


As described above, a number of different (auxiliary) graphs and maps are used in
our packing procedure. For the convenience of the reader we collect these in the
following table.



  G_s are the given n-vertex guest graphs, forming a D-degenerate
  (μ,n)-graph sequence, whose last ⌊(D+1)^-3n⌋ vertices form
  an independent set.

  G'_s is in the subgraph sequence corresponding to (G_s)_s∈[s^*]
  omitting ⌊ν n ⌋ leaves; the special G'_s have n-⌊μ n ⌋ vertices, the others n.

  G”_s is obtained from G'_s by adding isolated vertices to the end of
  the degeneracy order until we have n vertices.

  H is the given n-vertex (ξ,2D+3)-quasirandom host graph.

  H_s-1 is the part of H used by  to embed G”_s[[n-δ
  n]].

  H_s-1^* is the part of H used in  to
  complete the embedding of G”_s.

  H is the leftover host graph after running .

   is a random-like orientation of H with as many outgoing edges for
  each vertex r as there are leaves dangling at r.

  F_k^(r) is what remains of the leaf matching graph F_k after round r of . 

  ϕ”_s embeds G”_s[[n-δ
  n]] into H_s-1 and is constructed by .
  

  ϕ_s^* is an extension of ϕ”_s, embedding G”_s into
  H_s-1∪ H^*_s-1 constructed in .

  ϕ'_s is an embedding of G'_s into H obtained from
  ϕ_s^* by ignoring the added isolated vertices.

  ϕ_s is an embedding of G_s into H obtained from
  ϕ'_s and the σ_r in .

  ψ_t is the partial embedding obtained in round t of .

  σ_r is the matching in the leaf matching graph F_r^(r-1) found
  by .

  


§ CONSTANTS



In this section we set values for the various constants we need throughout our proofs (including
those used in the algorithms above), which are the following.



  α_x is the error in the quasirandomness of H_x.

  α is a quasirandomness error used in auxiliary lemmas; we
  always assume α_0≤α≤α_2n.

  β_t is the error in the diet-condition (see
  Definition <ref>) for round t of .

  c is the constant in the maximum degree bound of the G_s.

  C appears in the error term for the probability of embedding a fixed
  vertex of G”_s on a fixed vertex of H_s-1.

  C' appears in the error term for the fraction of vertices of certain
  sets that get covered by embedding one graph G”_s

  D is the degeneracy bound of the guest graphs G_s.

  n_0 is the lower bound on the number n of vertices.

  p̂ is the density of the host graph H.  

  p̂_0 is the lower bound on p̂.

  p is the density of the leftover host graph H after running 
   to embed the subgraph sequence.

  p_s is the density of the graph H_s.

  δ is the proportion of vertices in G”_s formed by the
  independent set at the end of the degeneracy order as required by .

   gives the length n of intervals in V(G_s) used in
  the cover condition (see Definition <ref>); it also appears in
  the error term of the cover condition.

  η is the error in the quasirandomness of H_0^*.

  γ is the proportion of host graph edges used by
   to complete almost spanning embeddings to spanning embeddings.

  γ' determines the error bound in our analysis here of .

  μ specifies the fraction of special G_s, how far they are from spanning and how many leaves they have.

  ν specifies the fraction of leaves omitted in the subgraph sequence.

  ξ is the error in the quasirandomness of H.


The constants D, p̂ and μ are provided as input to our main
technical theorem; the other constants are chosen to satisfy

    0≪1/n_0,c≪≤ξ≪α_0≤α_2n≤1/C'≪1/C≪δ≪η≪γ≪γ'≪ν≪μ,p̂_0,1/D .

Here a≪ b means that we choose a sufficiently small in terms of b, so
that our calculations work. In other words, there is a monotone increasing function
fℝ_>0→ℝ_>0 with f(b)≤ b such that we choose a=f(b).

For the constants ν, γ', γ, and n_0 we do not provide
explicit dependencies (mainly because Lemma <ref>, which we take from
elsewhere, does not provide explicit dependencies), but merely state that we can choose them suitably with
the above relations.






The various host graph densities satisfy the following relations. We have p̂≥p̂_0.
Given n≥ n_0, the density p is determined by 

    p=⌊μ n⌋⌊ν n⌋n2^-1 .

Moreover, in our later proofs we will assume that
e(H_0^*)=(1±1/10)γn2,
which can be seen to hold with probability 
larger than 1-e^-n by an application of Theorem <ref>.
Then, since the density of H is p̂, the density of H_0 is
p_0≥p̂-1.1γ, and therefore, because  embeds
∑_s∈[s^*]e(G_s)-⌊μ n ⌋⌊ν n ⌋≤p̂n2-⌊μ n ⌋⌊ν n ⌋
edges we have

    p_s≥p̂-1.1γ-p̂n2-⌊μ n ⌋⌊ν n ⌋/n2≥νμ-1.1γ≥γ     for all s∈[s^*] .


The remaining constants are only used in the proof of the most technically involved of our main lemmas,
Lemma <ref>.
These are defined precisely in the same way as
in <cit.> apart from C', which is added here.[The density of the
  host graph H is denoted by p in <cit.>; we
  denote it by p̂ here.]
This is important, because much of our proof of Lemma <ref> builds on
tools developed in <cit.>, and the relation of the constants involved is
somewhat more intricate.


  Let D,n∈ℕ and p̂,γ>0 be given. We define
  
    η   =γ^D/200D ,  δ=γ^10Dη/10^6D^4 ,  
          C=40Dexp(1000Dδ^-2γ^-2D-10) ,  
          C'=10^4Cδ^-1 , 
    α_x   =δ/10^8CDexp(10^8CD^3δ^-1(x-2n)/n)     for each x∈ℝ,
       = α_0δ^2γ^10D/1000CD ,   c= D^-4^4/100   and  ξ=α_0/100 .

  Moreover, given α>0 we use the following constants
  β_t(α), which are
  chosen such that β_0(α)=α and such that
  β_v(G)(α)/β_0(α) is bounded by a constant which does not depend on
  α (though it does depend on D, γ and δ). We define
  
    β_t(α) =2αexp(1000Dδ^-2γ^-2D-10tn) .




  When using the constants α_x, β_t, we will mainly take x and t integer in
  the range [0,2n], but it is convenient to allow them to be any real
  number.

  Note that we call α_x and β_t `constant' even
  though n appears in their definition. 
  It is easy to check though that
  α_x is strictly increasing in x and β_t is strictly
  increasing in t and
  that neither α_0,β_0 nor α_2n,β_2n depends on
  n. Further, for each t≥ 0, we have
  
    1n∫_i=0^t 1000Dδ^-2γ^-2D-10β_i  di
    ≤   2α∫_i=-∞^t
          1000Dδ^-2γ^-2D-10/nexp(1000Dδ^-2γ^-2D-10in)
           di
          =β_t .





§ MAIN LEMMAS



In this section we collect the main lemmas we need for the proof of our main technical
theorem.
Our first lemma states that the randomised algorithm
 generates an almost perfect packing of the
corresponding subgraph sequence of our guest graphs such that this packing
and the leftover H of the host graph satisfy certain properties. We prove this
lemma in Section <ref>. The fact that  produces a
packing of this type such that the leftover H is quasirandom is the main
result of <cit.>.
Here, we need to establish additional properties for completing this to a
perfect packing.


  Assume 0≪ c≪ξ≪δ≪γ≪γ'≪ν≪μ,p̂,1/D.
  Let H be a (ξ,2D+3)-quasirandom graph with n vertices and density p̂.
  Let s^*≤7/4n, let (G_s)_s∈[s^*] be a D-degenerate (μ,n)-graph sequence with
  maximum degree cn/log n and ∑_s∈[s^*]e(G_s)=e(H), and let (G'_s)_s∈[s^*] be a
  corresponding subgraph sequence omitting ⌊ν n ⌋ leaves.
  Then  (applied with constants γ and δ to the graphs (G”_s)_s∈[s^*]
  obtained in  from (G'_s)_s∈[s^*] by adding isolated
  vertices)
  a.a.s. provides a packing (ϕ'_s)_s∈[s^*] of
  (G'_s)_s∈[s^*] into H with leftover H such that for
  p=⌊μ n⌋⌊ν n⌋n2^-1 we have
  
  
  *  H is (γ'^3,2D+3)-quasirandom and has density p,
  
  for all v∈ V(H) and s^*-⌊μ n⌋<s,s'≤ s^* we have
  
    
  *  w(v)=(1±γ'^3)pn/2,
    
  *  |N_H(v)∖ϕ'_s|=(1±γ'^3)μ pn,
    
  *  |N_H(v)∖
      (ϕ'_s∪ϕ'_s')|=(1±γ'^3)μ^2pn if s≠ s',
  
  for all u,v∈ V(H) with u≠ v we have,
   
    
  *  ∑_s w_s(v)_u∉ϕ'_s=(1±γ'^3)μpn/2,
  
  and for all u∈ V(H) and s^*-⌊μ n⌋<s≤ s^* we have
  
    
  *  If u∉ϕ'_s then ∑_v vu∈ E(H) w_s(v)<10p^2 n/μ.
  


Our second lemma states that there is an orientation of H suitable for
completing the perfect packing by embedding the leaves with the help of the
algorithm .
A random orientation of a graph H=(V,E) is an orientation of H in which the
orientation of each edge { u,v}∈
E is chosen independently and uniformly at random. We prove this lemma in Section <ref>.


  Let H be a (γ'^3,2)-quasirandom graph of density p with vertex weights w
  V(H)→ℕ_0 such that w(v)=(1±γ'^3)pn/2 for all
  v∈ V(H) and such that ∑_v∈ V w(v)=e(H). If H⃗_0 is a random orientation of H, then a.a.s.    there is an orientation H⃗ of H such that for all v∈ V(H)
  
    
  *  ^+_H⃗(v)=w(v), and
    
  *  |{uv∈ E(H) uv  is oriented differently in H⃗ and H⃗_0}|≤γ'^2 n.
  


Our last lemma states that if in a graph F
satisfying a certain degree-codegree condition, we remove a few edges and
then choose a perfect matching uniformly at random, then each edge is
roughly equally likely to appear in the matching. In the proof of our main
theorem, we shall show that the leaf matching graphs F_v satisfy these
conditions, and hence  can find a perfect matching in F_v,
using edges almost uniformly.



  Assume 0≪1/m≪ p≪μ≪ 1. Let F=F[U,W] be a bipartite
  graph with |U|=|W|=(1± p) m such that
  
    
  *  _F(x)=(1± p)μ m for all x∈ U∪ W, and
    
  *  _F(u,u')=(1± p)μ^2 m for all but at most
      m^2/log m pairs {u,u'}∈U2,
  
  and let F'=F'[U,W] be a spanning subgraph of F[U,W] such that
  
    
  *  _F(x)-_F'(x)<100pm/μ^2 for all x∈ U∪ W.
  
  Then F' has a perfect matching and for a perfect matching σ chosen uniformly at random
  among all perfect matchings in F' and for all uw∈ E(F') we have
  
    [σ(u)=w]≤2/μ m .



This lemma is a straightforward consequence of a lemma (Lemma <ref>) on random matchings
in super-regular pairs by Felix Joos (see <cit.>) and the degree-codegree
characterisation of super-regular pairs (Lemma <ref>) provided by 
Duke, Lefmann, and Rödl in <cit.>. For
completeness, we provide the deduction in Section <ref>.



§ PROOF OF THE MAIN TECHNICAL THEOREM



To prove Theorem <ref> we shall run the algorithm
 (Algorithm <ref>), which uses  to pack the G'_s. 
The resulting graph H of unused edges
is likely to satisfy the conclusions of the
almost perfect packing lemma (Lemma <ref>).
 then chooses a random orientation _0 of H and modifies this orientation slightly to obtain ,
which satisfies the conclusions of the orientation lemma (Lemma <ref>) and also
oriented versions of properties <ref> and <ref> of Lemma <ref>. Finally,  runs
 to complete the packing. To show that  succeeds,
we will verify that with high probability for each r the graphs F_r and
F_r^(r-1) satisfy the conditions of the matching lemma (Lemma <ref>). For this we use
Corollary <ref> and the union bound.


 We use constants with relations as given in Section <ref>, that
 is
 
    0≪ c≪ξ≪δ≪γ≪γ'≪ν≪μ,p̂_0,1/D ,

 
 
 
 
 
 and p̂≥p̂_0.
 Suppose that H is an (ξ,2D+3)-quasirandom graph with n
 vertices and density p̂. Suppose that s^*≤7/4n and that the
 graph sequence (G_s)_s∈[s^*] is a D-degenerate (μ,n)-graph
 sequence, with maximum degree Δ≤cnlog n, such that the
 last ⌈(D+1)^-3n⌉ vertices in the degeneracy order form an independent
 set in G_s, and all have the same degree d_s in G_s. Suppose
 further that ∑_s∈[s^*]e(G_s)=e(H). We use 
 (Algorithm <ref>) for packing (G_s)_s∈[s^*]
 into H and argue in the following that it succeeds a.a.s.
 
 As ⌊ν n⌋<μ n,  can choose a corresponding subgraph
 sequence (G'_s)_s∈[s^*] omitting ⌊ν n⌋ leaves. Next it
 creates for each s∈ [s^*] a graph G”_s. For the non-special graphs
 (s≤ s^*-⌊μ n⌋) it sets G”_s:=G'_s. For the special graphs
 (s>s^*-⌊μ n⌋) it obtain G”_s
 by adding the set I'_s of
 n-v(G'_s) isolated vertices, which we place at the end of the
 D-degeneracy order. Note that for each G”_s the last δ n vertices of G”_s in the degeneracy order
 are an independent set all of whose vertices have degree d_s. Indeed,
 if s≤ s^*-⌊μ n⌋ then this holds by
 assumption on G_s and because δ<(D+1)^-3, and if s>s^*-⌊μ
 n⌋ then this holds because n-v(G'_s)=n-⌊μ n ⌋ and
 δ<μ (and in this case d_s=0).

  next runs  with input (G”_s)_s∈[s^*] and H.
 By the almost perfect packing lemma (Lemma <ref>),  a.a.s. returns a packing
 (ϕ^*_s)_s∈[s^*] of (G”_s)_s∈[s^*] into H, and a
 graph H consisting of all the edges not used in the packing, which satisfies
 the conclusions <ref>–<ref> of Lemma <ref>.
 As described in , we let for each s∈[s^*] the map
 ϕ'_s be the embedding of G'_s into H induced by ϕ^*_s.
 By construction of the (G”_s)_s∈[s^*], the (ϕ'_s)_s∈[s^*] form
 a packing of the (G'_s)_s∈[s^*] into H, with H being the
 graph formed by the unused edges. The total number of unused edges is by
 construction ⌊μ n⌋⌊ν n⌋=pn2, so H has
 density p.
 
  next chooses a random-like orientation of H. More precisely,
 we want to use an orientation  of H such that
 w(v)=^+_(v) for each v∈ V(H), which in addition inherits
 oriented versions of <ref> and <ref>. The next claim states that
 such an orientation exists.

  For all sufficiently large n there exists an orientation 
   of H such that w(v)=^+_(v) for each v∈ V(H), and in addition
   for each s^*-⌊μ n⌋<s,s'≤ s^* we have
  
   
  *  |N^+_(v)∖ϕ'_s|=(1±γ')μ pn2, and
   
  *  |N^+_(v)∖
      (ϕ'_s∪ϕ'_s')|=(1±γ')μ^2pn2 if s≠ s'.
  
 
 
  By <ref>, in particular H is (γ'^3,2)-quasirandom and of
  density p, and by <ref> we have
  w(v)=(1±γ'^3)pn2 for all v∈ V(H). This verifies that
  H satisfies the conditions of the orientation lemma (Lemma <ref>).
  
  Let _0 be a random orientation of H. Given v∈ V(H) and s^*-⌊μ n⌋<s≤ s^*, by <ref> and Theorem <ref>, with probability at least 1-exp(-γ'^6μ pn12) we have
  
    |N^+__0(v)∖ϕ'_s|=(1±3γ'^3)μ pn2 .

  Similarly, given v∈ V(H) and s^*-⌊μ n⌋<s<s'≤ s^*, by <ref> and Theorem <ref>, with probability at least 1-exp(-γ'^6μ^2 pn12) we have
  
    |N^+__0(v)∖ (ϕ'_s∪ϕ'_s')|=(1±3γ'^3)μ^2pn2 .

  Taking the union bound, and by Lemma <ref>, with probability at least 1-2n^3exp(-γ'^6μ^2 pn12)-o(1) each of the above good events holds for each v∈ V(H) and each s^*-⌊μ n⌋<s,s'≤ s^*, and in addition there is an orientation  of H satisfying conclusions <ref> and <ref> of Lemma <ref>.
  
  For sufficiently large n we have 1-2n^3exp(-γ'^6μ^2 pn12)-o(1)>0, so we fix _0 and  satisfying all these properties. By <ref> the orientation  satisfies _^+(v)=w(v) for each v∈ V(H), as desired. Given v∈ V(H) and s^*-⌊μ n⌋<s≤ s^*, by <ref> we have
  
    |N^+_(v)∖ϕ'_s|=|N^+__0(v)∖ϕ'_s|±γ'^2 n=(1±3γ'^3)μ pn2±γ'^2 n=(1±γ')μ pn2 ,

  where the final inequality is by choice of γ'. This verifies <ref>. Similarly, given v∈ V(H) and s^*-⌊μ n⌋<s<s'≤ s^*, we have
  
    |N^+_(v)∖
          (ϕ'_s∪ϕ'_s')|    =|N^+__0(v)∖
          (ϕ'_s∪ϕ'_s')|±γ'^2
          n=(1±3γ'^3)μ^2pn2±γ'^2
          n 
        =(1±γ')μ^2pn2 ,

  giving <ref>.
 

 This orientation is now used to embed the remaining dangling leaves.  runs
  (Algorithm <ref>) for this purpose. Recall that,
 for a vertex v∈ V(), the leaf matching graph F_v (see
 Definition <ref>) is a bipartite graph with parts consisting of
 the leaves L_v which we need to embed at v (which will be in many different
 G_s) and the out-neighbours N_^+(v) of v in  to which we will
 embed these leaves, with an edge from a leaf in some G_s to an out-neighbour
 u of v if u∉ϕ'_s. Recall that for convenience we assume
 V()=[n].  starts with F_v^(0):=F_v for each v∈[n],
 and then for each r∈[n] in succession takes a random perfect matching
 σ_r in F_r^(r-1) and for each k>r removes some edges from
 F_k^(r-1) to form F_k^(r). As explained in Section <ref>, it is
 enough to show that with positive probability 
 does not halt with failure. To analyse the running of
 , we aim to show that for each r the graphs
 F_r^(0) and F_r^(r-1) satisfy the conditions of Lemma <ref>
 with m:=pn2, with F=F_r^(0) and F'=F_r^(r-1), and with U=L_r and W=N^+_(r). We shall then
 use Lemma <ref> to conclude that the
 matching σ_r we choose in F_r^(r-1) does not use any given edge with
 exceptionally high probability, which in turn will allow us to show that
  is successful.
 
 Property <ref>: Given x∈ V(F_r^(0)), we separate
 two cases. If x∈ L_r is in the graph G_s, then by <ref> we have
 _F_r^(0)(x)=|N_^+(r)∖ϕ'_s|=(1±γ')μ
   p n2. If x∈ N^+_(r), then by <ref> we have
 _F_r^(0)(x)=∑_s
 w_s(r)_x∉ϕ'_s=(1±γ'^3)μ p n2. In either
 case, since p>γ' this verifies <ref> for F=F_r^(0),
 F'=F_r^(r-1) and every r∈ [n].
 
 Property <ref>: Given u,u'∈ L_r, if u∈ V(G_s)
 and u'∈ V(G_s'), where s≠ s', then by <ref> we have
 _F_r^(0)(u,u')=|N_^+(r)∖(ϕ'_s∪ϕ'_s')|=(1±γ')μ^2
   p n2. Again since γ'<p this is as required by <ref>,
 and we only need to show that the number of u,u'∈ L_r which are both in
 G_s for some s∈[s^*] is at most p^2n^24log(pn/2). But any
 given G_s has at most w_s(r)≤Δ=cnlog n vertices in L_r,
 so that for a given u there are at most cnlog n choices of u'
 with u,u'∈ V(G_s) for some s∈[s^*]. Since |L_r|≤ n we conclude that
 there are at most cn^2log n<p^2n^24log(pn/2) pairs
 u,u'∈ L_r such that u,u'∈ V(G_s) for some s∈[s^*]. This completes
 the verification of <ref> for F=F_r^(0), F'=F_r^(r-1) and
 every r∈ [n].
 
Property <ref>: 
This property does not hold deterministically, but we shall show that it
holds for all r with high probability. For this purpose we define the
following events.
For each r∈[n] let ℰ_r be the event that for each y∈ V(F_r^(0)) we have

    _F_r^(0)(y)-_F_r^(r-1)(y)≤
      50 p^2nμ^-2 ,

 that is, ℰ_r is the event that <ref> holds for
 F=F_r^(0) and F'=F_r^(r-1). We shall prove the following claim below,
 but first show how it implies the theorem.

 
   With probability at least 1-n^-1 for every r∈ [n] the event
   ℰ_r holds.
 

 If ℰ_r holds
 then all conditions of Lemma <ref> are satisfied 
 for F=F_r^(0), F'=F_r^(r-1). In this case, we can apply the lemma, and
 obtain a perfect matching σ_r in F_r^(r-1) with the following property.
 Let _r-1 consist of the collection of matchings
 σ_1,…,σ_r-1 obtained in earlier rounds.

 
  For r∈[n], for u∈ N^+_(r) and for s^*-⌊μ n⌋<s≤ s^* the following holds.
  Either _r does not occur or a random perfect matching σ_r in
  F_r^(r-1) satisfies
  
    [σ_r^-1(u)∈ V(G_s)|_r-1]≤4w_s(r)μ pn .

 
 
   If _r occurs, then all properties <ref>–<ref> from Lemma <ref> are
   satisfied with F=F_r^(0) and F'=F_r^(r-1), 
   and thus, a random matching σ_r in F' satisfies
   for any given edge xu∈ E(F_r^(r-1)) 
   
    [xu∈σ_r|_r-1]≤4μ p n.
 
   Taking the union bound over the w_s(r) choices of x∈ L_r which are in G_s, the claim follows.
 

 Hence, assuming Claim <ref>, we get that
 Algorithm <ref> does not halt with failure in any round with probability at
 least 1-n^-1 and provides matchings
 σ_1,…,σ_r.  uses these matchings to define
 for each s∈[s^*] the map ϕ_s:V(G_s)→
 V(H) by setting
 
    ϕ_s(x)=ϕ'_s(x)     if x∈ V(G_s)∩(ϕ_s)
    σ_r(x)     if x∈ L_r .

 Recall that for each s, the map ϕ'_s is an embedding
 of G'_s into H. All the edges of G_s which are not in G'_s
 have one end in the removed leaves V_s and the other end in V(G'_s).
 Consider those leaves of G_s which are adjacent to x∈ V(G'_s). By
 definition, these are in L_ϕ_s(x) and by construction of
 F_ϕ_s(x)^(ϕ_s(x)-1), they are embedded to distinct vertices of
 H which are adjacent in H to ϕ_s(x) and which are neither in
 ϕ_s, nor are of the form σ_i(y) for some i<ϕ_s(x) and y∈
 V_s. It follows that ϕ_s is indeed an embedding of G_s into H for
 each s∈[s^*]. 
   
 We now check that these embeddings together form a packing. The maps
 (ϕ'_s)_s∈[s^*] pack the graphs (G'_s)_s∈[s^*] into
 H, leaving exactly the edges of H unused. By construction 
 is an orientation of H, so for v⃗u⃗∈ E(), the edge uv∈ E(H) is
 used in the embedding of G_s, where σ_v^-1(u)∈ V(G_s). It follows
 that each edge of H is used in the maps (ϕ_s)_s∈[s^*] at
 least once, and since ∑_s∈[s^*]e(G_s)=e(H) each edge must be
 used exactly once. This justifies that the maps (ϕ_s)_s∈[s^*]
 perfectly pack the graphs (G_s)_s∈[s^*] into H, as desired.
 
 

 So it remains to verify Claim <ref>. We shall first argue that the claimed
 probability bound follows from a probability bound, given in (<ref>),
 which is of the right form to use Corrollary <ref>.
 Indeed,
 let 𝒜_r be the event that
 ℰ_i holds for each 1≤ i<r but ℰ_r does not hold.
 Observe that if for each r the event 𝒜_r does not hold, then
 ℰ_r holds for each r∈[n]. In particular, by the union bound
 over r∈[n] it
 suffices to show that for each fixed r∈[n] we have [𝒜_r]≤
 n^-2. Further, by another union bound over the at most
 v(F_r^(0))=2w(r)≤ 2n different y∈ V(F_r^(0)) and since 𝒜_r⊂⋂_1≤ i≤
   r-1ℰ_i it is enough to show that for a fixed y∈ V(F_r^(0))
 
    [⋂_1≤ i≤ r-1ℰ_i  and  _F_r^(0)(y)-_F_r^(r-1)(y)>50 p^2nμ^-2]≤12n^-3 ,

 where we used the definition of ℰ_i (see (<ref>)). The
 remainder of this proof is devoted to establishing this bound. We will use
 Corollary <ref> for this purpose, with the good event ⋂_1≤
   i≤ r-1ℰ_i. To that end, define for each 1≤ i≤ r-1 the
 random variable
 
    Y_i:=_F_r^(i-1)(y)-_F_r^(i)(y)

 and observe that
 
    _F_r^(0)(y)-_F_r^(r-1)(y)
     = ∑_i=1^r-1 Y_i .

 
To apply Corollary <ref> we need to find the range of each Y_i and the expectation of each Y_i, conditioned on the history _i-1 which consists of the collection of matchings σ_1,…,σ_i-1. This is encapsulated in Claim <ref>. 
 
   For each 1≤ i≤ r-1, we have 0≤ Y_i≤Δ. Furthermore, either some ℰ_i with 1≤ i≤ r-1 does not occur, or we have ∑_i=1^r-1[Y_i|_i-1]≤ 25p^2nμ^-2.
 
 
  We first show 0≤ Y_i≤Δ. There are two cases to consider. First, if y∈ L_r, then y is in G_s for some s∈[s^*]. An edge yu of F_r^(i-1) is removed to form F_r^(i) only if u is assigned a leaf of G_s in σ_i. Since there are at most w_s(i)≤Δ such leaves, we have Y_i≤Δ in this case. Second, if y∈ N^+_(r), and y is assigned a leaf of G_s in σ_i, then we remove all edges of F_r^(i-1) from y to leaves of G_s to form F_r^(i).  Since σ_i is a matching, this happens for at most one s∈[s^*]. There are at most w_s(r)≤Δ such leaves of G_s, so also in this case we have Y_i≤Δ.
  
  We now bound above the sum of conditional expectations. Again, there are two cases to consider. First, if y∈ L_r, then let s be such that y∈ V(G_s). Suppose that _i-1 is a history up to and including σ_i-1 such that _i holds. By linearity of expectation, and because σ_i^-1(u)∈ V(G_s) means that some leaf of G_s is matched to u in σ_i, we have
  
    [Y_i|_i-1]   =∑_u∈ N_F_r^(i-1)(y)
    i⃗u⃗∈ E()[σ_i^-1(u)∈ V(G_s)|_i-1]
       ≤∑_u∈ N_F_r^(i-1)(y)
    i⃗u⃗∈ E()w_s(i)4μ p n≤∑_u∈ N_H(r,i)w_s(i)4μ p n ,

  where the first inequality is by Claim <ref> and the second holds since i⃗u⃗∈ E() implies iu∈ E(H) and since u∈ N_F_r^(i-1)(y) implies ru∈ E(H). Summing over i, either some _i with i∈[r-1] does not hold, or we have
  
    ∑_i=1^r-1[Y_i|_i-1]≤∑_i=1^r-1∑_u∈ N_H(r,i)w_s(i)4μ p n≤∑_i=1^n|N_H(r,i)|· w_s(i)4μ p n≤ 2p^2n·4μ p n∑_i=1^nw_s(i) ,

  where the final inequality is by <ref>. Recall that we defined p=⌊μ n⌋⌊ν n⌋n2^-1, so in particular ν n≤pnμ. Since ∑_i=1^nw_s(i)=⌊ν n⌋≤pnμ counts the number of leaves removed from G_s to form G'_s, we obtain that either some _i with i∈[r-1] does not hold, or
  
    ∑_i=1^r-1[Y_i|_i-1]≤8p^2nμ^2 ,

  as desired.
  
  Finally, we consider the case y∈ N^+_(r). If a leaf of G_s is assigned to y by σ_i, it follows that y is adjacent to w_s(r) leaves of G_s in F_r^(i-1) and the edges to these leaves are exactly the edges at y removed from F_r^(i-1) to form F_r^(i). Suppose that _i-1 is a history up to and including σ_i-1 such that _i holds. Since a leaf of G_s can only be assigned to y by σ_i if i⃗y⃗∈ E(), and by linearity of expectation, we have
  
    [Y_i|_i-1]   =∑_s^*-⌊μ n⌋<s≤ s^*_y∈ N^+_(i)[σ_i^-1(y)∈ V(G_s)|_i-1]· w_s(r)
       ≤∑_s^*-⌊μ n⌋<s≤ s^*_y∈ N^+_(i)w_s(r)w_s(i)4μ p n ,

  where the second line follows by Claim <ref>. Summing over i, either some _i with i∈[r-1] does not hold, or we have
  
    ∑_i=1^r-1[Y_i|_i-1]   ≤∑_i=1^r-1∑_s^*-⌊μ n⌋<s≤ s^*_y∈ N^+_(i)w_s(r)w_s(i)4μ p n
       ≤∑_s^*-⌊μ n⌋<s≤ s^*∑_i=1^n_y∈ N^+_(i)w_s(r)w_s(i)4μ p n
       =∑_s^*-⌊μ n⌋<s≤ s^*∑_v:v⃗y⃗∈ E()^nw_s(r)w_s(v)4μ p n
       ≤∑_s^*-⌊μ n⌋<s≤ s^*4w_s(r)μ p n∑_v:vy∈ E(H)w_s(v)
       ≤∑_s^*-⌊μ n⌋<s≤ s^*4w_s(r)μ p n·10p^2nμ=40pμ^2∑_s^*-⌊μ n⌋<s≤ s^*w_s(r) ,

  where the last inequality is by <ref>. By definition of w(r), by <ref> and by choice of γ' we have ∑_s^*-⌊μ n⌋<s≤ s^*w_s(r)=w(r)≤5/8pn, so we conclude that either some _i with i∈[r-1] does not hold, or we have
  
    ∑_i=1^r-1[Y_i|_i-1]≤40pμ^2·5/8pn=25p^2nμ^2 ,

  as desired.


  Using Claim <ref>, We are now in a position to apply 
 Corollary <ref>, with R=Δ=cnlog n, with
 =25p^2nμ^-2, and with the event
 =⋂_i=1^r-1ℰ_i, which gives
 
    [⋂_1≤ i≤ r-1ℰ_i  and  ∑_i=1^r-1Y_i>50p^2nμ^-2]≤exp(-4R)=exp(-6.25c^-1p^2μ^-2log n)<12n^-3 ,

 where the final inequality is by choice of c. This
 establishes (<ref>).




§ PROOF OF THE ORIENTATION LEMMA



In this section we prove Lemma <ref>.


By the given quasirandomness of H we know that
_H(v)=(1±γ'^3)pn and
|N_H(v)∩ N_H(w)|=(1±γ'^3)p^2n 
for every v≠ w∈ V(H).
Applying a standard Chernoff argument, i.e. using Theorem <ref>, we
obtain that a.a.s. 
for every v≠ w∈ V(H) we have

    _H⃗_0^+(v)=(1± 2γ'^3)pn/2 and 
    |N_H⃗_0^+(v)∩ N_H⃗_0^-(w)|=(1± 2γ'^3)p^2n/4  .
 
From now on fix an arbitrary orientation H⃗_0
satisfying these two properties.
Starting with H⃗_0 we aim to switch the orientations
of some edges until we find an oriented graph H⃗
as desired. In order to do so, we will successively
switch the orientations of pairs of edges, 
thus producing a sequence
of oriented graphs (H⃗_i)_0≤ i≤ t 
that eventually end up with H⃗_t=H⃗.
For any such oriented graph H⃗_i
and every vertex v∈ V(H) we
define the potential ϕ_i(v):=_H⃗_i^+(v)-w(v) and

    ϕ(H⃗_i) := ∑_v∈ V(H) |ϕ_i(v)|  .

Initially we have |ϕ_0(v)|≤ 3γ'^3 pn for every v∈ V(H). 

The algorithm  describes how orientations are switched. In
every iteration of this algorithm, the central idea is to change the potential
of two vertices x,y∈ V(H) with ϕ_i(x)>0 and ϕ_i(y)<0 in the
following way: We choose a vertex m∈ N_H⃗_i^+(x)∩
N_H⃗_i^-(y) uniformly at random. We then switch (the orientation
of) the directed edge xm, that is we replace xm with mx, and we also
switch the edge my. Switching these two edges creates a new orientation
H⃗_i+1 of H. The vertex m will be called the middle vertex
of the switching, while x and y are called the end vertices. In case
that

    |{uv∈ E(H) uv  is oriented differently in H⃗_i
       and H⃗_0}|

gets too large in some round i and for some
vertex v, we let the algorithm halt with failure. However, we will see in the
following that this happens with probability tending to 0.

 
 
We start with some easy observations.
 

As long as the algorithm does not halt with failure
we have 

    ϕ(H⃗_i+1)=ϕ(H⃗_i)-2  .




For every vertex v∈ V(H) with ϕ_0(v)>0 
(or ϕ_0(v)<0) 
it holds that ϕ_i-1(v)≥ϕ_i(v)≥ 0 (or ϕ_i-1(v)≤ϕ_i(v)≤ 0) for all i∈ [t].
 
 
Indeed, both observations
hold since the switching of the orientations of xm
and my ensures that ϕ_i+1(x)=ϕ_i(x)-1
and ϕ_i+1(y)=ϕ_i(y)+1, while
the potentials of all the other vertices do not change.


 

A.a.s. throughout the algorithm every vertex v∈ V(H) is chosen at most 40γ'^3 n times as the middle vertex of a switching.
 


Every vertex v∈ V(H) can become a middle vertex only
if v∈ N_H⃗_i^+(x)∩ N_H⃗_i^-(y)
for some 0≤ i≤ t-1 and x,y∈ V(H)
with ϕ_i(x)>0 and ϕ_i(y)<0. Now, v
has at most (1+γ'^3)pn<2pn neighbours x∈ V(H) and every such vertex with positive potential 
participates in a switching as an end vertex 
in at most |ϕ_0(x)|≤ 3γ'^3 pn
rounds. Thus, there are at most 6γ'^3 p^2n^2
rounds which may consider v as a suitable middle vertex.
In each such round, the middle vertex is chosen
uniformly at random from a set N_H⃗_i^+(x)∩ N_H⃗_i^-(y).
As long as the algorithm does not halt with failure
we have 

    |N_H⃗_i^+(v)∩ N_H⃗_i^-(w)| = 
    |N_H⃗_0^+(v)∩ N_H⃗_0^-(w)| ± 2· 100γ'^3 n
    =(1±γ'^2)p^2n/4  .

Thus, when v is suitable for being a middle vertex, the probability that v is chosen is bounded from above by
5/p^2n. Now, applying a Chernoff-type argument
the claim follows.

 
With the above statements in hand, we can show that 
a.a.s.  does not halt with failure 
and that the resulting oriented graph
H⃗=H⃗_t satisfies the properties <ref> and <ref>. 
Indeed, let v∈ V(H) be any vertex.
In some round, we change the orientation of exactly one edge incident
with v 
if and only if v is an end vertex of the switching in this round.
As such a switching decreases |ϕ_i(v)| by 1
and since |ϕ_i(v)| never increases
according to Observation <ref>, this happens
at most |ϕ_0(v)|≤ 3γ' pn times.
Moreover, we change the orientation of exactly two 
edges incident with v if and only if v is a middle vertex
of a switching. By the above claim a.a.s. this happens
at most 40γ'^3 n times. 
Thus, as long as the algorithm runs, we a.a.s. switch the orientations of at most

    3γ' pn + 2· 40γ'^3 n < 100γ'^3 n < γ'^2 n

edges incident with v.
It follows that the algorithm runs without failures, and also that
property <ref> holds. 
By Observation <ref> and since t=ϕ(H⃗_0)/2 we obtain that
ϕ(H⃗_t)=0, meaning that <ref> holds for H⃗=H⃗_t.




§ PROOF OF THE MATCHING LEMMA



In this section we provide the proof of Lemma <ref>. The proof of
this lemma is the only place in this paper where we use the concept of a
regular pair.


  Let G be a graph and U,W⊂ V(G) be disjoint vertex sets. The
  density of the bipartite graph G[U,W] is 
  
    d_G(U,W)=e(G[U,W])/|U||W| .

  We say that G[U,W] is (,d)-regular if for all U'⊂ U and
  W'⊂ W with |U'|≥|U| and |W'|≥|W| we have
  
    d_G(U',W')=d± .

  The graph G[U,W] is (,d)-super-regular if it is
  (,d)-regular and for all u∈ U and for all w∈ W we have
  
    _G[U,W](u)=(d±)|W|,     and    _G[U,W](w)=(d±)|U| .



It is well-known that regular pairs are forced by a degree-codegree condition;
we use the following formulation due to
Duke, Lefmann, and Rödl in <cit.>.


  
  Assume 0<<2^-200 and let G[U,W] be a bipartite graph with
  parts U and W of size |U|=|W|=n and density d=d_G[U,W](U,W).
  If
  
    
  * _G[U,W](u)>(d-)|W| for all u∈ U, and
    
  * _G[U,W](u,u')<(d+)^2|W| for all but at most
      2|U|^2 pairs {u,u'}∈U2,
  
  then G[U,W] is (^1/6,d)-regular.
  

If we choose a perfect matching uniformly at random in a super-regular pair
then each edge is roughly equally likely to appear in the matching, as was shown
by Joos (see <cit.>).


  
  Assume 0≪1/m'≪'≪ d≪ 1. Let G[U,W] be an
  (',d)-super-regular graph with |U|=|W|=m'.
  Then G[U,W] contains a perfect matching.
  Moreover, for a perfect matching σ chosen uniformly at random
  among all perfect matchings in G[U,W] and for all uw∈ E(G) we have
  
         [σ(u)=w]=(1±(')^1/20)1/dm'  .      


The proof of the matching lemma simply combines these two lemmas.


  By <ref> and <ref>, for all x∈ U∪ W we
  have
  
    _F'(x)=(μ±200pμ^2)m

  By <ref> and <ref>, for all but at most
  m^2/log m pairs {u,u'}∈U2 we have
  
    _F'(u,u')=(μ^2±300pμ^2)m .

  We want to apply Lemma <ref> with d=μ and =400p/μ^3 to
  conclude that F'[U,W] is super-regular, and now check the
  conditions of this lemma.
  By (<ref>), for u∈ U we have
  
    _F'(u)=(d±200pμ^2)m 
          = (d±200pμ^2)|W|/1± p
          = (d±400 pμ^2)|W|
          >(d-)|W| ,

  and similarly for w∈ W we have _F'(w)=(d±400pμ^2)|U|>(d-)|U|.
  By (<ref>), for all but at most m^2/log m pairs
  {u,u'}∈U2 we have
  
    _F'(u,u')   ≤(d^2+300pμ^2)m≤(d^2+300pμ^2)|W|/1-p≤(d^2+400pμ^2)|W|<(d^2+2 d+^2)|W| 
       =(d+)^2|W| ,

  where the last inequality uses d=μ and =400p/μ^3.
  We conclude that, if 
  m^2/log m≤ 2 |U|^2 which holds for  
  log m>1/, then F' is
  ((400p/μ^3)^1/6, μ)-regular by
  Lemma <ref>.
  Since _F'(x)=(d±400pμ^2)|U| for all x∈ U∪ W, it follows
  that F' is  ((400p/μ^3)^1/6,μ)-super-regular.
  
  Hence we can apply Lemma <ref> to F' with 
  
    m'=|U|=(1± p)m ,   '=(400p/μ^3)^1/6 ,   and  
        d=μ ,

  and conclude that F' has a perfect matching and that for a perfect
  matching σ chosen uniformly at random among all perfect matchings
  of F' and for all uw∈ E(F') we have
  
    [σ(u)=w]=(1±(400p/μ^3)^1/120)1/μ(1±
          p)m≤2/μ m ,

  where the inequality holds if p is small and (400p/μ^3)^1/120≤1/100.




§ PROOF OF THE ALMOST PERFECT PACKING LEMMA



In this section we prove Lemma <ref>. This is the technical part
of this paper, which requires some stamina. 

We start this section by explaining the setup which we use throughout. Then, in
Section <ref> we define some auxiliary properties that our random
packing process preserves.
In Section <ref> we analyse the behaviour of the algorithm
,
and in Section <ref> the behaviour of .
In Section <ref>, finally, we use the obtained results to show
Lemma <ref>. 

In the results in this section we shall use the following setup.


  We use the constants defined in Setting <ref>.

  Let (G”_s)_s∈[s^*] (for some s^*≤7/4n) be graphs on [n], such
  that for each s and x∈ V(G”_s) we have _G”_s(x)≤ D, such
  that Δ(G”_s)≤ cn/log n, and such that the final δ n
  vertices of G”_s all have degree d_s and form an independent set.

  Let H be a (ξ,2D+3)-quasirandom graph with n vertices and density p̂.
  Recall that  chooses H_0^* as a subgraph of H by picking edges
  of H independently with probability γn2/e(H). We will assume that e(H_0^*)≤ 1.1γn2.


We note at this point that we assume e(H_0^*)≤ 1.1γn2 in
order to make use of (<ref>). This inequality holds with probability at
least 1-e^-n and hence this assumption does not affect the proof of
Lemma <ref>, since we will see that, if this inequality holds, each of
the properties <ref> – <ref> occurs with probability
at least 1-n^-4.



 §.§ Coquasirandomness, diet, codiet, and cover



The following properties coined in <cit.> are preserved throughout the run of our
random packing process. Firstly, for our analysis of , we need
the concept of coquasirandomness. This controls the intersections of vertex
neighbourhoods in two edge-disjoint graphs on the same vertex set.


    For α>0 and L∈ℕ, we say that a pair of graphs (F, F^*), both on the same vertex set V of order n
    and with densities p and p^*, respectively, is (α,L)-coquasirandom if for
    every set S⊂ V of at most L vertices and every subset R⊆ S we have
    
    |N_F(R)∩ N_F^*(S∖ R)|
        =(1±α)p^|R|(p^*)^|S∖ R|n .



For the analysis of one run of  we further need the following concepts.


   
  Let H be a graph with n vertices and pn2 edges, and let
  X⊆ V(H) be any vertex set. We say that the pair (H,X)
  satisfies the (β,L)-diet condition if for every set
  S⊂ V(H) of at most L vertices we have 
  
    |N_H(S)∖
      X|=(1±β)p^|S|(n-|X|) .

  Given further H^* on the same vertex set as H, which has no edges in common with H and which has p^*n2 edges, we say that the triple (H,H^*,X) satisfies the (β,L)-codiet condition if for every set S⊂ V(H) of at most L vertices, and for every R⊂ S, we have
  
    |(N_H(R)∩ N_H^*(S∖ R))∖
      X|=(1±β)p^|R|(p^*)^|S∖ R|(n-|X|) .

  Further, let G be a graph with vertex set [n].
  Given >0,  i∈ [n-ϵ n], and d∈ℕ, we define
  
    X_i,d:={x∈ V(G) i≤ x<i+ε n,|_G(x)|=d} .
 
  We say that a partial embedding ψ of G into H, which embeds
  _G(x) for each i≤ x<i+ε n, satisfies the
  (,β,i)-cover condition if for each v∈ V(H), and for each d∈ℕ,
  we have
  
    |{ x∈ X_i,d:v∈ N_H(ψ(_G(x)))}|=(1±β)p^d|X_i,d|±ε^2n .



Following <cit.>, we use Definition <ref> to define key events (·;·), (·;·), (·) on the probability space Ω^G H underlying the run of  which attempts to embed G into H. (For a formal definition of this probability space, see <cit.>.)


 Suppose that D, δ and  are as in Setting <ref>.
 Suppose that λ>0. Suppose that we have graphs G and H as in
 Algorithm <ref>. Suppose that we run  to partially
 embed G into H. Let (ψ_i)_i∈[t_*] be the partial embeddings of
 G[[i]] into H, where t_*=n-δ n if  succeeded, and otherwise
 t_*+1 is the step in which  halted with failure.

	
  * For each t∈[n-δ n], let (λ;t)⊂Ω^G H correspond to executions of  for which t_*≥ t and the pair (H,ψ_t)
	satisfies the (λ,2D+3)-diet condition.
	
  * For each t∈[n-δ n], let (λ;t)⊂Ω^G H correspond to executions of  for which t_*≥ t+ n and the embedding ψ_t^* of G into H
	satisfies the (ε,λ,t)-cover condition.
	
  * Suppose further that we have a graph H^*_0 with V(H)=V(H^*_0). For each t∈[n-δ n], let (t)⊂Ω^G H correspond to executions of  for which t_*≥ t and the triple (H,H^*_0,ψ_t) satisfies the (2η,2D+3)-codiet condition.






 §.§ Properties of 



In this section we collect properties that are preserved during a run of
. The constants we use are as in
Setting <ref>. However, since we are only concerned with a
single run of  here, we only consider a single guest
graph G, and a single host graph H with the following properties.


  Let G be a graph on vertex set [n] such that _G(x)≤ D for each
  x∈ V(G) and Δ(G)≤ cn/log n.
  Let H be an (α,2D+3)-quasirandom graph with n vertices and pn2 edges, with p≥γ, and suppose that H^*_0 is a graph on V(H) such that (H,H^*_0) is (η,2D+3)-coquasirandom.


The following lemma comes from <cit.> and the deduction of <cit.> which comes immediately after.
Specifically, <ref> is the deduction of <cit.> and <ref> is explicitly in
<cit.>, while <ref> and <ref> differ only from
the statements of <cit.> in that the error bound we
give here is in terms of β_t whereas in <cit.> a
(larger) error bound Cα is given. In the proof
of <cit.>, the stronger error bounds we claim here are
explicitly obtained. The cover conditions asserted are otherwise identical,
despite being written slightly differently.


  Given D∈ℕ and γ>0, let
  δ,α_0,α_2n,C, be as in
  Setting <ref>. Then the following holds for any
  α_0≤α≤α_2n and all sufficiently large n.
  Let G, H and H^*_0 be as in Setting <ref>.
  Let β_t=β_t(α) be as in Setting <ref>.
  If we run  to embed G[ [n-δ n]] into H,
  then with probability at least 1-2n^-9 
  
    
  *   succeeds in constructing
      partial embeddings (ψ_i)_i∈[n-δ n],
    
  *  (H,ψ_t) satisfies the (β_t,2D+3)-diet condition (i.e. (β_t;t) occurs) for
      each t∈[n-δ n],
    
  *  ψ_t has the (,20Dβ_t- n+2,t- n+2)-cover
      condition (i.e. (20Dβ_t- n+2,t- n+2) occurs) for each t∈[ n-1,n-δ n].
    
  *  (H,H^*_0,ψ_t) satisfies the (2η,2D+3)-codiet condition (i.e. (t) occurs) for
      each t∈[n-δ n]. 


The next lemma is proven as part of <cit.> (it can
be found in <cit.>).


  Given D∈ℕ and γ>0, let
  δ,α_0,α_2n,C, be as in
  Setting <ref>. Then the following holds for any
  α_0≤α≤α_2n and all sufficiently large n.
  Let G and H be as in Setting <ref> and let 1≤ j≤ t+1- n for t≤ (1-δ)n.
  Let β_j=β_j(α) be as in Setting <ref>.
  Assume we run  to embed G[ [n-δ n]] into H, that it
  produces a partial embedding ψ_j such that (H,ψ_j) has the
  (β_j,2D+3)-diet condition, and let T⊂ V(H)∖ψ_j
  with |T|≥1/2γ^2D+3δ n.
  Then with probability at least 1-2n^-2D-19, one of the following
  occurs.
  
  
  *  ψ_t does not have the (,20Dβ_j,j)-cover condition (i.e. (20Dβ_j,j) does not occur) , or
  
  *  |{x j≤ x<j+ n, ψ_t-1(x)∈ T}|=(1±40Dβ_j)|T| n/n-j.
  


In <cit.> we estimated the probability that, when running
, a given vertex x∈ V(H) is not used in the embedding
of the first t_1 vertices of G.

 
  Given D∈ℕ and γ>0, let
  δ,α_0,α_2n,C, be as in
  Setting <ref>. Then the following holds for any
  α_0≤α≤α_2n and all sufficiently large n.
  Let G and H be as in Setting <ref>.  Let
  0≤ t_0<t_1≤ n-δ n. Let  be a history ensemble of
   up to time t_0, and suppose that
  []≥ n^-4. Then the following hold for any distinct
  vertices u,v∈ V(H).
  
   
  *  If v∉ψ_t_0 then we have
     
             [v∉ψ_t_1|]=(1±100Cαδ^-1)n-1-t_1n-t_0 .
             
     
   
  *  If u,v∉ψ_t_0 then we have
     
             [u,v∉ψ_t_1|]=(1±100Cαδ^-1)(n-1-t_1n-t_0)^2 .
             
  


In addition we estimated the probability that a given edge of G is
embedded to a given edge of H. The following lemma is <cit.>, together with equation (6.10) of that paper which is established in the proof.


 Given D∈ℕ, and γ>0, let constants
 δ,,C,α_0,α_2n be as in
 Setting <ref>. Then the following holds for any
 α_0≤α≤α_2n and all sufficiently large n. 
 Let G and H be as in Setting <ref>. 
 Let uv be an edge of H, and let xy be an edge of G. When  is run to embed G[ [n-δ n]] into H, we have
 
    [x u,y v]=(1±500Cαδ^-1)^4D+2· p^-1n^-2 ,

 and furthermore the probability that some edge of G is embedded to uv is

         (1±500Cαδ^-1)^4D+2p^-1n^-2·2e(G) .
            


We can use these two lemmas for estimating the probability that a given vertex of G
is embedded on a given vertex of H.


  Given D∈ℕ, γ>0, let δ, , C, α_0, α_2n
  be as in Setting <ref> and let p≥γ. Let α_0<α≤α_2n
  and let n be sufficiently large. 
  Let G and H be as in Setting <ref>. 
  Let x∈ V(G) with x≤ (1-δ)n and 
  u∈ V(H). When we run
   to embed G[ [n-δ n]] into H, then
  
    [x u]=(1±10^4Cα Dδ^-1)1/n .



  While we could prove this lemma directly following the methods of <cit.>, it is convenient to deduce it from the results of <cit.>. We separate two cases.
  
  If x is an isolated vertex in G, then we embed x to u if and only if the first x-1 vertices of G are not embedded to u, and then among the n-x+1 vertices of H to which we could embed x, we choose u. Using Lemma <ref><ref> to estimate the probability of the first event occurring, with t_0=0 and t_1=x-1 (and so  is trivial) we have
  
    [x u]    =
        [u∉ψ_x-1]
        [x u| u∉ψ_x-1]=
        (1± 100Cαδ^-1)n-1-x+1/n·1/n-x+1
        =(1± 200Cαδ^-1)1/n .


  If, on the other hand, there is y such that xy∈ E(H), then we embed x to u if and only if we embed x to u and y to some neighbour v of u in H. Since these events are disjoint as v ranges over the neighbours of u, the probability that one of them occurs is exactly the sum of their individual probabilities, and the latter are estimated by Lemma <ref>. Since by the (α,2D+3)-quasirandomness of H, the vertex u has (1±α)pn neighbours, we obtain
  
    [x u]    =
        ∑_v∈ N_H(u)[x u,y v]=
        (1±α)pn·(1± 500Cαδ^-1)^4D+21/pn^2
        =(1± 10^4Cα Dδ^-1)1/n .

  In either case, we conclude the desired bound.


We further need the following lemma, estimating the probability that a given
vertex of G is embedded to a given vertex of H and another given vertex
of H is not used in the embedding of the first n-⌊μ n⌋ vertices of G. We will be interested in this when G is a special graph; so the remaining vertices of G (which  also embeds) are isolated vertices. The proof of this lemma is rather similar to the proof of <cit.>.



  Given D∈ℕ, γ>0, let δ, , C, α_0, α_2n
  be as in Setting <ref> and let p≥γ. Let α_0<α≤α_2n
  and let n be sufficiently large. 
  Let G and H be as in Setting <ref>. 
  Let x∈ V(G[ [n-μ n]]) and u,v∈ V(H) with u≠ v. When we run
   to construct an embedding ψ_n-⌊μ n⌋ of the first n-⌊μ n⌋ vertices of G into H, then
  
    [x v  and  u∉ψ_n-⌊μ n⌋]=(1±10^3Cα
        Dδ^-1)μ/n .
  


 Let y_1,…,y_d with d≤ D be the neighbours of x in _G(x)
  in degeneracy order, and (for convenience) define y_0=0. We define a collection of events. Let '_0 be the almost sure event. For each 1≤ i≤ d, let _i be the intersection of '_i-1 and the event that neither u nor v is in the image of ψ_y_i-1, and let '_i be the intersection of _i and the event that y_i is embedded to a vertex of N_H(v)∖{u}. Let _d+1 be the intersection of '_d and the event that neither u nor v is in the image of ψ_x-1. Let '_d+1 be the intersection of _d+1 and the event x v. And finally let _d+2 be the intersection of '_d+1 and the event that u∉ψ_n-⌊μ n⌋. Note that all of these events are history ensembles up to some given time.
  
  Now what we want to do is estimate [_d+2], and the reason for giving this collection of events is that we can estimate each of the successive conditional probabilities. We can estimate [_i|'_i-1] for each 1≤ i≤ d+2 using Lemma <ref> (using part <ref> for 1≤ i≤ d+1 and part <ref> for the final part). And we can estimate ['_i|_i] using the diet condition for each 1≤ i≤ d+1; the probability that the diet condition fails is tiny. To justify both of these steps we need to know [_i],['_i]>n^-4; this is (by induction) valid since the final _d+2 is the smallest event and we will argue its probability satisfies this bound. Assuming this bound for a moment, by Lemma <ref>, for each 1≤ i≤ d we have
  
    [_i|'_i-1]=(1± 100Cαδ^-1)(n-y_in-y_i-1)^2 ,  [_d+1|'_d]=(1± 100Cαδ^-1)(n-xn-y_d)^2
    and  [_d+2|'_d+1]=(1± 100Cαδ^-1)⌊μ n⌋-1n-x .

  
  For each 1≤ i≤ d, we have
  
    ['_i|_i]=(1± Cα)p^_G(y_i)+1(n-y_i+1)± 1/(1± Cα)p^_G(y_i)(n-y_i+1)± 4n^-5=(1± 4Cα)p .

  The fraction in the first term assumes the (Cα,2D+3)-diet condition,
  for the vertices ψ_y_i-1(_G(y_i))∪{v} in the
  numerator and ψ_y_i-1(_G(y_i)) in the denominator, to
  estimate respectively the number of neighbours of v in the candidate set of
  y_i which are not in ψ_y_i-1 and the number of vertices in the
  candidate set of y_i which are not covered by ψ_y_i-1. The ±1
  term in the numerator covers the possibility u∈ N_H(v). The 4n^-5
  error term covers  the possibility of failure of the
  diet condition: By Lemma <ref> the probability that the diet condition
  fails is at most 2n^-9, hence since [_i]>n^-4 the
  probability that the diet condition fails conditioned on _i is at
  most 2n^-5. By similar logic, we have
  
    ['_d+1|_d+1]=1/(1± Cα)p^d(n-x+1)± 4n^-5=(1± 4Cα)1p^d(n-x+1) .

  
  Multiplying together all these conditional probabilities, many terms cancel and we obtain
  
    [_d+2]   =(1±100Cαδ^-1)^d+2(1±4Cα)^d+1(n-x)(⌊μ n⌋-1)/n^2(n-x+1)
       =(1± 100Cαδ^-1)^2D+4·μ/n ,

  which since α≤α_2n and by choice of α_2n implies the desired bound.




 §.§ Properties of 



The following lemma summarises some facts we obtain in the course of proving <cit.>.


  Given D, p̂, γ, let (α_s)_s∈[s^*], η and the graphs
  (G”_s)_s∈[s^*], H be as in Setting <ref>.
  When  is run with input (G”_s)_s∈[s^*] and
  H, with probability at least
  1-2n^-5, the following holds.
  
    
  *   succeeds in packing (G”_s)_s∈[s^*]
      into H.
    
  *  For each s∈[s^*] the pair (H_s,H^*_0) is (α_s,2D+3)-coquasirandom.
    
  *  The leftover graph H is (η,2D+3)-quasirandom.
    
  *  H_0^* has maximum degree at most 2γ n.
  


 <ref> is obtained by summing the failure probabilities of all exceptional events in <cit.>.

 <ref> holding is implied by the exceptional event (ii) of that proof not occurring.
 
 <ref> is implied by exceptional event (v) of <cit.> not occurring. Again, event (v) not occurring states that (H_s^*,H^*_s^*) is (η,2D+3)-quasirandom. We would like to know that this implies H=H_s^*∪ H^*_s^* is (η,2D+3)-quasirandom. Since H_s^* and H^*_s^* are edge-disjoint, given any vertex set S of size at most 2D+3, the neighbours N_H(S) are partitioned into parts indexed by the subsets R of S, where a vertex v is in the part indexed by R if it is adjacent in H_s^* to the vertices R and in H^*_s^* to the vertices S∖ R. Now (η,2D+3)-coquasirandomness gives bounds on these part sizes with a (1±η) relative error, and summing the bounds we obtain the desired (η,2D+3)-quasirandomness of H.
Indeed, by the argument above we obtain

    N_H(S)
        =∑_R⊆ S (1±η)(p_s*)^|R|
    (p_s*^*)^|S∖ R| n 
        = (1±η) n ∑_r=0^|S|sr(p_s*)^r
    (p_s*^*)^|S|-r
    = (1±η)(p_s*+p_s*^*)^|S| n

for every S of size at most 2D+3.
 
 <ref> is implied by exceptional event (i) not occurring: this event in particular implies that H^*_0 is (14α_0,2D+3)-quasirandom, which together with the fact e(H^*_0)=(1±α_0)γn2 from <cit.> implies the claimed maximum degree.


We further need the following two lemmas. The first states that, while
running , chosen subsets T of neighbourhoods of vertices shrink
roughly as expected. We will use this with T being a vertex neighbourhood with the embedded image of one or two of the G”_i removed. Recall that p_s denotes
the density of H_s.


  Assume Setting <ref> and let s^*-⌊μ n⌋<s<s'≤ s^*. Consider the following experiment.
  Run  with input
  (G”_s”)_s”∈[s^*] and H up to and including the
  embedding of G”_s. Then fix T⊂ N_H_s(v) with
  |T|≥1/2 pμ^2 n, and continue  to perform the embedding
  of G”_s+1,…,G”_s'.
  
  The probability that  fails before embedding G”_s', or H_i fails to be (α_i,2D+3)-quasirandom for some 1≤ i≤ s', or we have 
    |T∩ N_H_s'(v)|=(1±γ^-1α_s')p_s'/p_s|T| ,

  is at least 1-n^-C.


 For s≤ i≤ s', we define the event _i that  does not fail before embedding G”_i, and H_j is (α_j,2D+3)-quasirandom for each 1≤ j≤ i,
  and |T∩ N_H_j(v)|=(1±γ^-1α_j)p_j/p_s|T| for each s≤ j≤ i. If the event in the lemma statement fails to occur, then there must exist some s≤ i< s' such that _i occurs and
  
    |T∩ N_H_i+1(v)|≠(1±γ^-1α_i+1)p_i+1/p_s|T| .

 It suffices to show that each of these bad events occurs with probability at most n^-C-1, since then the union bound over the at most μ n choices of i gives the lemma statement. This is an estimate we can obtain using Corollary <ref>. We now fix s≤ i<s' and prove the desired estimate.
 
 Suppose s≤ j≤ i, and let Y_j:=|N_H_j(v)∩ T∖ N_H_j+1(v)| be the number of edges from v to T used for the embedding G_j+1. Then we have |T∩ N_H_i+1(v)|=|T|-∑_j=s^iY_j, and what we want to do is argue that the sum of random variables is concentrated. To that end, suppose  is a history of  up to time j such that H_j is (α_j,2D+3)-quasirandom and |T∩ N_H_j(v)|=(1±γ^-1α_j)p_j/p_s|T|. Then we have
 
    [Y_j | ]=2e(G”_j+1)·(1± 500Cα_jδ^-1)^4D+2/p_jn^2·(1±γ^-1α_j)p_j/p_s|T|

  where we use linearity of expectation: the first factor is by Lemma <ref> the probability that a given edge from v to T in H_j is used in the embedding of G”_j, and the second factor is the number of such edges. Note that the p_j terms cancel, so we obtain
  
    [Y_j | ]   =2e(G”_j+1)·(1± 500Cα_jδ^-1)^4D+2/p_sn^2·(1±γ^-1α_j)|T|
       =2e(G”_j+1)|T|/p_s n(n-1)±10^5δ^-1CD^2|T|/p_s
          nα_j ,

  where for the error term we use the upper bound e(G”_j+1)≤ Dn and our choice δ^-1>γ^-1. Let
  
    μ̃:=∑_j=s^i2e(G”_j+1)|T|/p_s n(n-1)  and  ν̃:=∑_j=s^i10^5δ^-1CD^2|T|/p_s
          nα_j

and observe that μ̃≤ |T|≤ n and
ν̃≤10^5δ^-1CD^2|T|/p_sα_i < |T|/10^3 since p_s≥γ and
by the definition of α_j. 
  
  We trivially have 0≤ Y_j≤Δ(G”_j+1)≤  cn/log n. So what Corollary <ref><ref>, with ρ̃= n, gives us is that
  
    [_i and ∑_j=s^iY_i≠μ̃±(ν̃+ n)]<2exp(-^2n^24cn^2/log n)<n^-C-1 ,

  where we use the upper bound μ̃+ν̃+ρ̃≤ 2n for the first inequality and the choice of c as well as < 1/C for the second. This is the probability bound we wanted. We now simply need to show that if
  
    ∑_j=s^iY_i=μ̃±(ν̃+ n)

  then we have
  
    |T∩ N_H_i+1(v)|=(1±γ^-1α_i+1)p_i+1/p_s|T| .
 
  Since
  
    |T|-μ̃=|T|(1-∑_j=s^ie(G”_j+1)p_sn2)=|T|(1-(p_s-p_i+1)n2p_sn2)=p_i+1/p_s|T| ,

  what remains is to argue ν̃+ n<γ^-1α_i+1p_i+1p_s|T|. Since α_j=δ/10^8CDexp(10^8CD^3δ^-1(j-2n)/n) is increasing in j, we have
  
    ∑_j=s^iα_j   ≤∫_s^i+1α_j dj≤∫_-∞^i+1α_j dj
       =[δ/10^8CD·n/10^8CD^3δ^-1·exp(10^8CD^3δ^-1(j-2n)/n)]_j=-∞^i+1
        =δ n/10^8CD^3α_i+1 .

  It follows that
  
    ν̃+ n≤10^5δ^-1CD^2|T|/p_s n·δ n/10^8CD^3α_i+1+ n≤α_i+11000D·1p_s|T|+ n .

  Finally, since p_i+1,p≥γ, by choice of , since δ≤μ and because |T|≥12 pμ^2n, we conclude ν̃+ n≤γ^-1α_i+1p_i+1p_s|T| as desired.


The second lemma states that for a set S of host graph vertices fixed
before the embedding of G”_s, it
is likely that the embedding of G”_s (which has n-⌊μ n⌋ vertices) uses about (1-μ)|S| vertices of S. To prove it, we repeatedly apply Lemma <ref>, which tells us that it is likely that each successive n vertices of G”_s embedded cover about the expected fraction of S.


  Assume Setting <ref> and let s^*-⌊μ n⌋<s≤ s^*.  Run  with input
  (G”_s”)_s”∈[s^*] and H up to just before the
  embedding of G”_s.
  Then fix any S⊂ V(H_s-1) with |S|≥1/2pμ^2 n, and
  let  perform the embedding of G”_s. With
  probability at least 1-3n^-9 either H_s-1 is not (α_s-1,2D+3)-quasirandom or
  
    |S∖ϕ'_s|=(1± C'α_s)μ|S| .



  Fix s such that s^*-⌊μ n⌋<s≤ s^*, and condition on H_s-1. If H_s-1 is not (α_s-1,2D+3)-quasirandom, then the bad event of this lemma cannot occur. So it suffices to show that if H_s-1 is (α_s-1,2D+3)-quasirandom, then the probability of the event |S∖ϕ'_s|≠(1± C'α_s)μ|S|, conditioned on H_s-1, is at most 3n^-9. This is what we will now do, so we suppose that H_s-1 is (α_s-1,2D+3)-quasirandom. Consider the run of  which embeds G”_s[ [n-δ n]]. 
  
  Recall that the embedding ϕ'_s of G'_s is given by letting  perform the embedding
  of G”_s[ [n-δ n]], constructing the partial embeddings ψ_t for
  0≤ t≤(1-δ)n. More precisely, ϕ'_s is given by ignoring the
  embedding of all vertices not in G'_s, that is, by ψ_n-⌊μ n
    ⌋.

Define S_0=S, and for i=1,…,τ with
  τ=⌈(1-μ)/⌉ set
  S_i=S_i-1∖ψ_i n. Since S_τ⊆ S∖ϕ'_s⊆ S_τ-1, it is enough to show both |S_τ-1| and |S_τ| are likely to be in the claimed range. Since the two quantities differ by at most n, we will focus on estimating |S_τ|.
  In this proof we will always use α=α_s, and hence will
  often omit the parameter α in β_t=β_t(α). 
  By Lemma <ref> (applied with t=j+ n +1), with probability at
  least 1-n^-2D-18, either for some j≤ n-μ n- n
  
    
  *  failed to
      construct ψ_j, or
    
  * the partial embedding ψ_j+ n +1 
    of G_s”[ [j+ n +1]] into H_s-1
    does not have the
      (,20Dβ_j,j)-cover condition,
  
  or we have that for every j≤ n-μ n- n
 
    
  *  
    | {x:  j≤ x<j+ n: ψ_j+ n(x) ∈ S∖ψ_j 
    		}| =
    		(1± 40Dβ_j)|S∖ψ_j|
      n/n-j  .
   
  
  By Lemma <ref>, with probability at least 1-2n^-9, the first
  two options do not hold, so with probability at least 1-3n^-9 we have
  that <ref> holds for every j≤ n-μ n - n. Applying <ref> with j=(i-1) n we conclude
  
    |S_i|=|S_i-1|-(1± 40Dβ_(i-1) n)|S_i-1|
          n/n-(i-1) n
 
for all i≥ 1.
  
  
  Assuming this is the case, we get
  
    |S_i|=|S_i-1|(1-(1± 40Dβ_(i-1) n)/1-(i-1)) ,

  and hence
  
    |S_τ|=|S|∏_i=1^τ(1-(1± 40Dβ_(i-1) n)/1-(i-1)) .

  In order to evaluate this product, observe that
  
    1-(1± 40Dβ_i n)/1-i
        =1-(i+1)/1-i±40 Dβ_i n/1-i
        = 1-i-/1-i(1±40Dβ_i
            n/1-(i+1)) ,

  and therefore
  
    |S_τ|=|S|∏_i=0^τ-11-i-/1-i·(1±40Dβ_i n/1-(i+1))
        =|S|(1-τ) ∏_i=0^τ-1(1±40Dβ_i n/1-(i+1)) .

  
By the definition of τ we have
  (1-μ)/≤τ≤(1-μ)/+1 and hence (1-τ)=μ(1±/μ).
Moreover, we obtain that

    ∑_i=0^τ-140Dβ_i n/1-(i+1)   ≤40D/1-τ∑_i=0^τ -1β_i n≤80D/μ∑_i=0^τ -1β_i n
       ≤80D/μ n∫_0^τ nβ_i n di
        ≤80D/μ n∫_0^τ nβ_x dx 
       eq:betabound80D/μ· 1000
          Dδ^-2γ^-2D-10β_τ n≤β_(1-μ +  )n≤1/2 C'α=1/2 C'α_s
  
   since
  β_(1-μ+)n=β_(1-μ+)n(α)=2αexp(1000Dδ^-2γ^-2D-10(1-μ+))<2α
  and 
    C'=10^4·40D/δexp(1000Dδ^-2γ^-2D-10) .

  

So, since ∏_i(1± x_i)=1±2∑_i x_i
  as long as ∑_i x_i < 1/100
  and since 1/2C'α_s < 1/100, 
  we get
  
    |S_τ|   =|S|(1-τ)(1±2∑_i=0^τ-140Dβ_i
              n/1-(i+1))
          =|S|(1-τ)(1±80D/1-τ∑_i=0^τ-1β_i
            n) 
       =|S|(1-τ± 80D∑_i=0^τ-1β_i
            n)
          =|S|μ(1±/μ±80D/μ∑_i=0^τ-1β_i
            n) 
       =|S|μ(1±1/2α_s ±1/2C'α_s) ,

  where for the last equation we use that ≤α_0δ^2γ≤1/2α_sμ. It follows that  
  
    |S∖ϕ'_s|=
      |S_τ|± n = 
      |S|μ(1±12α_s±12C'α_s)± n=(1± C'α_s)μ|S| ,

  as desired.




 §.§ Proof of Lemma <ref>



We now have all tools at hand to prove the almost perfect packing lemma.

 
  For 0≤ s<s^* let _s be the event that H_s is
  (α_s,2D+3)-quasirandom. By
  Lemma <ref><ref> we have
  
    [⋂_s_s]≥ 1-2n^-5 .

  Let _s be an embedding of G”_1,…,G”_s by 
  such that _s holds.

  Recall that we may assume that e(H_0^*)≤ 1.1γn2 holds,
  which is fine as the probability of this inequality not being satisfied is at
  most e^-n. So, from now on we always condition on this assumption, and we
  shall show in the following that then each of the properties
  <ref>–<ref> holds with probability at
  least 1-n^-4, which gives the lemma.

  <ref>:
  H is (γ'^3,2D+3)-quasirandom and has density p.

  

  By Lemma <ref><ref>, the leftover
  graph H is (η,2D+3)-quasirandom with probability at least 1-2n^-5.
  By (<ref>) and since γ≪γ' we
  have
  η≤γ'^3, which gives <ref>.
  
  

  <ref>:
  w(v)=(1±γ'^3)pn/2.

  

  Fix v∈ V(H) and let Y_s=w_s(x)_x v. We have Y_s≤Δ and
  
    w(v)=∑_s w_s(v)=∑_s,x∈ V(G_s) Y_s .

  We want to apply Corollary <ref>. By Lemma <ref> we have
  
    ∑_s∈[s^*][Y_s | _s-1]=
          ∑_s∈[s^*] 
    x∈ V(G_s) w_s(x)[x v| _s-1]=
          ∑_s∈[s^*] 
    x∈ V(G_s) w_s(x) (1±10^4 Cα_s Dδ^-1)1/n .

  It follows that
  
    ∑_s∈[s^*][Y_s | _s-1]=
          pn2(1±10^4 Cα_s^* Dδ^-1)1/n=
          pn/2(1±2· 10^4 Cα_s^* Dδ^-1) .

  By the second part of Corollary <ref><ref>
  applied with =⋂_s_s, =pn/2, =2·
  10^4 Cα_s^* Dδ^-1 we obtain
  
    [ and ∑_s Y_s≠pn/2·(1±
        4· 10^4Cα_s^* Dδ^-1)]
           ≤ 2exp(-· 4· 10^8C^2α_s^*^2
          D^2δ^-2/4Δ) 
       ≤ 2exp(-10^10log n) ,

  where the last inequality uses Δ≤ cn/log n, c≤
  10^-10γ^10Dα_0^4, α_0≤α_s^*, p≥μν and γ≪ν≤μ.

  We have s^*≤7/4 n and hence by the definition of α_x and of C
  in (<ref>) we get
  
    4· 10^4Cα_s^* Dδ^-1   ≤ 4· 10^4Cα_7/4n Dδ^-1
        = 4· 10^4C·δ/10^8CDexp(-10^8CD^3δ^-1·14 )
      · Dδ^-1
       ≤exp(-10^7CD^3δ^-1) 
      ≤exp(-10^7· 40Dexp(1000Dδ^-2γ^-2D-10)) 
       ≤exp(-exp(γ^-2D-10))
      ≤γ^3≤γ'^3 .

  Combining this with (<ref>) and (<ref>) and a union
  bound over v, we
  conclude that <ref> fails with probability at most
  2n^-5+n· n^-10≤ n^-4.

  

  <ref>:
  |N_H(v)∖ϕ'_s|=(1±γ'^3)μ pn
  and

  
    <ref>:
    |N_H(v)∖
    (ϕ'_s∪ϕ'_s')|=(1±γ'^3)μ^2pn if s≠ s'.

  

  We prove these together.
  Fix v∈ V(H) and s,s' with s^*-⌊μ n⌋<s<s'≤ s^*+1.
  The artificial case s'=s^*+1 will be used to prove <ref>.

  We first run  up to time s-1 and consider the
  embedding of G”_s. We want to apply Lemma <ref> to estimate what
  happens in this first stage.
  We set S=N_H_s-1(v), so if _s-1 holds then
  |S|=(1±α_s-1)p_s-1n≥1/2pn≥1/2pμ^2 n.
  Hence we can apply Lemma <ref> with S and
  conclude that with probability at least 1-3n^-9 either _s-1
  does not hold or
  
    |N_H_s-1(v)∖ϕ'_s|
        =(1± C'α_s)μ|S|
        =(1± 3C'α_s)p_s-1μ n .

  Further, we have N_H_s(v)∖ϕ'_s=N_H_s-1(v)∖ϕ'_s.

  Now let  perform the embeddings of G”_s+1,…,G”_s'-1. We want to
  apply Lemma <ref> to estimate what happens in this second stage.
  Set T=N_H_s(v)∖ϕ'_s and observe that T∩
  N_H_s'-1(v)=N_H_s'-1(v)∖ϕ'_s.
  If (<ref>) holds, then |T|≥1/2pμ^2 n because
  by (<ref>) we have C'α_s≤ 10^-4. So
  by Lemma <ref> applied with T we get that with probability at
  least 1-n^-C either ⋂_i_i fails or we have
  
    |N_H_s'-1(v)∖ϕ'_s|     =(1±γ^-1α_s'-1)p_s'-1/p_s|T|
        eq:appl:Nv1 (1±γ^-1α_s'-1)p_s'-1/p_s (1±
        3C'α_s)p_s-1μ n 
        = (1± 5C'α_s'-1) μ p_s'-1 n

  where the last equality follows from p_s-1/p_s=1+o(1) and since γ^-1<C'.
  For the case s'=s^*+1 this immediately implies <ref>.
  Indeed, in this case (<ref>) gets 
  
    |N_H_s^*(v)∖ϕ'_s|= (1± 5C'α_s^*) μ p_s^* n  .

As long as Δ(H^*_s^*)≤Δ(H^*_0)≤ 2γ n, which holds with probability at least
 1-2n^-5 according to
 Lemma <ref><ref>,
 we have that |N_H(v)|-|N_H_s^*(v)|≤ 2γ n and p_s^*=p± 2γ=(1±2γ/p)p
 from which we conclude that
  
    |N_H(v)∖ϕ'_s|= (1± 5C'α_s^*) (1±2γ/p)μ p n ± 2γ n 
        = (1±γ'^3)μ pn

  since C'α_s^*<1/100γ'^3, since
  γ≪γ'≪ν≪μ and p≥μν.
  Hence, in total, taking a union bound over v and s and using (<ref>),
  the probability that <ref> fails is at most
  4n^-5+n^2(3n^-9+n^-C)≤ n^-4.

  For proving <ref>, assume that s'≤ s^* and consider next the
  embedding of G”_s' by . We again want to apply Lemma <ref>, this
  time with S=N_H_s'-1(v)∖ϕ'_s. If (<ref>)
  holds, then
  |S|=(1± 5C'α_s-1)μ p_s-1n≥1/2pμ^2 n.
  Hence we can apply Lemma <ref> with S and with s' in place
  of s to
  conclude that with probability at least 1-3n^-9
  either (<ref>) fails, or _s'-1 fails or
  
    |N_H_s'(v)∖(ϕ'_s∪ϕ'_s')|    
        =|N_H_s'-1(v)∖(ϕ'_s∪ϕ'_s')| 
        =(1± C'α_s')μ|S|
        =(1± 7C'α_s')p_s'-1μ^2 n .


  In a last stage, consider the embedding of G”_s'+1,…,G”_s^*
  by . We apply Lemma <ref> with 
  T=N_H_s'(v)∖(ϕ'_s∪ϕ'_s')⊂ N_H_s'(v) and with s'
  replaced by s^*, which is possible if (<ref>) holds since
  then |T|≥1/2 pμ^2n. In this case, because T∩
  N_H_s^*(v)=N_H_s^*(v)∖(ϕ'_s∪ϕ'_s'),  we conclude that with
  probability at least 1-n^-C we have 
  
    |N_H_s*(v)∖(ϕ'_s∪ϕ'_s')|     =(1±γ^-1α_s^*)p_s^*/p_s'|T| 
       eq:appl:Nv3 (1±γ^-1α_s^*)p_s^*/p_s' (1±
        7C'α_s')p_s'-1μ^2 n 
         = (1± 9C'α_s^*) μ^2 p_s^* n

  from which we obtain
  
    |N_H(v)∖(ϕ'_s∪ϕ'_s')|          = (1±γ'^3) μ^2 p n

  analogously to the discussion of <ref> and
  as long as Δ(H_0)≤ 2γ n.
  We conclude, using a union bound over v,
  s and s' and again (<ref>) and
  Lemma <ref><ref>,
  that <ref> fails with probability at most
  4n^-5+n^3(2· 3n^-9+2· n^-C)≤ n^-4.

  

  
  <ref>:
  ∑_s w_s(v)_u∉ϕ'_s=(1±γ'^3)μpn/2.

  

  Fix u and v≠ u and define
  
    Y_s=w_s(v)_u∉ϕ'_s ,

  and observe that Y_s≤ w_s(v)≤Δ. 
  Again, we want to apply Corollary <ref>.
  We have
  
    [Y_s|_s-1]=∑_x∈ V(G_s)w_s(x)·[x v,u∉ϕ_s'|_s-1] .

  By Lemma <ref> we obtain
  
    [Y_s|_s-1]=
      ∑_x∈ V(G_s) w_s(x)·(1± 10^3Cα_s-1
        Dδ^-1)μ/n
        =⌊ν n⌋·(1± 10^3Cα_s-1 Dδ^-1)μ/n .

  This implies
  
    ∑_s [Y_s|_s-1]=⌊μ n⌋⌊ν n⌋·(1± 10^3Cα_s^* Dδ^-1)μ/n 
      =μ pn/2·(1± 2· 10^3Cα_s^* Dδ^-1) .

  We apply the second part of Corollary <ref><ref> with
  
    =⋂_s_s ,    R=Δ ,   =μ pn/2 ,   =2· 10^3Cα_s^* Dδ^-1
 and use
  ≤1/2, which holds by definition of α_s^*, to
  conclude that
  
    [ and ∑_s Y_s≠μ pn/2·(1±
        4· 10^3Cα_s^* Dδ^-1)]
           ≤ 2exp(-·4· 10^6C^2α_s^*^2
          D^2δ^-2/4Δ) 
       ≤ 2exp(-10^10log n) ,

  where the last inequality uses Δ≤ cn/log n, c≤
  10^-10γ^10Dα_0^4, α_0≤α_s^*, p≥μν and γ≪ν≪μ.
  Combining this with (<ref>)
  and (<ref>) and using a union bound over all u, v, we conclude that
  <ref> fails with probability at most 2n^-5+n^2·
  n^-10≤ n^-4.

  

  
    <ref>: If u∉ϕ'_s then we have ∑_v
      vu∈ E(H) w_s(v)<10p^2 n/μ.

  

    The verification of this statement is the most complicated part of this
    proof. We fix u∈ V(H) and s with s^*-⌊μ n⌋<s≤ s^*.
    We shall show that either an unlikely event occurs, or the desired property
    holds when G'_s is embedded, and then continues to hold while the
    remaining guest graphs are embedded. The embeddings of these guest
    graphs G'_s'
    is performed in the graphs H_s' and we shall show that
    ∑_v vu∈ E(H_s') w_s(v) stays concentrated.
    But since <ref>
    concerns the whole graph H, we additionally need to control the contribution of
    edges vu in H_s'^*, for which we can only provide an upper bound.
    More precisely, we shall establish the following claim. We will then, at the
    end of this proof, argue that this implies <ref>,

    
      Suppose u∉ϕ'_s. Then with probability at least 1-4n^-19
      either (H_i,H^*_0) is not (α_i,2D+3)-coquasirandom for some
      i∈[s^*], or (H_i-1,ϕ'_i([t])) does not satisfy
      the (Cα_i-1,2D+3)-diet condition for some i∈[s^*] and
      t∈[n-δ n], or (H_i-1,H^*_0,ϕ'_i([t])) does
      not satisfy the (2η,2D+3)-codiet condition for some i∈[s^*] and
      t∈[n-δ n], or for each s≤ s'≤ s^* we have
     
    ∑_v:vu∈ E(H_s')w_s(v)=(1± 10Cp^-1α_s')p_s'pn2μ ,

     and
     
    ∑_v:vu∈ E(H^*_0)w_s(v)≤γ pnμ .

    
    
    We will prove this claim in two steps. First (in
    Claim <ref>), we establish that it is very likely
    that (<ref>) holds for s'=s and
    that (<ref>) holds. Then, based on
    Claims <ref> to <ref>, we show that it
    is unlikely that any given s'>s is the smallest s' for
    which (<ref>) fails. Taking the union bound over s'
    will complete the proof of the claim.

  Recall again that the embedding ϕ'_s of G'_s is given by letting  perform the embedding
  of G”_s[ [n-δ n]],
  thus constructing partial embeddings ψ_t for
  0≤ t≤(1-δ)n,
  and then ignoring the
  vertices that do not belong to G'_s, i.e. the last 
  μ n - δ n ones.
  
    
      Suppose u∉ϕ'_s. Then with probability at least 1-n^-20
      the pair (H_s-1,H^*_0) is not (α_s-1,2D+3)-coquasirandom, or
      (H_s-1,ϕ'_s([t])) does not satisfy the
      (Cα_s-1,2D+3)-diet condition for some t∈[n-⌊μ n ⌋],
      or
      (H_s-1,H^*_0,ϕ'_s([t])) does not satisfy the
      (2η,2D+3)-codiet condition for some t∈[n-⌊μ n ⌋], or we have
     
    ∑_v:vu∈ E(H_s)w_s(v)=(1± 10Cp^-1α_s)p_spn2μ  and  ∑_v:vu∈ E(H^*_0)w_s(v)≤γ pnμ .

     
    
     We begin by proving the concentration of ∑_v:vu∈ E(H_s)w_s(v). For every t∈
      [n], let x_t be the t-th vertex of G_s”, let _t' be the event
      that H_s-1 is (α_s-1,2D+3)-quasirandom and
      (H_s-1,ϕ'_s([t])) satisfies the
      (Cα_s-1,2D+3)-diet condition, and let '_t be a history up
      to and including the embedding of x_t which satisfies '_t. When
       is run, for t∈[n-⌊μ n⌋] we obtain
      
    [x_t  N_H_s-1(u) | _t-1 ]
            =
            (1± Cα_s-1)p_s-1^1+_G^-(x_t)(n-t+1)/
              (1± Cα_s-1)p_s-1^_G^-(x_t)(n-t+1)
            =
            (1± 3Cα_s-1)p_s-1

      where the first equality holds, since under assumption of the diet
      condition for (H_s-1,ϕ_s'([t-1])) the candidate set for x_t is of
      size (1± Cα_s-1)p_s-1^_G^-(x_t)(n-t+1), and since
      u∉ϕ_s' and thus there exist (1±
      Cα_s-1)p_s-1^1+_G^-(x_t)(n-t+1) candidates among
      N_H_s-1(u). Now, set
      
    X_t:=w_s(x_t) ·_x_t  N_H_s-1(u)

      so that
      
    ∑_v:vu∈ E(H_s)w_s(v)=
            ∑_v:vu∈ E(H_s-1)w_s(v)=
            ∑_t∈ [n] X_t  ,

      where the first equation holds because of u∉ϕ'_s. In order
      to apply Corollary <ref><ref> observe that
      0≤ X_t≤Δ. Moreover,
      
    ∑_t∈ [n][X_t|'_t-1]
               = ∑_t∈ [n-⌊μ n⌋][X_t|'_t-1]
             = ∑_t∈ [n-⌊μ n⌋] w_s(x_t) [x_t  N_H_s-1(u) | '_t-1 ] 
        = (1± 3Cα_s-1)p_s-1∑_t∈ [n-⌊μ n⌋] w_s(x_t) 
              = (1± 4Cα_s-1) p_spn/2μ

      since p_s=(1-o(1))p_s-1, and ∑_t∈ [n-⌊μ n⌋] w_s(x_t) = ⌊ν n ⌋, and by definition of p. So,
      Corollary <ref><ref> with
      μ̃=p_spn/2μ, ν̃ =
      4Cα_s-1p_spn/2μ and ρ̃ =
      Cα_s-1p_spn/2μ yields
      
    ['_t  and ∑_t∈ [n]X_t 
            ≠ (1± 5Cα_s-1) 		
            p_spn/2μ]
            ≤
            2 exp(
            - C^2α_s-1^2p_spn/4Δμ (1+5Cα_s-1)) ≤ n^-21

      where the last inequality holds, since Δ≤cn/log n and
      by choice of c. This gives the first part of the claim, as
      5Cα_s-1≤ 10Cp^-1α_s.

      The second part of the claim, concerning H^*_0, is very similar, and we
      only sketch the proof. We define ”_t to be the event that
      (H_s-1,H^*_0) is (α_s-1,2D+3)-coquasirandom and
      (H_s-1,H^*_0,ϕ'_s([t])) satisfies the
      (2η,2D+3)-codiet condition, and let ”_t be a history up to
      and including the embedding of x_t which satisfies ”_t”. By a
      similar calculation as before, with p^*≤ 1.1γ being the density
      of H_0^*, we see that when  is run, we have
      
    [x_t N_H^*_0(u)|_t-1]=(1±6η)p^*≤ 32 γ,

      as the codiet condition for (H_s-1,H_0^*) makes sure that the
      candidate set for x_t is of size (1± 2η
      )p_s-1^_G^-(x_t)(n-t+1), while among these candidates (1±
      2η)p_s-1^_G^-(x_t)p^*(n-t+1) vertices belong to
      N_H^*_0(u).
 
      Having that, we can again define X'_t:=w_s(x_t)·_x_t
        N_H^*_0(u), and as before we obtain
      
    ∑_t∈[n][X'_t|”_t-1]=∑_t∈[n-μ
              n][X'_t|”_t-1]≤53·γ p n/2μ .


      Applying Corollary <ref><ref>, we get
      
    [”_t  and ∑_t∈ [n]X'_t > γ pn/μ] ≤ n^-21 .

      This is the second part of the claim; the total failure probability is at
      most 2n^-21<n^-20.
    
    
    We now need to show that it is unlikely that a given s'>s is the first
    s' for which (<ref>) fails. 
    To that end, fix s' with
    s^*-⌊μ n⌋≤ s<s'≤ s^*. For s<i≤ s^* we
    define 
    Y_i:=∑_v∈ N_H_i-1(u)∖ N_H_i(u) w_s(v) .

    We have
    
    ∑_v vu∈ E(H_s') w_s(v)=∑_v vu∈ E(H_s)
          w_s(v)-∑_i=s+1^s' Y_i ,
 and so the missing piece to establishing
    Claim <ref> is to show that the sum of the Y_i is
    likely to stay close to its expectation. We start by determining this expectation.

    
      Suppose that H_i-1 is (α_i-1,2D+3)-quasirandom, and suppose
      that (<ref>) holds for s'=i-1. Then when
       is run to embed G”_i[ [n-δ n]]
      into H_i-1, we have
      
    [Y_i|H_i-1]=(1± 10^4CDα_i-1δ^-1)·pe(G”_i)μ n .

    
    
      By definition of Y_i we obtain
      
    Y_i=∑_v∈ N_H_i-1(u)
            w_s(v)·_uv is used when embedding G_i”

      and therefore
      
    [Y_i|H_i-1]
            = 
            ∑_v∈ N_H_i-1(u)
            w_s(v)·[uv is used when embedding G_i”|H_i-1]  .

      Under assumption that H_i-1 is (α_i-1,2D+3)-quasirandom,
      Lemma <ref> yields
      
    [Y_i|H_i-1]
            = 
            ∑_v∈ N_H_i-1(u)
            w_s(v)· 
            (1± 500Cα_i-1δ^-1)^4D+22e(G_i”)/p_i-1n^2  .

      Applying (<ref>) for s'=i-1 finally leads to
      
    [Y_i|H_i-1]
                = (1± 10Cp^-1α_i-1)
              p_i-1pn/2μ· 
              (1± 500Cα_i-1δ^-1)^4D+22e(G_i”)/p_i-1n^2
         = (1 ± 10^4Cα_i-1Dδ^-1 )pe(G_i”)/μ n

      where last equality holds since p≥νμ and δ≪ν≪μ.
    
  
    What we would like to do now is apply Corollary <ref> (or
    Lemma <ref>) to show that the sum of the Y_i is likely to be
    close to the sum of the observed expectations we just calculated. But
    unfortunately this approach fails, because the range of the Y_i is too
    large; it is possible that there are as few as O(log n) vertices which
    contain all the weight of w_s in N_H_s(v), and we might use all the
    edges to these vertices in embedding a single G”_i. This is the reason
    for defining the random variables 
    
    Z_i:=max{Y_i-K'Δ,0}  with   K'=10^10CD^3δ^-1 .

    Trivially the `capped' random variable 
    Y'_i:=Y_i-Z_i
 does not have an
    excessively large range (it cannot exceed K'Δ), and we shall see (in
    the proof of Claim <ref>) that we can apply
    Corollary <ref> to argue that the sum of the Y'_i is concentrated. In order to
    show that this implies that also the sum of the Y_i is concentrated, we need
    to argue that the `error' caused by the Z_i is not too large, which we
    establish in Claim <ref>. As preparation for this, we will
    analyze the behaviour of the variables Z_i more in detail (in
    Claim <ref>) and bound their expectation (in
    Claim <ref>; we will need this bound when we show that the
    sum of the Y'_i is concentrated).

    Let us now try to understand the behaviour of Z_i.
    Consider the embedding of G”_i[ [n-δ n]] into
    H_i-1 by . Observe that Z_i is determined by the
    vertex x_t that is embedded to u and by the embedding of neighbours
    of x_t. Until we embed x_t to u at
    time t, we have used no edges of H_i-1 leaving u. On embedding a vertex to u,
    we have
    
    ∑_y∈_G”_i(x_t)w_s(ϕ'_i(y))≤ DΔ ,

    because x_t has at most D neighbours preceding it in the degeneracy
    order. Consider now the successive embedding of the forward neighbours
    y_1,…,y_ℓ of x_t by . In order for Z_i>0 to
    occur, we have to embed the next j forwards neighbours of x_t (for some
    j) to vertices such that ∑_k=1^j w_s(ϕ'_i(y_k))≥
    (K'-D-1)Δ. We say that the embedding of G”_i goes near the
      cap at the first time when we embed a y_j such that this inequality
    holds. We write (i,y) for the event that the embedding of G”_i goes near the cap at the time when we embed y (note that these events are pairwise disjoint as y ranges over V(G”_i)), and we write (i) for their union, i.e. the event that the embedding of G”_i goes near the cap at some time. If (i,y_j) occurs, we have the inequality Z_i≤∑_k=j+1^ℓ
    w_s(ϕ'_i(y_k)); it is important to note that the right hand side
    depends only on embeddings after the event of going near the cap is decided.
    Our next aim is to show that, conditioned on the embedding up to the time
    when x_t is embedded to u, it is unlikely that the embedding goes near
    the cap.
  
    
      Suppose that H_i-1 is (α_i-1,2D+3)-quasirandom. Suppose
      furthermore that ψ_t is a partial embedding of G”_i to H_i-1
      generated by  which embeds x_t to u (and embeds no
      vertices after x_t). Suppose that ψ_t is such that the probability, conditioned on
      H_i-1 and ψ_t, of (H_i-1,ϕ'_i) failing to have the
      (Cα_i-1,2D+3)-diet condition is at most n^-5. Then we have
     
    [(i) | H_i-1,ψ_t]≤ 3e^-K'/8 .

    
  
    With the notation from above, set
    
    X_k=w_s(ϕ_i'(y_k))

    for every forward neighbour y_k of x_t, and observe that 0≤ X_k≤Δ. Let '_k-1 be a history up to and including the embedding
    ψ_r of the vertex x_r which comes immediately before y_k in the
    ordering of G_i”. Let _r be the event that (H_i-1,ψ_r)
    satisfies the (Cα_i-1,2D+3)-diet condition.

    Then, if _r holds, we have
    
    [
            X_k | '_k-1]
          ≤⌊ν n ⌋/1/2p^Dμ n≤ 2p^-Dμ^-1ν

    since the sum over all weights from G_i” is ⌊ν n⌋, while
    the diet-condition ensures that the candidate set for y_k is of size at
    least
    
    (1-Cα_i-1)p^D⌊μ n⌋≥1/2p^Dμ n  .


    In particular,
    
    ∑_k=1^ℓ[X_k | '_k-1]
          ≤ 2p^-Dμ^-1νΔ  .

    Applying the first part of Corollary <ref><ref>
    with
    = ⋃_r _r,
    μ̃=ν̃
    = p^-Dμ^-1νΔ,
    ρ̃=(K'-D-1-2p^-Dμ^-1ν)Δ
    and R=Δ
    we then obtain that 
    
    [
           and  ∑_k=1^ℓ X_k ≥ (K'-D-1)
          Δ]
             ≤ 2exp(
            - (K'-D-1-2p^-Dμ^-1ν)^2/2(K'-D-1))
       ≤ 2exp(
            -(1/2K')^2/2K')
            = 2exp(-K'/8)  .

    Since by assumption the probability of  not occurring is at most n^-5, the claim follows.
  
  
  Now we can use this, and Lemma <ref>, to estimate the expectation of Z_i conditioned on H_i-1 which is quasirandom.
  
  
   Suppose that H_i-1 is (α_i-1,2D+3)-quasirandom.
   Then we have
   
    [Z_i|H_i-1]≤ 13e(G”_i)ne^-K'/8· 2νμ^-1p_s^*^-D .

  
  
    We have
    
    [Z_i|H_i-1]
          = ∑_x∈ V(G_i”)[x  u | H_i-1] ·[Z_i | x  u, H_i-1] .

    Assuming that H_i-1 is (α_i-1,2D+3)-quasirandom, we know by Lemma <ref> that
    
    [x  u | H_i-1 ]
          = (1+10^4Cα_s-1Dδ^-1)1/n =(1±12) 1/n .

    For estimating [Z_i | x  u, H_i-1], we let  be the event that (H_i-1,ϕ'_i) satisfies the
    (Cα_i-1,2D+3)-diet condition. Then by linearity of expectation we have
    
    [Z_i | x  u, H_i-1]   =[Z_i_ | x  u, H_i-1]+[Z_i_ | x  u, H_i-1]
       ≤[Z_i_ | x  u, H_i-1]+n·2n^-92/n=[Z_i_ | x  u, H_i-1]+4n^-7 ,

     where the estimate for the second term is from Lemma <ref> bounding
     the probability of  and (<ref>) lower bounding the
     probability of x u, and since trivially Z_i≤ Y_i≤ n. To
     estimate the first term, we observe that since outside (i) we
     have Z_i=0, it follows that
     
    [Z_i_|x u,H_i-1] 
    
           =∑_z∈ V(G”_i)[(i,z)|x
          u,H_i-1]·[Z_i_|x u,H_i-1,(i,z)] .

    Note that the only terms of the sum in which the probability is positive are those with z a forwards neighbour of x, so fix such a z. Recall that if (i,z) occurs then we have
    
    Z_i≤∑_y∈ N_G”_i(x)
    y comes after zw_s(ϕ'_i(y)) ,  and so  
        Z_i_≤∑_y∈ N_G”_i(x)
    y comes after zw_s(ϕ'_i(y))_ .

    For bounding [Z_i_|x u,H_i-1,(i,z)],
    for any forwards neighbour y of x which comes after z in the degeneracy order, let '_<y denote
    any history up to and including the embedding of the vertex which comes
    immediately before y that is consistent with x u and is contained in (i,z). Then we have
    
    [Z_i_|x u,H_i-1,(i,z)] 
    ≤∑_y∈ N_G”_i(x)
    y comes after z ∑_'_<y[w_s(ϕ'_i(y))_|'_<y,H_i-1]
          ·['_<y|x u,H_i-1,(i,z)] .

    Let y be a forwards neighbour of x which comes after z. Then y is
    not isolated, so it is in the first n-μ n vertices of G”_i.
    We want to calculate
    [w_s(ϕ'_i(y))_|'_<y,H_i-1].
    There are two cases to consider.
    First, if  occurs, then since y is in the first n-μ n vertices
    of G”_i, it has a candidate set of size at
    least
    
    (1-Cα_i-1)p_i-1^D⌊μ n⌋≥1/2p_s^*^Dμ n .

    Hence we embed y uniformly to a set of
    size at least 12p_s^*^Dμ n, so (because the total weight of all
    vertices in G”_s is ⌊ν n⌋) the expectation of
    w_s(ϕ'_i(y)) conditioned on '_<y and H_i-1 is at
    most ν np_s^*^Dμ n/2. Second, if y is chosen from a
    candidate set of size less than 12p_s^*^Dμ n, then the event
     does not occur, and so the conditional expectation we
    want to calculate is zero. In either case, we obtain
    
    [w_s(ϕ'_i(y))_|'_<y,H_i-1]≤ 2νμ^-1p_s^*^-D .

    Plugging this into (<ref>) gives 
    
    [Z_i_|x u,H_i-1,(i,z)]≤ d_G”_i(x)· 2νμ^-1p_s^*^-D ,

    since the sum over '_<y of ['_<y|x u,H_i-1,(i,z)] is trivially 1, and d_G”_i(x) is at least as big as the number of forward neighbours of x which come after y. Now putting this into (<ref>) we obtain
    
    [Z_i_|x u,H_i-1]   ≤∑_z∈ V(G”_i)[(i,z)|x
          u,H_i-1]· d_G”_i(x)· 2νμ^-1p_s^*^-D
       =[(i)|x
          u,H_i-1]· d_G”_i(x)· 2νμ^-1p_s^*^-D .

      
    We finally use Claim <ref> to estimate [(i)|x
    u,H_i-1]. By (<ref>), we have [x
    u|H_i-1]≥12n. By Lemma <ref>, the probability that
    (H_i-1,ϕ'_i) fails to have the (Cα_i-1,2D+3)-diet condition,
    conditioned on H_i-1, is at most 2n^-9. Consequently, summing up
    [ψ_x|x u,H_i-1] over partial embeddings ψ_x which
    embed the vertices up to and including x of G”_i, and embed x to u,
    but which fail the condition of Claim <ref> (i.e. the
    probability that (H_i-1,ϕ'_i) fails to have the
    (Cα_i-1,2D+3)-diet condition, conditioned on H_i-1 and
    ψ_x, exceeds n^-5), we obtain at most 4n^-3. For any ψ_x
    which does satisfy the condition of Claim <ref>, we have
    [(i)|H_i-1,ψ_x]≤ 3e^-K'/8. Putting these together, we have
    
    [(i)|x u,H_i-1]   =∑_ψ_x[ψ_x|x u,H_i-1]·[(i)|ψ_x,x u,H_i-1]
       ≤ 4n^-3· 1+1· 3e^-K'/8= 3e^-K'/8+4n^-3 .

    At last, we obtain
    
    [Z_i_|x  u,H_i-1]≤ (3e^-K'/8+4n^-3)· d_G_i”(x)· 2νμ^-1p_s^*^-D .

    Thus, using (<ref>), we have
    
    [Z_i|x  u,H_i-1]   ≤ (3e^-K'/8+4n^-3)· d_G_i”(x)· 2νμ^-1p_s^*^-D+4n^-7
       ≤ 3e^-K'/8· d_G_i”(x)· 2νμ^-1p_s^*^-D+n^-2 ,

    and so by (<ref>) and (<ref>) we get
    
    [Z_i|H_i-1]
             ≤∑_x∈ V(G_i”)2/n·( 3e^-K'/8· d_G_i”(x)· 2νμ^-1p_s^*^-D+n^-2)
        = 2 ∑_x∈ V(G_i”) d_G_i”(x)/n· 3e^-K'/8· 2νμ^-1p_s^*^-D + 2n^-2
            < 13 e(G”_i)n· e^-K'/8· 2νμ^-1p_s^*^-D .


  
This expectation is tiny, because the term e^-K'/8 is very small. Thus we see that the expectations of Y'_i and
Y_i (conditioning on any H_i-1 which is quasirandom) are very close. The final
thing we have to do before we complete the proof of
Claim <ref> is to show that the sum of the Z_i is likely to
be very small.

  
    With probability at least 1-2n^-20, the following event occurs when  is run. Either H_i is not (α_i,2D+3)-quasirandom for some i∈[s^*], or (H_i-1,ϕ'_i([n-μ n])) does not satisfy the (Cα_i-1,2D+3)-diet condition for some i∈[s^*], or we have
    
    ∑_i=s+1^s'Z_i≤α_s p n1000μ .

  
   Let  denote the event that H_i is (α_i,2D+3)-quasirandom for each i∈[s^*], and (H_i-1,ϕ'_i([n-μ n])) satisfies the (Cα_i-1,2D+3)-diet condition for each i∈[s^*]. So we want to show that it is likely that either  fails or ∑_i=s+1^s'Z_i<α_spn1000μ.
  
   In order to prove this claim, we need to reinterpret ∑_i=s+1^s'Z_i. The random variables Z_i can be very large, so that Corollary <ref> does not help us.
   
   What we do is to use our earlier observation that we can understand Z_i as
   follows. We watch  as it embeds G”_i[
     [n-δ n]], until it embeds some x_t to u, and then embeds
   the forwards neighbours of x_t until it goes near the cap (if one or the
   other event does not occur, then Z_i=0). Then Z_i is at most the sum of
   w_s(ϕ'_i(y)) taken over forwards neighbours y of x_t
   which are embedded after reaching the cap. We refer to these vertices y
   as after-cap vertices. We then use the inequality
   
    ∑_i=s+1^s'Z_i≤∑_i=s+1^s' ∑_v=ϕ'_i(y)
    for y after-cap in G”_iw_s(v) ,

   where the right hand side sum runs over all after-cap vertices in all graphs
   G”_s+1,…,G”_s'. For a given after-cap vertex y∈ V(G”_i) we
   know y is an after-cap vertex before we embed it. Now when we embed y,
   provided the (Cα_i-1,2D+3)-diet condition holds for
   (H_i-1,ϕ([n-μ n])), we embed it uniformly into a set S of size at
   least 12 p_i-1^Dμ n (because y, since it is not isolated, must
   be one of the first n-μ n vertices of G”_i). The sum of w_s(z) over
   the vertices z of S is at most ⌊ν n⌋. So the expected
   value of w_s(ϕ'_i(y)), conditioned on the history up to the time
   y-1 immediately before embedding y and on the (Cα_i-1,2D+3)-diet
   condition holding for (H_i-1,ϕ'_i([y-1])), is at most
   2⌊ν n⌋ p_i-1^-Dμ^-1 n^-1≤ 2p
   p_s^*^-Dμ^-2, where the inequality uses the equation ⌊ν
   n⌋⌊μ n⌋=pn2.
   
   Let 
    L:=40Dne^-K'/8 ,
 and define a random variable X_j for 1≤ j≤
   L by X_j=w_s(ϕ'_i(y)), where the jth after-cap vertex in a
   run of  is y∈ V(G”_i) (y and hence i depend on the
   run of ). If there is no such after-cap vertex, we let
   X_j:=0. Observe that we have 0≤ X_j≤Δ for each j, and what we
   just calculated is that, letting _j denote the history of
    up to immediately before embedding the jth after-cap
   vertex y∈ V(G”_i), if the (Cα_i-1,2D+3)-diet condition holds
   for (H_i-1,ϕ'_i([y-1])), then [X_j|_j]≤2p
   p_s^*^-Dμ^-2. So we can apply
   Corollary <ref><ref>, with μ̃=2p
   p_s^*^-Dμ^-2L, to obtain
   
    [ and ∑_j=1^LX_j>4p p_s^*^-Dμ^-2L]<exp(-2p p_s^*^-Dμ^-2L/4Δ)≤ n^-20 ,

   where the final inequality follows from Δ=cnlog n and by choice of c and K'.
   
   Let T denote the total number of after-cap vertices encountered during the
   entire run of . Since by choice of K' and (<ref>) we have 4p
   p_s^*^-Dμ^-2L<α_s p n1000μ, what we have just
   argued is that
   
    [ and  T≤ L  and ∑_i=s+1^s'Z_i>α_s p n1000μ]
         ≤ n^-20 .

   What we now want to do is estimate the probability of the event
   that  occurs and that T>L.
  
   To that end, for each s+1≤ i≤ s', we define X'_i to be the number of after-cap vertices embedded 
   from G”_i in a given run of . By definition we have T=∑_i=s+1^s'X'_i. Now, if H_i-1 is (α_i-1,2D+3)-quasirandom, we can estimate [X'_i|H_i-1] as follows. First, observe X'_i can only be positive if some x_t∈ V(G”_i) is embedded to u, and then G”_i goes near the cap, and then the remaining neighbours of x_t will be the after-cap vertices counted by X'_i. So we have
   
    X'_i≤∑_x_t∈ V(G”_i)_x_t u_(i)· d_G”_i(x_t) .

   It follows that
   
    [X'_i|H_i-1]≤∑_x_t∈
           V(G”_i)d_G”_i(x_t)[x_t u|
         H_i-1]·[(i)|H_i-1,ψ_t] ,

   where ψ_t is a partial embedding of the first t vertices of G”_i into H_i-1 generated by
    which embeds x_t to u.
   By respectively Lemma <ref> and Claim <ref>, we have
   
    [X'_i|H_i-1]≤∑_x_t∈ V(G”_i)d_G”_i(x_t)·(2n· 3e^-K'/8+2n^-4)≤ 20De^-K'/8 ,

   where the first inequality uses the observation that, by Lemma <ref>,
   there is at most 2n^-4 probability of generating ψ_t such that the
   (Cα_i-1,2D+3)-diet condition holding for (H_i-1,ϕ([n-μ n]))
   has more than n^-5 chance of failing (when embedding the remaining
   vertices). The second inequality uses the fact that G”_i has at most Dn
   edges and so the sum of its degrees is at most 2Dn.
   
   Since 0≤ X'_i≤Δ for each i, we can apply Corollary <ref><ref>, with μ̃=20Dne^-K'/8, to obtain
   
    [ and ∑_i=s+1^s'X'_i>40Dne^-K'/8]<exp(-20Dne^-K'/84Δ)≤ n^-20 ,

   where the second inequality comes from Δ=cnlog n and choice of c and K'. Since ∑_i=s+1^s' X_i'= T, this proves as desired that it is unlikely that  occurs and T>L.
   
   Putting these two pieces together, we conclude that with probability at most 2n^-20, the event  occurs and we have ∑_i=s+1^s'Z_i>α_spn1000μ. This completes the proof of the claim.
  
  
  The reader might at this point wonder why we cannot simply estimate the sum of the Y_i by modifying the above method. The point is that it is not easy to obtain an accurate estimate of the quantity [X_j|_j] in the above proof (the upper bound we obtain above is off from the truth by a rather large factor, compensated for by the unlikeliness of going near the cap), and we would need such an accurate estimate for Claim <ref>. 
  
  Finally, we are in a position to prove Claim <ref>.
  
  [Proof of Claim <ref>]
    Firstly, by Claim <ref> we have that either (H_i,H^*_0) is
    not (α_i,2D+3)-co­qua­si­ran­dom for some i∈[s^*], or
    (H_i-1,ϕ'_i([t])) does not satisfy the
    (Cα_i-1,2D+3)-diet condition for some i∈[s^*] and
    t∈[n-δ n], or (H_i-1,H^*_0,ϕ'_i([t])) does
    not satisfy the (2η,2D+3)-codiet condition for some i∈[s^*] and
    t∈[n-δ n], or that (<ref>) holds
    and (<ref>) holds for the case s'=s with probability at
    least 1-n^-20. Now, let s<s'≤ s^*. We aim to show that with
    probability at most 3n^-20 we have that (<ref>)
    continues to hold for s'. Taking a union bound over the choices of s'
    then completes the proof of Claim <ref>.
    
    More precisely, let  denote the event that u∉ϕ'_s, and
    (H_i,H^*_0) is (α_i,2D+3)-coquasirandom for each i∈[s^*], and
    (H_i-1,ϕ'_i([t])) satisfies the
    (Cα_i-1,2D+3)-diet condition for each i∈[s^*] and
    t∈[n-δ n], and (H_i-1,H^*_0,ϕ'_i([t]))
    satisfies the (2η,2D+3)-codiet condition for each i∈[s^*] and
    t∈[n-δ n], and (<ref>) holds for each s≤
    i<s'.  Our goal is to show that  occurs and (<ref>)
    fails for s' with probability at most 3n^-20. 

    By Claim <ref>, with probability at least 1-n^-20,
    either we witness a failure of  before beginning to embed G”_s+1,
    or we have ∑_v vu∈ E(H_s)w_s(v)=(1±
    10Cp^-1α_s)p_spn2μ. Suppose that this likely event
    occurs, and that we do not witness a failure of  before beginning to
    embed G”_s+1.
   
   Since we have
   
    ∑_v vu∈ E(H_s') w_s(v)=∑_v vu∈ E(H_s)
        w_s(v)-∑_i=s+1^s' Y_i ,

    and we want to conclude that it is unlikely that  occurs and ∑_v vu∈ E(H_s')w_s(v)≠(1± 10Cp^-1α_s')p_s'pn2μ, it is enough to estimate the probability, conditioned on H_s, that  occurs and
    
    ∑_i=s+1^s' Y_i≠(1± 10Cp^-1α_s)p_spn2μ-(1± 10Cp^-1α_s')p_s'pn2μ=(p_s-p_s')pn2μ± 20Cα_s'p_sn2μ .

    We have Y_i=Y'_i+Z_i for each i, and so
    ∑_i=s+1^s'Y_i=∑_i=s+1^s'Y'_i+∑_i=s+1^s'Z_i.
    For showing that (<ref>) is unlikely to occur, we will use
    Corollary <ref> to argue that ∑ Y'_i is concentrated and
    Claim <ref> to bound the contribution of ∑ Z_i. Accordingly,
    we shall first calculate the expectation of ∑ Y'_i.

    By Claim <ref>, provided H_i-1 does not
    witness that  fails, we have [Y_i|H_i-1]=(1±
    10^4CDα_i-1δ^-1)·pe(G”_i)μ n. By
    Claim <ref>, again provided H_i-1 does
    not witness that  fails, we have [Z_i|H_i-1]≤
    13e(G”_i)ne^-K'/8· 2νμ^-1p_s^*^-D. By linearity,
    we conclude
    
    [Y'_i|H_i-1]   =(1± 10^4CDα_i-1δ^-1)·pe(G”_i)μ n± 13e(G”_i)ne^-K'/8· 2νμ^-1p_s^*^-D
       =(1± 10^5 CDα_i-1δ^-1)·pe(G”_i)μ n ,

    where for the second inequality we use our choice of K'. Summing this up, we see that either  fails or we have
    
    ∑_i=s+1^s'[Y'_i|H_i-1]   =∑_i=s+1^s'(1± 10^5 CDα_i-1δ^-1)·pe(G”_i)μ n
       =∑_i=s+1^s'pe(G”_i)μ n±∑_i=s+1^s'10^5 CDα_i-1δ^-1·pDnμ n
       =pμ n(p_s-p_s')n2± 10^5CD^2δ^-1μ^-1p∫_i=-∞^s'α_idi
       eq:sum:alphapn2μ(p_s-p_s')±1μ± 10^5CD^2δ^-1μ^-1p·δ n/10^8CD^3α_s'
       =pn2μ(p_s-p_s')±pα_s'n/100μ=(p_s-p_s')pn2μ± Cα_s'p_sn2μ ,

    where the final inequality is by choice of C
    and since p≤ p_s+2γ
    according to (<ref>). Now applying the first part of Corollary <ref><ref>, with μ̃=(p_s-p_s')pn2μ and ν̃=ρ̃=Cα_s'p_sn2μ, and using the fact 0≤ Y'_i≤ K'Δ, we obtain
    
    [ and ∑_i=s+1^s'Y'_i≠(p_s-p_s')pn2μ± 2Cα_s'p_sn2μ]<2exp(-ρ̃^22K'Δ(μ̃+ν̃+ρ̃))≤ n^-20 ,

    where the final inequality uses Δ=cnlog n and the choice of c and K'.
    
    Putting this estimate together with Claim <ref>, where we show that with probability at least 1-n^-20 either  does not occur, or we have ∑_i=s+1^s'Z_i≤α_spn1000μ, we conclude the following. With probability at least 1-3n^-20, either  does not occur, or we have
    
    ∑_i=s+1^s'Y_i=(p_s-p_s')pn2μ± 2Cα_s'p_sn2μ±α_spn1000μ=(p_s-p_s')pn2μ± 3Cα_s'p_sn2μ .

    If this holds (<ref>) does not occur. With this we finally proved that with probability at most 3n^-20 the event  occurs and (<ref>) holds for each s≤ i<s' but fails for s'.
  
  
Finally, we argue that Claim <ref> implies <ref> holds with high probability. It is straightforward to check that 10Cp^-1α_s^*<1, and p_s^*≤ p. Since E(H)⊂ E(H_s^*)∪ E(H^*_0), provided (<ref>) with s'=s^* and (<ref>) hold, we have
 
    ∑_v:vu∈ E(H)w_s(v)   ≤∑_v:vu∈ E(H_s^*)w_s(v)+∑_v:vu∈ E(H^*_0)w_s(v)
       ≤ 2p_s^*pn2μ+γ p nμ<10p^2nμ ,

 where the last inequality follows since p_s^*,γ<p. Thus by
 Claim <ref>, with probability at least 1-4n^-19, either
 the stated coquasirandomness, diet or codiet conditions fail,
 or <ref> holds for fixed u and s. So it is enough to check
 that it is unlikely that either the stated coquasirandomness, diet or codiet
 conditions fail. By respectively
 Lemma <ref><ref>, and
 Lemma <ref><ref> and <ref> (and the union bound over the at
 most 2n runs of ), the probability that either of these
 occur is at most 2n^-5+4n^-8. For the latter, note that
 β_t(α_i-1)≤ Cα_i-1 for each i,t. We finally conclude,
 using a union bound over u and s, that <ref> holds with
 probability at least 1-n^2· 4n^-19-2n^-5-4n^-8>1-3n^-5.




§ CONCLUDING REMARKS


 Once one knows that a given collection of graphs  can be packed into a host graph H, it is natural to ask whether there is an efficient algorithm, randomised or not, which will exhibit such a packing. For  as in Theorem <ref> (with the various parameters taken as fixed while n is large) the obvious answer is simply to run our packing algorithm. Most of the steps in this algorithm simply consist of uniform random samples from sets which are of linear size and trivial to compute. In addition the completion step of  requires finding a perfect matching in a linear-sized and easily computed auxiliary bipartite graph; this is well known to be solvable in polynomial time using the augmenting paths algorithm. Finally, the completion step of  requires sampling uniformly from the set of perfect matchings of a dense bipartite graph (which is linear-sized and easy to compute).
 
 If one assumes that it is possible to sample in polynomial time from these
 various distributions, then our algorithm clearly is polynomial time. However,
 if the source of randomness is an unbiased bit string (which is the natural and
 usual assumption) then one cannot sample exactly uniformly from arbitrary distributions. It is standard in the literature to ignore this problem (because sample approximately uniformly is possible and this suffices), but for completeness we give the details.
 
 For the random sampling in , it is easy to sample approximately uniformly: using k bits of randomness one can approximately sample any
 probability p Bernoulli random variable up to an error 2^-k by viewing the bits as an integer in [2^k] and returning 1 if this integer is at most 2^kp. One can similarly select uniformly from a set, by partitioning [2^k] into intervals of approximately equal size corresponding to the set elements. For all the analysis here and in <cit.>, it is easy to check that using n random bits per sample, the sampling error is tiny compared to the probabilities we want to estimate and is absorbed by our error terms (in fact, O(log n) bits would suffice).
 
 However sampling a perfect matching approximately uniformly, even from a dense bipartite graph, is not so obviously possible. We actually do not need a uniform random perfect matching: what we need is any distribution on perfect matchings which satisfies the conclusion of Lemma <ref>, i.e. that any given edge is in the matching with probability not too much greater (by at most a factor 32 would suffice) than the average. So the question becomes whether one can sample in polynomial time from such a distribution. There is a Markov chain on perfect matchings due to Broder <cit.>, which Jerrum and Sinclair <cit.> showed can be simulated and has polynomial mixing time. This means we can sample in polynomial time from a distribution on perfect matchings which is exponentially close to the uniform distribution, and in particular has the desired property.
 
 In conclusion, one can actually simulate the randomised algorithm of <cit.> and this paper in polynomial time. Following the (somewhat) general belief that RP≠NP, this suggests that the packing problem for the graphs we pack in this paper should not be NP-complete (in contrast to the general packing problem, which is known to be NP-complete <cit.>). We suspect the problem is in P, but we do not know how to derandomise our algorithm, or otherwise provide a deterministic polynomial time algorithm for the packing.



§ ACKNOWLEDGEMENTS


Part of the work leading to this paper was done while PA and JB visited Hamburg.
PA and JB would like to thank TU Hamburg and the University of Hamburg for their
hospitality, the Suntory and Toyota International Centres for Economics and
Related Disciplines and TU Hamburg for financial support, and Heike Böttcher
for help with childcare arrangements.

amsplain_yk
	 

