Nearly optimal packings of equally sized rainbow forests
Abstract
A forest in an edge-colored graph is rainbow if its edges have pairwise distinct colors. We prove that for every ε>0 and all sufficiently large integers m, every properly edge-colored simple graph with km edges, where 1≤ k≤ 2m and every color class has size at most m, contains at least (1−ε)m pairwise edge-disjoint rainbow forests, each with exactly k edges. The range k≤ 2m is best possible: for every k>2m there are such graphs containing no k-edge forest. Thus the conjecture of Montgomery, Pokrovskiy, and Sudakov fails beyond this range, while our theorem establishes its predicted conclusion throughout the largest possible range of k. The number of forests is asymptotically optimal. The proof uses an orientation dichotomy, hypergraph matching, matroid intersection, and martingale concentration.
Related
- Optimal Extensions of Cross-Sections: Sphere Packings in Dimensions 38 to 43
- Nearly optimal Kolmogorov widths under holomorphic mappings
- Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback
- Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics
- Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
BibTeX
@misc{xu2026nearly,
title = {{Nearly optimal packings of equally sized rainbow forests}},
author = {Boyan Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.29351},
eprint = {2609.29351},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29351},
}
RIS
TY - UNPB
TI - Nearly optimal packings of equally sized rainbow forests
AU - Boyan Xu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.29351
UR - https://arxiv.org/abs/2609.29351
AB - A forest in an edge-colored graph is rainbow if its edges have pairwise distinct colors. We prove that for every ε>0 and all sufficiently large integers m, every properly edge-colored simple graph with km edges, where 1≤ k≤ 2m and every color class has size at most m, contains at least (1−ε)m pairwise edge-disjoint rainbow forests, each with exactly k edges. The range k≤ 2m is best possible: for every k>2m there are such graphs containing no k-edge forest. Thus the conjecture of Montgomery, Pokrovskiy, and Sudakov fails beyond this range, while our theorem establishes its predicted conclusion throughout the largest possible range of k. The number of forests is asymptotically optimal. The proof uses an orientation dichotomy, hypergraph matching, matroid intersection, and martingale concentration.
ER -