Graph Decompositions at the Integral Expectation Threshold

Proof. If no such copy exists, no graph containing H can be contained in such a union. Thus \calF_H\subseteq\mathcal E_{K_0}(\calD). Theorem 2.1 supplies a cover of \calF_H of cost at most 1/2 at r, contrary to r>q(H;n).□

Proof. The family of all single edges covers \calF_H, proving the first bound. For the second, choose a subgraph of minimum degree d, with v vertices and a\geq dv/2 edges. Its copies on [n] form a cover of \calF_H with cost at most n^vp^a. At p=2^{-1/a}n^{-v/a}\in(0,1) this is at most 1/2. Since a\geq1 and v/a\leq2/d, this parameter is at least \frac12n^{-2/d}.□

Proof. Fix a degeneracy order. At each vertex, partition its edges to preceding neighbors into m groups of size at most \lceil d/m\rceil, and assign each group to its corresponding piece. Each edge is assigned once. The same order certifies the claimed bound in every piece.□

Proof. Start with \calQ=\varnothing. While some T\in\calR satisfies

add T to \calQ. The probability that Z satisfies the current family increases by

at each addition. A previously added set cannot be chosen again, and the process makes fewer than 2r^{-s} additions. It makes at least one, because \calR is nonempty.

At termination the conditional probability is at least 1/2 for every T\in\calR. The conditional law of Z given Z\supseteq T is the law of T\cup Z with a fresh Bernoulli sample. Hence f_{\calQ}(T)\geq1/2. The function f_{\calQ} is increasing in S, proving (3.2) whenever S contains such a T.□

Proof. We impose upper bounds on source sums of f_{\calQ} and lower bounds on target counts satisfying \calQ. Compression makes each vertex in a set U to be matched contribute at least 1/2 to an appropriate source sum, while each target neighborhood counted by the corresponding \calQ is usable for at least one vertex of U.

The test families. Use every Y\subseteq[n] of size at most n^{2/3} and every nonempty family

Write m=n-|Y|, put \tau=1-(1-r)^2, and let x(\calQ) and x_*(\calQ) be the probabilities that Bernoulli-\tau and Bernoulli-r_* subsets of Y satisfy \calQ, respectively. Both are at least r^s. Define \calD by requiring, for every test (Y,\calQ),

Also define a target event by the inequalities

for all of the same tests.

Simultaneous concentration. For fixed Y,\calQ and G\sim G(n,r), the summands in (3.5) are independent and lie in [0,1]. Their mean is x(\calQ): the neighborhood sample and the independent sample in (3.1) have union density \tau. Their independence follows because the edges from distinct vertices outside Y into Y are disjoint sets of random variables.

The logarithm of the number of tests is at most

with an absolute C. Indeed, choosing Y costs at most (\lfloor n^{2/3}\rfloor+1)n^{n^{2/3}} possibilities. One can then list at most \lceil2n^{1/100}\rceil subsets, each of size at most s\leq10\log n. This overcounts families and gives (3.7).

For large n, m\geq n/2. Since x(\calQ)\geq n^{-1/100}, Hoeffding’s inequality [4] bounds the failure probability of (3.5) for a fixed test by \exp(-c n^{98/100}). The indicators in (3.6), for G_*\sim G(n,r_*), are likewise independent, with mean x_*(\calQ)\geq n^{-1/100}. The same bound, with another absolute c>0, applies to their relative deviation by 1/4. Thus each simultaneous event has probability at least 1-\varepsilon_n, where uniformly in r,s,

Increase N_1 so that this error is at most \min\{1/K_0,1/2\} for n\geq N_1.

The relation between the two test means is important. A Bernoulli-r_* set is the union of 16 independent Bernoulli-\tau sets. Satisfaction is increasing, so

Hall’s criterion. Fix J,Y,G as in the statement and a target graph G_* satisfying (3.6). Keep Y fixed and match the positive-degree vertices of J outside Y to distinct vertices of [n]\setminus Y. A candidate image a is usable for a vertex w when N_J(w)\subseteq N_{G_*}(a)\cap Y.

For any nonempty set U of vertices to be matched, apply Lemma 3.1 to

It gives an admissible test \calQ\subseteq\calR. Every N_G(w)\cap Y, for w\in U, satisfies \calR, because G contains the labelled edges of J. Writing x=x(\calQ), (3.5) therefore yields

Repeated neighborhoods disappear from \calR, but their distinct vertices still contribute separately to this sum.

Every target vertex counted in (3.6) is usable for some vertex of U, because \calQ\subseteq\calR. If x\leq1/16, then

so there are at least 6xm\geq|U| usable vertices. If x>1/16, there are at least

Hall’s theorem [3] gives the matching in both cases. All choices of \calQ are legitimate even though they depend on J,U,G: the inequalities were established simultaneously for every test.

The matching embeds every edge of J while fixing Y. Any remaining isolated vertices can be added afterward. The target event has probability at least 1/2, giving p_c(J;n)\leq r_*. Finally, the union bound for 32 independent Bernoulli-r samples gives r_*\leq32r.□

Proof. Discard isolated vertices and assume that an edge remains. We partition the vertices into layers that are independent sets, constructed in reverse order. In any residual subgraph with m' vertices, the average degree is at most 2s. At least m'/2 vertices therefore have degree at most 4s. The graph they induce has an independent set of size at least m'/(2(4s+1)), by greedily choosing a vertex and deleting it and its neighbors. Take such a set as the last remaining layer and repeat on the residual graph. Geometric decrease gives

layers. Every vertex has at most 4s neighbors in earlier layers.

For each layer choose a disjoint bin in [n] of size equal to the layer size plus

The bins fit, since their total size is at most n/4+tb\leq n/2. Embed the layers in order. At a given step expose the edges between the current bin and the earlier images, and seek a matching of the layer into its bin. These edges are fresh independent Bernoulli-r variables conditional on the entire past: all previous exposures were between earlier bins.

Write \Delta=\Delta(J). Fix a subset U of the current layer with |U|=u\geq1. Each vertex of U requires adjacency to at most 4s earlier images. Each earlier image occurs in at most \Delta requirements, so the conflict graph joining intersecting requirements has maximum degree at most 4s\Delta. It has an independent set of size at least u/(1+4s\Delta), whose requirements are pairwise disjoint.

For a set W of u-1 vertices in the current bin, at least b vertices of the bin remain outside W. The probability that none is usable for any vertex of U is at most

Indeed, restrict to the disjoint requirements just selected. Each succeeds at a given candidate with probability at least r^{4s}, independently over those requirements and over candidates. If an empty requirement is present, the failure event is impossible, so the bound remains valid.

Uniformly under (3.3) and (4.1), for sufficiently large n,

Here b\geq c'n/(\log n)^2 and r^{4s}\geq n^{-4/100}. There are at most n^{2u} choices of U,W for each u. Failure of Hall’s condition implies such a pair with all usable images of U in W. By (4.2)–(4.3), the conditional failure probability at a layer is at most

Summing this bound over the O((\log n)^2) layers shows that the embedding succeeds with probability tending to one, uniformly over the allowed parameters. Taking an absolute N_2 so that it succeeds with probability at least 1/2 proves the proposition.□

Proof. The edgeless case is immediate. Put q_J=q(J;n)>0. If q_J\geq1/(2A), then 2Aq_J\geq1, so (4.4) is automatic. We may therefore assume q_J<1/(2A) and set p=Aq_J\in(0,1/2).

For \ell\geq1, let m_\ell be the number of components of J with exactly \ell leaves, ignoring isolated vertices. If m=m_\ell>0, the copies on [n] of m disjoint \ell-edge stars cover \calF_J. Their number is at most

This follows by counting vertex injections and dividing by permutations of the leaves and of the stars. For \ell=1 there are additional automorphisms, which only decrease the actual count. Since such a star forest exists on at most n vertices, C_\ell\geq1. Using its cover at (1/(2C_\ell))^{1/(m\ell)}\in(0,1) yields

The last step uses m!\geq(m/e)^m and 2^{1/m}\leq2.

Partition [n] into a center bin of size \lfloor n/2\rfloor and a leaf bin containing the remaining vertices. Process the components of J one at a time. For a star with \ell leaves, test unused centers successively until one has at least \ell neighbors among the unused leaf vertices. Use that center and any \ell such neighbors, and never test that center again. Failed centers are also discarded.

Throughout the process, at least b'=\lfloor n/3\rfloor leaf vertices remain. The unused leaf set is determined by previously tested center rows, and a fresh center row has not been exposed. Thus each trial, conditional on the past, has success probability at least

For the purpose of counting trials, append infinitely many auxiliary centers with fresh independent rows to the same leaf bin. This enlarged process agrees with the actual process until the original center bin is exhausted. The number T of trials needed to finish all stars in the enlarged process satisfies

because the conditional expected waiting time for each success is at most 1/u_\ell.

If \mu=b'p\geq2\ell, the second-moment bound \E[\Bin(b',p)^2]\leq\mu^2+\mu and the Paley–Zygmund inequality give

since \mu\geq2. Otherwise b'p<2\ell. For every occupied star size, \ell\leq n/100, and for large n, b'-\ell+1\geq n/4. As p<1/2, the inequality \log(1-p)\geq-2p implies

where the last inequality uses (4.5).

There are at most n/200 nontrivial components. Combining the two bounds in (4.7) gives

For large n, Markov’s inequality shows that T\leq\lfloor n/2\rfloor with probability at least 1/2. On this event all centers used belong to the actual random graph, so the construction embeds J in G(n,p). This proves p_c(J;n)\leq Aq_J in the remaining case.□

Proof of Theorem 1.1. Fix

Choose an absolute integer n_0\geq2 large enough for Propositions 3.2, 4.1, and 4.2, and so that, for every n\geq n_0,

All these conditions have absolute cutoffs. Set

If H is edgeless, use only empty pieces. Otherwise write q=q(H;n)>0 and d=\degen(H)\geq1. When n<n_0, Lemma 2.3 gives Lq\geq n_0^2/(n(n-1))\geq1. When q\geq1/(2A), we also have Lq\geq1. In either case put all edges in one piece and use empty pieces for the rest. Henceforth

Large degeneracy: d\geq M. Set

By Lemma 2.3, r\geq n^{-2/d}, whereas (5.3) gives r<1/A<1/2. Consequently

These bounds also give s\leq10\log n, so (3.3) holds.

Take the family \calD from Proposition 3.2. Corollary 2.2 supplies a copy of H covered by K_0 members G_1,\ldots,G_{K_0} of \calD. Fix those graphs and the labelled copy, and use this copy to label H on a subset of [n]. Assign each edge of H to one G_i containing it. This gives K_0 initial edge pieces, each contained in its specified typical graph.

We separate the high-degree vertices, following the obstacle identified in [1, Section 8]. Initially let

By (2.2), |Y_0|\leq2d\sqrt n. Starting from Y_0, add an outside vertex whenever it has more than 2d neighbors in the current set, and stop when no such vertex remains. Let Y be the resulting set and let a=|Y\setminus Y_0|. Each added vertex contributes more than 2d edges to earlier vertices of the set; no edge is counted twice. Thus

giving |Y|\leq2|Y_0|\leq4d\sqrt n\leq n^{2/3} by (5.4) and (5.2). The conclusion also holds if Y_0 is empty, in which case no vertex is added. At termination every w\notin Y satisfies

Partition V(H)\setminus Y into B possibly empty blocks of size at most \lceil n/B\rceil. Subdivide each initial edge piece as follows.

Edges inside Y. Apply Lemma 2.4 with m=M to obtain M pieces of degeneracy at most \lceil d/M\rceil\leq s. Each is supported on at most |Y|\leq n^{2/3}\leq n/4 vertices and has maximum degree at most n^{2/3}. Proposition 4.1 gives threshold at most r.

Edges outside Y. First partition by the unordered pair of endpoint blocks, allowing both endpoints in the same block. There are B(B+1)/2 such pairs. Apply Lemma 2.4 with m=M to each resulting graph. The pieces have degeneracy at most s, maximum degree at most \sqrt n, and support size at most 2\lceil n/B\rceil\leq n/100. Proposition 4.1 again gives threshold at most r.

Edges between Y and its complement. First partition by the block of the endpoint outside Y. At each such endpoint, distribute its edges in the initial piece among M groups of size at most \lceil2d/M\rceil=s, using (5.5). This assigns every cut edge once. Each resulting bipartite piece is still contained in its specified G_i\in\calD, has at most \lceil n/B\rceil\leq n/8 positive-degree vertices outside Y, and has all those degrees at most s. Proposition 3.2 gives threshold at most r_*\leq32r=64q.

All pieces therefore have threshold at most 64q\leq Lq. Their number is at most

Bounded degeneracy: 1\leq d<M. Lemma 2.4, with m=d, partitions E(H) into d graphs of degeneracy at most one, hence into forests. Indeed, the last vertex of a cycle in the certifying order would have two preceding neighbors.

Root every nontrivial tree. Color each parent–child edge by the parity of the depth of its parent. Each color class is a star forest: its centers occur at one depth parity, and their children have the other parity and no other incident edge of that color. This is the parity splitting used in [1, Claim 6.2].

Partition V(H) into B blocks of size at most \lceil n/B\rceil, and split each star forest by unordered endpoint-block pairs. Every resulting piece J remains a star forest and has |V_+(J)|\leq2\lceil n/B\rceil\leq n/100. By Proposition 4.2 and (2.1),

The number of pieces is at most 2d\,B(B+1)/2=dB(B+1)\leq k.

Finally, add empty pieces if necessary. In the large-degeneracy case, pull the labelled edge pieces back to the original H. The typical graphs, the copy of H, all vertex orders, and all assignments have been fixed using only H,n; none depends on the random host used to test a piece’s threshold. This completes the proof.□