Random embeddings of bounded-degree trees with optimal spread
Paul Bastide (Labri, TU Delft - Discrete Mathematics and Optimization)
Clément Legrand-Duchesne (Jagiellonian University)
Alp Müyesser (New College, Oxford)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
A seminal result of Komlós, Sárközy, and Szemerédi states that any n-vertex graph G with minimum degree at least (1/2+α)n contains every n-vertex tree T of bounded degree. Recently, Pham, Sah, Sawhney, and Simkin extended this result to show that such graphs G in fact support an optimally spread distribution on copies of a given T, which implies, using the recent breakthroughs on the Kahn-Kalai conjecture, the robustness result that T is a subgraph of sparse random subgraphs of G 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 G has linear minimum degree, almost all constant-sized subgraphs of G inherit the same minimum degree condition that G has.
help_outline