Graph Decompositions at the Expectation Threshold
Abstract
For n≥3 and a graph H on at most n vertices, let q(H) be the expectation threshold for its containment in G(n,p). We prove that there are absolute constants a,L>0 such that, for every C>0, every graph of degeneracy at most Clog n/loglog n has a deterministic edge decomposition into at most ⌈ a(C+1)⌉ pieces, each with ordinary containment threshold at most Lq(H). This removes the maximum-degree hypothesis from a theorem of Ascoli, He, Park, and Talagrand in their approach to Talagrand's discrete convexity problem. With constants depending on the fixed parameters, a structural extension allows the addition of O(log n) vertices with arbitrary incident edges. The uniform main bound also gives an O(1+loglog n)-piece decomposition for every target graph, with an absolute threshold multiplier. The main ingredient converts Li's two-set coupling for spread measures into a partition of a prescribed neighborhood list, fixed before the random host is sampled. It allows arbitrary overlaps and repetitions and controls all Hall matching conditions simultaneously by bounding target demand and host supply through common two-sided approximations under the biased host measure.
Related
- A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- The threshold for fractional clique decompositions of random hypergraphs, via matrix scaling
- Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing
- A dimension-free comparison between expectation thresholds and fractional expectation thresholds
BibTeX
@misc{yang2026graph,
title = {{Graph Decompositions at the Expectation Threshold}},
author = {Jia-Qi Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20864},
eprint = {2609.20864},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20864},
}
RIS
TY - UNPB
TI - Graph Decompositions at the Expectation Threshold
AU - Jia-Qi Yang
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.20864
UR - https://arxiv.org/abs/2609.20864
AB - For n≥3 and a graph H on at most n vertices, let q(H) be the expectation threshold for its containment in G(n,p). We prove that there are absolute constants a,L>0 such that, for every C>0, every graph of degeneracy at most Clog n/loglog n has a deterministic edge decomposition into at most ⌈ a(C+1)⌉ pieces, each with ordinary containment threshold at most Lq(H). This removes the maximum-degree hypothesis from a theorem of Ascoli, He, Park, and Talagrand in their approach to Talagrand's discrete convexity problem. With constants depending on the fixed parameters, a structural extension allows the addition of O(log n) vertices with arbitrary incident edges. The uniform main bound also gives an O(1+loglog n)-piece decomposition for every target graph, with an absolute threshold multiplier. The main ingredient converts Li's two-set coupling for spread measures into a partition of a prescribed neighborhood list, fixed before the random host is sampled. It allows arbitrary overlaps and repetitions and controls all Hall matching conditions simultaneously by bounding target demand and host supply through common two-sided approximations under the biased host measure.
ER -