Robustness of the Sauer–Spencer Theorem

Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa, Mihir Neve · 2025

Read Robustness of the Sauer–Spencer Theorem by Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa, Mihir Neve (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03676.txt.

Introduction

Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa, and Mihir Neve prove a hardier version of a classic graph embedding theorem, in this 2025 arXiv paper. The Sauer-Spencer theorem says a dense enough host graph swallows any guest graph of bounded degree. The new result asks whether a randomly thinned host, keeping each edge with some small chance, still contains the guest.

Above a probability threshold their answer is yes, and the threshold is best possible apart from a log factor. They also soften the host's degree demand to a new boundary value, which they bound and guess exactly, tying it to a famous open conjecture. A sharpened blow-up lemma, proved along the way, may serve other problems, the authors note.

Catalog record

CREATORPeter Allen, Julia Böttcher, Yoshiharu Kohayakawa, Mihir Neve
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03676

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Robustness of the Sauer–Spencer Theorem Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa, Mihir Neve Abstract We prove a robust version of a graph embedding theorem of Sauer and Spencer. To state this sparser analogue, we define G ⁡ ( p ) G(p) to be a random subgraph of G G obtained by retaining each edge of G G independently with probability p ∈ [ 0 , 1 ] p\in[0,1] , and let m 1 ​ ( H ) m_{1}(H) be the maximum 1 1 -density of a graph H H . We show that for any constant Δ \Delta and γ > 0 \gamma>0 , if G G is an n n -vertex host graph with minimum degree δ ⁡ ( G ) ≥ ( 1 − 1 / 2 ​ Δ + γ ) ​ n \delta(G)\geq(1-1/2\Delta+\gamma)n and H H is an n n -vertex graph with maximum degree Δ ⁡ ( H ) ≤ Δ \Delta(H)\leq\Delta , then for p ≥ C n − 1 / m 1 ( H ) log n p\geq Cn^{-1/m_{1}(H)}\log n , the random subgraph G ⁡ ( p ) G(p) contains a copy of H H with high probability. Our value for p p is optimal up to a log \log -factor. In fact, we prove this result for a more general minimum degree condition on G G , by introducing an extension threshold δ e ​ ( Δ ) \delta_{\rm e}(\Delta) , such that the above result holds for graphs G G with δ ⁡ ( G ) ≥ ( δ e ​ ( Δ ) + γ ) ​ n {\delta(G)\geq(\delta_{\rm e}(\Delta)+\gamma)n} . We show that δ e ​ ( Δ ) ≤ ( 2 ​ Δ − 1 ) / 2 ​ Δ \delta_{\rm e}(\Delta)\leq(2\Delta-1)/2\Delta , and further conjecture that δ e ​ ( Δ ) \delta_{\rm e}(\Delta) equals Δ / ( Δ + 1 ) \Delta/(\Delta+1) , which matches the minimum degree condition on G G in the Bollobás–Eldridge–Catlin Conjecture. A main tool in our proof is a vertex-spread version of the blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person, which we believe to be of independent interest. 1 Introduction Many of the most fundamental problems in graph theory can be phrased as embedding problems. A graph H is said to have an embedding into a host graph G if there exists an injective map from V(H) to V(G) which maps every edge of H to some edge in G . For such problems, one is usually interested in finding sufficiency conditions on the host graph, such as bounds on its minimum degree, that allow for embedding a given family of graphs. A prominent result of this flavour is Dirac’s theorem [ 14 ] , which states that any graph on n\geq 3 vertices with minimum degree at least n/2 contains a Hamilton cycle. Moving to other spanning subgraphs, Bollobás in 1978 [ 8 ] conjectured that if G is an n -vertex graph with minimum degree at least (1/2+\varepsilon)n , then G contains any spanning tree of bounded constant degree \Delta for any \varepsilon>0 and n\geq n_{0}(\varepsilon) . This was shown to be true by Komlós, Sárközy, and Szemerédi in 1995 [ 24 ] . In fact, they later improved their result to show that it is possible to find any spanning tree of degree \mathcal{O}(n/\!\log n) under a similar minimum degree condition [ 28 ] . Such embedding results have been studied for a variety of other families of subgraphs, such as clique-factors [ 16 ] , F -factors [ 27 ] , powers of Hamilton cycles [ 26 ] , and for subgraphs with bounded degree and sublinear bandwidth [ 10 ] . A common link in all these embedding theorems is that the subgraphs have sublinear bandwidth. However, the question of which minimum degree enforces the appearance of all spanning subgraphs of a given maximum degree still remains open. Observe that this class of graphs also contains expanders, which do not have sublinear bandwidth. Bollobás, Eldridge, and Catlin [ 7 , 11 ] made the following conjecture. 1 1 1 This conjecture still remains open: Kun announced a proof of the conjecture for sufficiently large n in 2009, but so far no manuscript has appeared. Conjecture 1.1 (Bollobás–Eldridge–Catlin Conjecture) . Let \Delta be a positive integer. Suppose G is an n -vertex graph with minimum degree \delta(G)\geq\tfrac{\Delta}{\Delta+1}n and H is an n -vertex graph with maximum degree \Delta(H)\leq\Delta . Then H is a spanning subgraph of G . This conjecture is known to be tight, as is shown by a slightly unbalanced complete (\Delta+1) -partite graph, which does not contain a K_{\Delta+1} -factor. There have been several partial results towards the resolution of this conjecture. For instance, this conjecture is known to be true for \Delta\leq 2 [ 1 , 5 ] ; for the case where \Delta=3 and n is large [ 13 ] ; and when H is a bipartite graph [ 12 ] . In a major improvement, Kaul, Kostochka, and Yu [ 21 ] showed that if the graph H had a large maximum degree, then it can be embedded into a graph G having minimum degree \delta(G)\geq(1-3/5(\Delta+1))n . To this date, however, the best known bound on the minimum degree that enforces all spanning subgraphs with maximum degree \Delta is given by the following old and well-known theorem of Sauer and Spencer [ 33 ] . Theorem 1.2 (Sauer–Spencer Theorem) . Let \Delta>0 be given. Suppose that G is an n -vertex graph with minimum degree \delta(G)\geq\frac{2\Delta-1}{2\Delta}n and H is an n -vertex graph with maximum degree \Delta(H)\leq\Delta . Then H is a spanning subgraph of G . In general, embedding theorems such as the ones mentioned so far allow for embedding subgraphs into dense graphs, that is, graph having \Theta(n^{2}) edges. A popular line of research in the past few decades has been to establish sparse analogues of such results. Roughly, the idea is to use the high minimum degree host graph from a Dirac-type embedding theorem as a template and ask whether a sparse spanning subgraph of this host graph will inherit its subgraph embedding properties. This is captured by the notion of robustness, which was proposed by Krivelevich, Lee, and Sudakov [ 29 ] in their study of Hamiltonicity. A robustness result examines how strongly a graph satisfies a property. To make this more precise, given a graph G and p\in[0,1] , let G(p) be the random subgraph of G obtained by retaining edges of G independently with probability p . Further, we say that a graph property holds with high probability if the probability of this event tends to 1 as the size of the graph, |G|=n , grows to infinity. Suppose the graph G satisfies some property \Pi . Then this property \Pi is said to hold robustly for G and for some p<1 , if the random subgraph G(p) satisfies the property \Pi with high probability. For instance, Krivelevich, Lee, and Sudakov [ 29 ] proved that Hamiltonicity is robust for Dirac graphs. They showed that if G is an n -vertex graph with minimum degree n/2 and p\geq Cn^{-1}\log n , then

Read the complete text