Random embeddings of bounded-degree trees with optimal spread

Journal article

A seminal result of Komlós, Sárközy, and Szemerédi states that any -vertex graph with minimum degree at least contains every -vertex tree of bounded degree. Recently, Pham, Sah, Sawhney, and Simkin extended this result to show that such graphs in fact support an optimally spread distribution on copies of a given , which implies, using the recent breakthroughs on the Kahn-Kalai conjecture, the robustness result that is a subgraph of sparse random subgraphs of as well. Pham, Sah, Sawhney, and Simkin construct their optimally spread distribution by following closely the original proof of the Komlós-Sárközy-Szemerédi theorem which uses the blow-up lemma and the Szemerédi regularity lemma. We give an alternative, regularity-free construction that instead uses the Komlós-Sárközy-Szemerédi theorem (which has a regularity-free proof due to Kathapurkar and Montgomery) as a black box. Our proof is based on the simple and general insight that, if has linear minimum degree, almost all constant-sized subgraphs of inherit the same minimum degree condition that has.

Authors: Bastide, P; Legrand-Duchesne, C; Müyesser, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics, Probability and Computing
• Pages: 1-12
• Publication date: 2025-10-13
• Acceptance date: 2025-09-05
• DOI: 10.1017/s0963548325100217
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English
• Keywords: 05C80; Dirac’s theorem; spread distributions; Tree embedding; 05D40