Robustness of the Sauer-Spencer Theorem

Julia B\"ottcher; Mihir Neve; Peter Allen; Yoshiharu Kohayakawa

REVIEW 2 major objections 5 minor 36 references

Robustness of the Sauer-Spencer Theorem

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that the Sauer–Spencer embedding theorem remains true after random sparsification: for hosts meeting the Sauer–Spencer minimum-degree condition, keeping each edge with probability $p \ge C n^{-1/m_1(H)} \log n$ still…

desk verdict Robust Sauer-Spencer for all bounded-degree spanning subgraphs, with a genuinely new spread blow-up lemma—but the load-bearing constants live in an earlier arXiv preprint. read the letter →

arxiv 2507.03676 v1 pith:LPL7ASNE submitted 2025-07-04 math.CO

Peter Allen , Julia Böttcher , Yoshiharu Kohayakawa , Mihir Neve This is my paper

classification math.CO MSC 05C8005C3505C7005D40

keywords robustgraphembeddingSauer–Spencertheoremrandomsubgraphsspreadmeasuresvertex-spreadmeasureblow-uplemmaminimumdegreebounded-degreespanning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a robust version of the Sauer–Spencer graph embedding theorem. If a host graph $G$ on $n$ vertices has minimum degree at least $(\delta_{\rm e}(\Delta)+\gamma)n$, where $\delta_{\rm e}(\Delta) \le (2\Delta-1)/(2\Delta)$, and $H$ is an $n$-vertex graph of maximum degree at most $\Delta$, then the random subgraph $G(p)$ obtained by keeping each edge independently with probability $p \ge C n^{-1/m_1(H)} \log n$ contains a copy of $H$ with high probability. Here $m_1(H)$ is the maximum 1-density of $H$, namely $\max_{H' \subseteq H} e(H')/(v(H')-1)$. The probability range is optimal up to a logarithmic factor. The proof introduces an extension threshold $\delta_{\rm e}(\Delta)$, proves the upper bound above, and conjectures $\delta_{\rm e}(\Delta)=\Delta/(\Delta+1)$, which would match the Bollobás–Eldridge–Catlin minimum-degree condition. The technical engine is a new vertex-spread version of the blow-up lemma, which produces an $O(1/n)$-vertex-spread measure on the set of embeddings of $H$ into $G$ and is intended to be useful beyond this paper.

What carries the argument

The central new object is a $q$-vertex-spread probability measure on the set $\mathrm{Emb}(H,G)$ of embeddings: a measure under which any fixed assignment of $k$ distinct vertices of $H$ to distinct vertices of $G$ has probability at most $(C/n)^k$. The theorem that carries the proof is the spread blow-up lemma (Theorem 5.6), which shows that whenever the usual blow-up lemma conditions hold (regular and super-regular partitions, an $R$-partition of $H$, an $(\alpha,R')$-buffer, and image restrictions), such a $(C_S/n)$-vertex-spread measure exists on the embeddings that respect the restrictions. The mechanism inside it is a probabilistic analysis of the random greedy algorithm of the earlier sparse blow-up lemma specialised to $p=1$: the main vertices are embedded one by one uniformly from candidate sets of size $\Theta(n)$, producing the $1/n$ spread factor, and the buffer vertices are then completed by a random perfect matching in an auxiliary bipartite graph whose matching measure is shown to be $O(1/n)$-spread by coupling a binomial random subgraph with a uniformly random subgraph and proving Hall's condition holds with probability at least $1/2$. A second mechanism is the extension threshold $\delta_{\rm e}(\Delta)$, used in Lemma 6.3 to turn an embedding of a small induced subgraph of $H$ into a full size-compatible $R$-partition with buffers, and this is the only place the minimum-degree condition enters.

What would settle it

Run the random greedy algorithm at $p=1$ on a concrete $\varepsilon$-regular partition equipped with a $K_{\Delta+1}$-factor and record the candidate-set size at every step along with the final buffer candidate counts; if any step has fewer than $(1/10)\mu\zeta|V(x)|$ available vertices, or any buffer vertex has fewer than $(1/2)\mu d^b|V_i|$ candidates, then the $O(1/n)$-spread bound of the spread blow-up lemma fails and the probability threshold in Theorem 1.5 would need a different proof.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.5: for all $\gamma>0$ and $\Delta \in \mathbb{N}$ there is a constant $C$ such that whenever $\Delta(H)\le \Delta$ and $\delta(G)\ge(\delta_{\rm e}(\Delta)+\gamma)n$, the random subgraph $G(p)$ contains $H$ with high probability for $p\ge Cn^{-1/m_1(H)}\log n$. Since the paper proves $\delta_{\rm e}(\Delta)\le(2\Delta-1)/(2\Delta)$, Theorem 1.3 follows: the classic Sauer–Spencer minimum-degree condition $\delta(G)\ge((2\Delta-1)/(2\Delta)+\gamma)n$ is enough for the robust statement. The proof path is: extend the Sauer–Spencer switching argument to complete any partial embedding on at most $\eta n$ vertices; use Szemerédi regularity to obtain a reduced graph $R$ with a spanning $K_{\Delta+1}$-factor $R'$; use the extension property to partition $H$ compatibly with $R$ and to set aside buffer vertices; apply the spread blow-up lemma to obtain a $O(1/n)$-vertex-spread measure on embeddings of $H$ into $G$; then convert this to a $O(n^{-1/m_1(H)})$-spread measure on copies of $H$ and invoke the spread-measure threshold theorem to conclude that $G(p)$ contains $H$.

Load-bearing premise

The load-bearing assumption is that the random greedy algorithm used inside the spread blow-up lemma always has a candidate set of size at least a fixed fraction of the part at every step, and that the buffer-vertex candidate counts are as large as the earlier sparse blow-up lemma claims; those bounds are imported without being reproved here.

Editorial extensions

If this is right

The theorem proves that every bounded-degree spanning graph $H$ is embedded in $G(p)$ with high probability once $p \ge C n^{-1/m_1(H)} \log n$, so the Sauer–Spencer property is robust to random edge deletion.
The bound on $p$ is optimal up to a logarithmic factor over the class of bounded-degree graphs with a fixed maximum 1-density, and for graphs with $m_1(H)=(\Delta+1)/2$ (for instance $K_{\Delta+1}$-factors) the improved probability $p\ge C n^{-2/(\Delta+1)}(\log n)^{1/((\Delta+1)/2)}$ is optimal up to a constant.
The spread blow-up lemma gives a $O(1/n)$-vertex-spread measure on all embeddings satisfying the blow-up lemma's conditions, so any embedding problem that fits the blow-up lemma automatically inherits spread information.
If the conjecture $\delta_{\rm e}(\Delta)=\Delta/(\Delta+1)$ holds, the robust embedding theorem and its optimal $p$ would hold at the Bollobás–Eldridge–Catlin minimum-degree threshold, matching the conjectured extremal bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves implicit a counting corollary: a $O(1/n)$-vertex-spread measure supported on $\mathrm{Emb}(H,G)$ forces the number of embeddings of $H$ in a dense host $G$ at degree $\delta_{\rm e}(\Delta)+\gamma$ to be exponentially large, so the copy count jumps discontinuously at this minimum-degree threshold; this could be made quantitative by integrating the spread measure.
Because the spread blow-up lemma works with the entire reduced graph rather than a bounded-size part of it, it should transfer to other robust embedding problems, such as embeddings into perturbed random graphs or into pseudorandom hosts, where the prior spread blow-up lemma was too weak.
A sharper value of $\delta_{\rm e}(\Delta)$ could be located computationally for small $\Delta$ by searching for a host $G$ and a bounded-degree $H$ for which the partial-embedding extension property fails just below $(2\Delta-1)/(2\Delta)n$; the paper's proof shows this extension property is the only place the degree condition enters.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:2507.03676. This is a serious paper. It proves a robust version of the Sauer–Spencer theorem for every bounded-degree spanning subgraph, with edge probability optimal up to a log factor. The new vertex-spread blow-up lemma is the real engine, and it genuinely extends what Nenadov–Pham got, because it works on the whole reduced graph rather than a bounded subgraph.

What is new and good: the extension threshold δe(Δ) is a clean way to separate the degree condition from the embedding argument. Lemma 3.1, the switching proof for extending partial embeddings, is short and self-contained. The spread-measure construction in Section 7 is thoughtful: the RGA gives spread on main vertices, Hall's theorem on buffers, and the product measure ties them together. Theorem 9.2 is a nice extra, getting the sharp threshold (up to constants) for the maximal-density case.

The soft spots are real but not fatal. The load-bearing worry is exactly the one in the stress-test note: Theorem 5.6 imports four RGA invariants—(INV3), (GPE3), (PRGA2), (PRGA3)—from the earlier Allen–Böttcher–Hàn–Kohayakawa–Person preprint [4], with a "rephrased for p=1" and no proof. Since [4] is an arXiv preprint and not published as far as the reference shows, and since the O(1/n)-spread bound depends on the exact constants, a referee has to check a long external proof to certify the main theorem. That is a genuine risk, but on reading, the invariants are plausible and consistent with the rest of the argument. I would call it a vulnerability, not a discovered error. There are also small technical gaps in the union-bound estimates in Lemma 7.4—the Case II calculation has a suspicious exponent—but these look repairable, and the main line is coherent.

Who should read this: anyone working on robust embedding, spread measures, or blow-up lemmas. It will likely become a standard reference. Not a quick read, but a worthwhile one.

Recommendation: send it to peer review. The referee should be someone willing to check the dependence on [4], and if that holds up, this is a strong accept.

Referee Report

2 major / 5 minor

Summary. The paper proves a robust (random-subgraph) version of the Sauer–Spencer embedding theorem. For any Δ and γ>0, if an n-vertex host G has minimum degree at least (δ_e(Δ)+γ)n—in particular at least ((2Δ-1)/(2Δ)+γ)n—and H is an n-vertex graph with maximum degree at most Δ, then the random subgraph G(p) contains a copy of H with high probability for p ≥ C n^{-1/m_1(H)} log n. The proof introduces an extension threshold δ_e(Δ), proves δ_e(Δ) ≤ (2Δ-1)/(2Δ) via a switching argument (Lemma 3.1), and establishes a vertex-spread version of the Allen–Böttcher–Hàn–Kohayakawa–Person blow-up lemma (Theorem 5.6). The spread blow-up lemma is proved by reanalysing the random greedy algorithm and the Hall-type buffer-embedding step of [4], and it is combined with the Frankston–Kahn–Narayanan–Park spread threshold theorem. The paper also proves an improved probability bound for graphs H of maximal 1-density and contains an optimality discussion in Section 9.

Significance. Assuming correctness, this is a substantial advance: it shows that the Sauer–Spencer minimum degree condition is robust at a value of p that is optimal up to a log factor, and it introduces a spread blow-up lemma that applies to the entire reduced graph, which is likely to be useful for further robust embedding problems. The paper is well organised, states explicit constants in the main chain, and the switching proof of Lemma 3.1 is elegant. The reduction to a O(1/n)-vertex-spread measure and the use of the FKNP spreadness theorem are well motivated. The optimality discussion and Theorem 9.2 add value. The main caveat is the heavy dependence of Theorem 5.6 on the external preprint [4] for the random-greedy-algorithm invariants.

major comments (2)

[Section 7, proof of Theorem 5.6] The construction of the (C_S/n)-vertex-spread measure is not self-contained at the decisive step. Lemma 7.1 uses (RGA 1), derived from (INV 3), and Lemma 7.4 uses (FB 1)–(FB 3), derived from (GPE 3), (PRGA 2), and (PRGA 3). These four invariants are imported without proof from [4, Lemma 4.1] and are only stated as 'rephrased for p=1'. Since the O(1/n)-vertex-spread bound—and hence the p = O(n^{-1/m_1(H)} log n) threshold in Theorem 1.5—is exactly as strong as these constants, this dependency is load-bearing. Please either give a self-contained proof of the p=1 case of these invariants, or state the precise lemma from [4] with all quantifiers (including how μ, ζ, ρ depend on the input parameters) and verify explicitly that its hypotheses are satisfied in the dense setting of Theorem 5.6. As [4] is an arXiv preprint, this link is currently the least externally verified part of the chain.
[Section 8.1, Lemma 6.2] The quantifier order in Lemma 6.2 and its use in the proof of Theorem 1.5 needs clarification. Lemma 6.2 is stated 'for all ε>0', but the proof chooses auxiliary constants ε' and d' defined in terms of ε and needs inequalities such as d' ≤ γ/4 and ε' ≤ ε*_0. If ε is not sufficiently small, these inequalities can fail; in particular, d' = 2d + 4ε'Δ + 4Δ√ε' is not bounded by γ/4 for arbitrary ε. In the proof of Theorem 1.5, ε is first returned by Theorem 5.6 and only then fed into Lemma 6.2. Please reorder the quantifiers: either state Lemma 6.2 for all sufficiently small ε, or allow ε to be chosen as small as required before applying Theorem 5.6.

minor comments (5)

[Section 7, definition of C_buf(x)] In the second-step paragraph, the candidate set for a buffer vertex is defined as C_buf(x) = N*_G(φ_m(N_H(x; X_main); V_buf_i), with no intersection with the image restriction I_x. To justify the claim that the final embedding respects the image restrictions in Theorem 5.6, the definition should include ∩ I_x (or the text should clarify that the candidate sets are taken relative to the image restrictions). For the main theorem this issue does not arise because ζ=1 and I_x=V_i, but Theorem 5.6 as stated is affected.
[Section 7, Lemma 7.4, Case II] The displayed union-bound chain in Case II contains an unnecessarily crude intermediate estimate: after bounding each term by (C_2 λ^{-2(C-4)/3})^k, the text writes '≤ Σ_{k≤λ^{1/3}} C_2 λ^{-2/3}', which loses the factor k in the exponent. The final conclusion is correct, but rewriting the sum as a geometric sum would improve clarity.
[Section 6, proof of Theorem 1.5] The reduction performed when H has fewer than n/4 edges should explicitly treat the case E(H)=∅, since m_1(H) is undefined for the empty graph. This case is trivial, but it should be stated for completeness.
[Section 8.2, Step I] The lower bound on |B_0| implicitly uses that n is sufficiently large, so that the equitable Hajnal–Szemerédi partition of eH into Δ^6 parts gives a part of size at least (1-γ/4)n/Δ^6. Please state the required lower bound on n explicitly.
[References] Reference [4] is listed as an arXiv preprint; if a published or revised version exists, the citation should be updated to the version actually used, and the exact location of the invariants (INV 3), (GPE 3), (PRGA 2), and (PRGA 3) should be given more precisely than a single Lemma 4.1 reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof derives the spread blow-up lemma from the authors' earlier independent blow-up lemma [4] rather than assuming the target theorem, and no fitted input is renamed as a prediction.

full rationale

The derivation chain is self-contained and non-circular. Theorem 1.5 is proved by constructing a vertex-spread measure via the spread blow-up lemma (Theorem 5.6), converting it to a spread measure (Theorem 5.5), and applying the Frankston--Kahn--Narayanan--Park threshold theorem (Theorem 5.2). The only imported non-elementary ingredient is the blow-up lemma and its proof invariants from [4], which is a prior independent work by three of the present authors. Although Section 7 relies on the random greedy algorithm invariants (INV3), (GPE3), (PRGA2), and (PRGA3) from [4, Lemma 4.1] without reproof, these are cited as an external proven lemma with stated assumptions that do not include the Sauer--Spencer robustness conclusion; the paper explicitly says its proof 'results from a careful probabilistic analysis of the key steps used in the proof of the sparse blow-up lemma in [4]', i.e. it derives the spread version rather than assuming it. The extension threshold delta_e(Delta) is defined as a property and then bounded above by Lemma 3.1, so Theorem 1.5 is not using its conclusion as an input. No parameter is fitted to data, and no 'prediction' is a renamed input. The self-citation is load-bearing but not circular, because [4] is a separate published result with independent content; under the stated rules this does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claim rests on standard theorems of extremal graph theory and on one internal proof from the authors' earlier paper [4]; no data fitting or invented entities are involved. The extension threshold δ_e(Δ) is a defined real number, and the vertex-spread measure is a probabilistic construction; these are tools and definitions, not entities. All constants are existential, not fitted to data.

assumptions (7)

standard math Szemerédi regularity lemma and its degree form (Theorem 4.1, Corollary 4.1.1)
Used in Lemma 6.2 to construct a reduced graph R with controlled minimum degree and a spanning K_{Δ+1}-factor R'.
standard math Hajnal-Szemerédi theorem and its K_r-factor corollary (Theorem 2.1, Corollary 2.1.1)
Used to partition H into independent sets for buffer selection and to find the K_{Δ+1}-factor in the reduced graph.
domain assumption Blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa and Person [4, Lemma 7.1] (Lemma 4.8)
Black-box embedding theorem with buffer vertices and image restrictions, specialised to p=1.
domain assumption Internal RGA invariants (INV 3), (GPE 3), (PRGA 2), (PRGA 3) from [4, Lemma 4.1]
The spread measure construction in Section 7 relies on these invariants; they are quoted from the authors' earlier paper, not re-proved here.
standard math Frankston-Kahn-Narayanan-Park threshold theorem (Theorem 5.2)
Converts the q-spread measure on copies of H into containment in G(p) with p ≥ K q log ℓ(F).
standard math Pham-Sah-Sawhney-Simkin robust K_{Δ+1}-factor theorem (Theorem 9.4)
Used in the proof of Theorem 9.2 to embed the clique components H1 of H.
standard math Hypergeometric Chernoff bound (Lemma 9.5)
Used in Theorem 9.2 to show a random vertex subset of G retains high minimum degree.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Robustness of the Sauer-Spencer Theorem." pith.science (2026). https://pith.science/paper/LPL7ASNE

@misc{pith2026250703676,
  author       = {Pith},
  title        = {Pith review of: Robustness of the Sauer-Spencer Theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LPL7ASNE}},
  note         = {Machine review of arXiv:2507.03676}
}

abstract

We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define $G(p)$ to be a random subgraph of $G$ obtained by retaining each edge of $G$ independently with probability $p \in [0,1]$, and let $m_1(H)$ be the maximum $1$-density of a graph $H$. We show that for any constant $\Delta$ and $\gamma > 0$, if $G$ is an $n$-vertex host graph with minimum degree $\delta(G) \geq (1 - 1/2\Delta + \gamma)n$ and $H$ is an $n$-vertex graph with maximum degree $\Delta(H) \leq \Delta$, then for $p \geq Cn^{-1/m_1(H)}\log n$, the random subgraph $G(p)$ contains a copy of $H$ with high probability. Our value for $p$ is optimal up to a log-factor. In fact, we prove this result for a more general minimum degree condition on $G$, by introducing an \emph{extension threshold} $\delta_{\rm e}(\Delta)$, such that the above result holds for graphs $G$ with ${\delta(G) \geq (\delta_{\rm e}(\Delta) + \gamma)n}$. We show that $\delta_{\rm e}(\Delta) \leq (2\Delta-1)/2\Delta$, and further conjecture that $\delta_{\rm e}(\Delta)$ equals $\Delta/(\Delta+1)$, which matches the minimum degree condition on $G$ in the Bollob\'as-Eldridge-Catlin Conjecture. A main tool in our proof is a vertex-spread version of the blow-up lemma of Allen, B\"{o}ttcher, H\`{a}n, Kohayakawa, and Person, which we believe to be of independent interest.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

36 extracted references · 32 canonical work pages

[4]

Allen, J

P. Allen, J. B¨ ottcher, H. H` an, Y. Kohayakawa, and Y. Person,Blow-up lemmas for sparse graphs, 2019. arXiv:1612.00622. (Return to page 2, 4, 6, 8, 9, 14, 15, 16)

arXiv 2019
[1]

Aigner and S

M. Aigner and S. Brandt, Embedding arbitrary graphs of maximum degree two , J. London Math. Soc. (2) 48 (1993), no. 1, 39–51. (Return to page 2)

work page 1993
[2]

Allen, J

P. Allen, J. B¨ ottcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, and J. Skokan, A robust Corr´ adi-Hajnal theorem, Random Structures Algorithms 65 (2024), no. 1, 61–130. (Return to page 2)

work page 2024
[3]

Allen, J

P. Allen, J. B¨ ottcher, Y. Kohayakawa, and M. Neve,Local resilience for containment of bounded degree spanning subgraphs, manuscript in preparation. (Return to page 13)

work page
[5]

Alon and E

N. Alon and E. Fischer, 2 -factors in dense graphs , Discrete Math. 152 (1996), no. 1–3, 13–23. (Return to page 2)

work page 1996
[6]

Bastide, C

P. Bastide, C. Legrand-Duchesne, and A. M¨ uyesser,Random embeddings of bounded degree trees with optimal spread , 2024. arXiv:2409.06640. (Return to page 2)

arXiv 2024
[7]

Bollob´ as and S

B. Bollob´ as and S. E. Eldridge,Packings of graphs and applications to computational complexity , J. Combin. Theory Ser. B 25 (1978), no. 2, 105–124. (Return to page 2)

work page 1978
[8]

Bollob´ as,Extremal graph theory, London Mathematical Society Monographs, vol

B. Bollob´ as,Extremal graph theory, London Mathematical Society Monographs, vol. 11, Aca- demic Press, Inc., 1978. (Return to page 1)

work page 1978

Show all 36 references

[9]

B¨ ottcher, M

J. B¨ ottcher, M. Schacht, and A. Taraz,Spanning 3-colourable subgraphs of small bandwidth in dense graphs, J. Combin. Theory Ser. B 98 (2008), no. 4, 752–777. (Return to page 7)

2008
[10]

, Proof of the bandwidth conjecture of Bollob´ as and Koml´ os, Math. Ann. 343 (2009), no. 1, 175–205. (Return to page 1, 20)

2009
[11]

P. A. Catlin, Embedding subgraphs and coloring graphs under extremal degree conditions , Thesis (Ph.D.)–The Ohio State University, 1976. (Return to page 2)

1976
[12]

Csaba, On the Bollob´ as–Eldridge conjecture for bipartite graphs, Combin

B. Csaba, On the Bollob´ as–Eldridge conjecture for bipartite graphs, Combin. Probab. Comput. 16 (2007), no. 5, 661–691. (Return to page 2)

2007
[13]

Csaba, A

B. Csaba, A. Shokoufandeh, and E. Szemer´ edi, Proof of a conjecture of Bollob´ as and Eldridge for graphs of maximum degree three , Combinatorica 23 (2003), no. 1, 35–72, Paul Erd˝ os and his mathematics (Budapest, 1999). (Return to page 2)

2003
[14]

G. A. Dirac, Some theorems on abstract graphs , Proc. London Math. Soc. (3) 2 (1952), 69–81. (Return to page 1)

1952
[15]

Frankston, J

K. Frankston, J. Kahn, B. Narayanan, and J. Park, Thresholds versus fractional expectation- thresholds, Ann. of Math. (2) 194 (2021), no. 2, 475–495. (Return to page 3, 9, 10)

2021
[16]

Hajnal and E

A. Hajnal and E. Szemer´ edi,Proof of a conjecture of P. Erd˝ os, Combinatorial theory and its applications, I-III (Proc. Colloq., Balatonf¨ ured, 1969), Colloq. Math. Soc. J´ anos Bolyai, vol. 4, North-Holland, Amsterdam-London, 1970, pp. 601–623. (Return to page 1, 4) 27

1969
[17]

Janson, T

S. Janson, T. Luczak, and A. Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. (Return to page 26)

2000
[18]

Johansson, J

A. Johansson, J. Kahn, and V. Vu, Factors in random graphs , Random Structures Algorithms 33 (2008), no. 1, 1–28. (Return to page 25)

2008
[19]

F. Joos, R. Lang, and N. Sanhueza-Matamala, Robust hamiltonicity, 2024. arXiv:2312.15262. (Return to page 2)

2024 arXiv
[20]

D. Y. Kang, T. Kelly, D. K¨ uhn, D. Osthus, and V. Pfenninger,Perfect matchings in random sparsifications of Dirac hypergraphs, Combinatorica 44 (2024), no. 6, 1233–1266. (Return to page 2)

2024
[21]

H. Kaul, A. Kostochka, and G. Yu, On a graph packing conjecture by Bollob´ as, Eldridge and Catlin, Combinatorica 28 (2008), no. 4, 469–485. (Return to page 2)

2008
[22]

Kelly, A

T. Kelly, A. M¨ uyesser, and A. Pokrovskiy,Optimal spread for spanning subgraphs of Dirac hypergraphs, J. Combin. Theory Ser. B 169 (2024), 507–541. (Return to page 2, 3, 10, 25)

2024
[23]

Koml´ os and M

J. Koml´ os and M. Simonovits,Szemer´ edi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erd˝ os is eighty (Keszthely, 1993), Bolyai Soc. Math. Stud., vol. 2, J´ anos Bolyai Math. Soc., Budapest, 1996, pp. 295–352. (Return to page 6)

1993
[24]

Koml´ os, G

J. Koml´ os, G. N. S´ ark¨ ozy, and E. Szemer´ edi,Proof of a packing conjecture of Bollob´ as, Combin. Probab. Comput. 4 (1995), no. 3, 241–255. (Return to page 1)

1995
[25]

1, 109–123

, Blow-up lemma , Combinatorica 17 (1997), no. 1, 109–123. (Return to page 4, 7, 8)

1997
[26]

, Proof of the Seymour conjecture for large graphs , Ann. Comb. 2 (1998), no. 1, 43–60. (Return to page 1)

1998
[27]

235 (2001), no

, Proof of the Alon–Yuster conjecture , Discrete Math. 235 (2001), no. 1-3, 255–269, Combinatorics (Prague, 1998). (Return to page 1)

2001
[28]

, Spanning trees in dense graphs , Combin. Probab. Comput. 10 (2001), no. 5, 397–416. (Return to page 1)

2001
[29]

Krivelevich, C

M. Krivelevich, C. Lee, and B. Sudakov, Robust Hamiltonicity of Dirac graphs , Trans. Amer. Math. Soc. 366 (2014), no. 6, 3095–3130. (Return to page 2, 12, 25)

2014
[30]

K¨ uhn, D

D. K¨ uhn, D. Osthus, and A. Taraz,Large planar subgraphs in dense graphs , J. Combin. Theory Ser. B 95 (2005), no. 2, 263–282. (Return to page 7)

2005
[31]

Nenadov and H

R. Nenadov and H. T. Pham, Spread blow-up lemma with an application to perturbed random graphs, 2024. arXiv:2410.06132. (Return to page 3, 4)

2024 arXiv
[32]

H. T. Pham, A. Sah, M. Sawhney, and M. Simkin, A toolkit for robust thresholds , 2023. arXiv:2210.03064v4. (Return to page 2, 3, 10, 17, 25)

2023 arXiv
[33]

Sauer and J

N. Sauer and J. Spencer, Edge disjoint placement of graphs , J. Combin. Theory Ser. B 25 (1978), no. 3, 295–302. (Return to page 2, 5)

1978
[34]

Sudakov, Robustness of graph properties , Surveys in combinatorics 2017, London Math

B. Sudakov, Robustness of graph properties , Surveys in combinatorics 2017, London Math. Soc. Lecture Note Ser., vol. 440, Cambridge Univ. Press, Cambridge, 2017, pp. 372–408. (Return to page 2)

2017
[35]

Szemer´ edi,Regular partitions of graphs , Probl` emes combinatoires et th´ eorie des graphes (Colloq

E. Szemer´ edi,Regular partitions of graphs , Probl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401. (Return to page 6)

1976
[36]

Talagrand, Are many small sets explicitly small? , Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp

M. Talagrand, Are many small sets explicitly small? , Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, 2010, pp. 13–35. (Return to page 3, 9) 28

2010

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [4]

Allen, J

P. Allen, J. B¨ ottcher, H. H` an, Y. Kohayakawa, and Y. Person,Blow-up lemmas for sparse graphs, 2019. arXiv:1612.00622. (Return to page 2, 4, 6, 8, 9, 14, 15, 16)

arXiv 2019

[2] [1]

Aigner and S

M. Aigner and S. Brandt, Embedding arbitrary graphs of maximum degree two , J. London Math. Soc. (2) 48 (1993), no. 1, 39–51. (Return to page 2)

work page 1993

[3] [2]

Allen, J

P. Allen, J. B¨ ottcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, and J. Skokan, A robust Corr´ adi-Hajnal theorem, Random Structures Algorithms 65 (2024), no. 1, 61–130. (Return to page 2)

work page 2024

[4] [3]

Allen, J

P. Allen, J. B¨ ottcher, Y. Kohayakawa, and M. Neve,Local resilience for containment of bounded degree spanning subgraphs, manuscript in preparation. (Return to page 13)

work page

[5] [5]

Alon and E

N. Alon and E. Fischer, 2 -factors in dense graphs , Discrete Math. 152 (1996), no. 1–3, 13–23. (Return to page 2)

work page 1996

[6] [6]

Bastide, C

P. Bastide, C. Legrand-Duchesne, and A. M¨ uyesser,Random embeddings of bounded degree trees with optimal spread , 2024. arXiv:2409.06640. (Return to page 2)

arXiv 2024

[7] [7]

Bollob´ as and S

B. Bollob´ as and S. E. Eldridge,Packings of graphs and applications to computational complexity , J. Combin. Theory Ser. B 25 (1978), no. 2, 105–124. (Return to page 2)

work page 1978

[8] [8]

Bollob´ as,Extremal graph theory, London Mathematical Society Monographs, vol

B. Bollob´ as,Extremal graph theory, London Mathematical Society Monographs, vol. 11, Aca- demic Press, Inc., 1978. (Return to page 1)

work page 1978