Resilient forest universality in percolated dense graphs
Abstract
Christoph, Müyesser and Wigderson recently asked whether an approximate form of the Erdős-Sós conjecture is robust under random edge deletions. We establish a density-sensitive transference theorem that converts global resilience for bounded-degree trees in sparse random graphs into resilient forest universality in arbitrary dense host graphs. More precisely, if F is an N-vertex graph of edge density λ bounded away from zero and p∈[K/N,1], then, with probability 1−o(1) uniformly over the host and the percolation parameter, every subgraph obtained from Fp by deleting at most an α-fraction of its edges contains every bounded-degree forest on at most $((1-α)λ-ξ)N$ vertices. Consequently, for every c>0, L≥1, fixed D and α<c, every graph F on at most Ld vertices with average degree at least d has the property that, after percolation at any rate p∈[K/d,1] and any subsequent deletion of at most an α-fraction of the surviving edges, the remaining graph is universal for all forests on at most (1−c)d vertices and maximum degree at most D. This includes vertex-disjoint packings of any prescribed collection of bounded-degree trees of that total order. We further obtain forest-universality results for graphs whose connected components have vertex-cover number at most Cd, and for graphs that can be brought into this form by deleting sufficiently few edges on the dn-scale.
Related
- Translation Universality and Countable Configuration Theory for Dense Gδ-Sets in Polish Abelian Groups
- Edge universality of random regular graphs of growing degrees
- Bulk universality of random regular graphs
- Countable Graphs with Finite Path-width: Characterisation and Universality
- The singularity probability of dense random regular graphs
BibTeX
@misc{mirabi2026resilient,
title = {{Resilient forest universality in percolated dense graphs}},
author = {Mostafa Mirabi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.27927},
eprint = {2609.27927},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27927},
}
RIS
TY - UNPB
TI - Resilient forest universality in percolated dense graphs
AU - Mostafa Mirabi
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2609.27927
UR - https://arxiv.org/abs/2609.27927
AB - Christoph, Müyesser and Wigderson recently asked whether an approximate form of the Erdős-Sós conjecture is robust under random edge deletions. We establish a density-sensitive transference theorem that converts global resilience for bounded-degree trees in sparse random graphs into resilient forest universality in arbitrary dense host graphs. More precisely, if F is an N-vertex graph of edge density λ bounded away from zero and p∈[K/N,1], then, with probability 1−o(1) uniformly over the host and the percolation parameter, every subgraph obtained from F_p by deleting at most an α-fraction of its edges contains every bounded-degree forest on at most $((1-α)λ-ξ)N$ vertices. Consequently, for every c>0, L≥1, fixed D and α<c, every graph F on at most Ld vertices with average degree at least d has the property that, after percolation at any rate p∈[K/d,1] and any subsequent deletion of at most an α-fraction of the surviving edges, the remaining graph is universal for all forests on at most (1−c)d vertices and maximum degree at most D. This includes vertex-disjoint packings of any prescribed collection of bounded-degree trees of that total order. We further obtain forest-universality results for graphs whose connected components have vertex-cover number at most Cd, and for graphs that can be brought into this form by deleting sufficiently few edges on the dn-scale.
ER -