Defect and transference versions of the Alon-Frankl-Lovasz theorem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908844196626432 |
|---|---|
| author | Gishboliner, Lior Glock, Stefan Michaeli, Peleg Sgueglia, Amedeo |
| author_facet | Gishboliner, Lior Glock, Stefan Michaeli, Peleg Sgueglia, Amedeo |
| contents | Confirming a conjecture of Erdős on the chromatic number of Kneser hypergraphs, Alon, Frankl and Lovász proved that in any $q$-colouring of the edges of the complete $r$-uniform hypergraph, there exists a monochromatic matching of size $\lfloor \frac{n+q-1}{r+q-1}\rfloor$. In this paper, we prove a transference version of this theorem. More precisely, for fixed $q$ and $r$, we show that with high probability, a monochromatic matching of approximately the same size exists in any $q$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_05089 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Defect and transference versions of the Alon-Frankl-Lovasz theorem Gishboliner, Lior Glock, Stefan Michaeli, Peleg Sgueglia, Amedeo Combinatorics Confirming a conjecture of Erdős on the chromatic number of Kneser hypergraphs, Alon, Frankl and Lovász proved that in any $q$-colouring of the edges of the complete $r$-uniform hypergraph, there exists a monochromatic matching of size $\lfloor \frac{n+q-1}{r+q-1}\rfloor$. In this paper, we prove a transference version of this theorem. More precisely, for fixed $q$ and $r$, we show that with high probability, a monochromatic matching of approximately the same size exists in any $q$-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. |
| title | Defect and transference versions of the Alon-Frankl-Lovasz theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.05089 |