Back to Search
Start Over
Conflict‐free hypergraph matchings.
- Source :
-
Journal of the London Mathematical Society . May2024, Vol. 109 Issue 5, p1-78. 78p. - Publication Year :
- 2024
-
Abstract
- A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]
- Subjects :
- *HYPERGRAPHS
*STEINER systems
*GREEDY algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 00246107
- Volume :
- 109
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Journal of the London Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 177146634
- Full Text :
- https://doi.org/10.1112/jlms.12899