Stability and exact extremal colourings for the Alon--Frankl--Lovász bound
Abstract
The Alon--Frankl--Lovász theorem states that every q-colouring of the edges of the complete r-uniform hypergraph on n vertices contains a monochromatic matching of size ⌊(n+q−1)/(r+q−1)⌋. For fixed uniformity r and number of colours q, we prove a stability theorem: every colouring whose largest monochromatic matching has size at most n/(r+q−1)+o(n) differs from a threshold extremal colouring on only o(nr) edges. We also give a necessary and sufficient structural characterization of all extremal colourings for sufficiently large n. The proofs combine rigidity of fractional covering weights with an extension argument for prescribed matchings. These results answer, for sufficiently large orders, the stability and extremal-colouring questions posed by Gishboliner, Glock, Michaeli and Sgueglia.
Related
- Exact majority C-colourings of balanced Hamming graphs and grids
- Structure of large t-intersecting families I: Stability for the Hilton--Milner--Frankl theorem
- Extremal Sasaki manifolds and weighted K-stability
- Zero-damped modes of near-extremal Reissner--Nordström black holes from exact WKB
- Super-g-Hölder Regularity in Stieltjes Dynamics: Atomic Structure, Exact Extremal Values, and Recovery of the Stieltjes Clock
BibTeX
@misc{kan2026stability,
title = {{Stability and exact extremal colourings for the Alon--Frankl--Lovász bound}},
author = {Tianhong Kan and Hongliang Lu and Feihong Yuan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02885},
eprint = {2611.02885},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02885},
note = {CC0},
}
RIS
TY - UNPB
TI - Stability and exact extremal colourings for the Alon--Frankl--Lovász bound
AU - Tianhong Kan
AU - Hongliang Lu
AU - Feihong Yuan
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02885
UR - https://arxiv.org/abs/2611.02885
AB - The Alon--Frankl--Lovász theorem states that every q-colouring of the edges of the complete r-uniform hypergraph on n vertices contains a monochromatic matching of size ⌊(n+q−1)/(r+q−1)⌋. For fixed uniformity r and number of colours q, we prove a stability theorem: every colouring whose largest monochromatic matching has size at most n/(r+q−1)+o(n) differs from a threshold extremal colouring on only o(n^r) edges. We also give a necessary and sufficient structural characterization of all extremal colourings for sufficiently large n. The proofs combine rigidity of fractional covering weights with an extension argument for prescribed matchings. These results answer, for sufficiently large orders, the stability and extremal-colouring questions posed by Gishboliner, Glock, Michaeli and Sgueglia.
ER -