Defect and transference versions of the Alon–Frankl–Lovász theorem

Journal article

Confirming a conjecture of Erdős on the chromatic number of Kneser hypergraphs, Alon, Frankl and Lovász proved that in any -colouring of the edges of the complete -uniform hypergraph, there exists a monochromatic matching of size . In this paper, we prove a transference version of this theorem. More precisely, for fixed and , we show that with high probability, a monochromatic matching of approximately the same size exists in any -colouring of a random hypergraph, already when the average degree is a sufficiently large constant. In fact, our main new result is a defect version of the Alon–Frankl–Lovász theorem for almost complete hypergraphs. From this, the transference version is obtained via a variant of the weak hypergraph regularity lemma. The proof of the defect version uses tools from extremal set theory developed in the study of the Erdős matching conjecture.

Authors: Gishboliner, L; Glock, S; Michaeli, P; Sgueglia, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Cambridge University Press
• Journal: Combinatorics, Probability and Computing
• Pages: 1-12
• Publication date: 2026-03-27
• Acceptance date: 2026-02-18
• DOI: 10.1017/s0963548326100431
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English
• Keywords: Transference and defect versions; 05C70; 05C65; 05C80; Matchings; 05D15; Alon–Frankl–Lovász Theorem