Conflict-free hypergraph matchings and coverings
Recent work showing the existence of conflict-free almost-perfect hypergraph matchings has found many applications. We show that, assuming certain simple degree and codegree conditions on the hypergraph H \mathcal{H} and the conflicts to be avoided, a conflict-free almost-perfect matching can be ext...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
March 2026
|
| In: |
Combinatorics, probability & computing
Year: 2026, Volume: 35, Issue: 2, Pages: 230-254 |
| ISSN: | 1469-2163 |
| DOI: | 10.1017/S0963548325100291 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1017/S0963548325100291 Verlag, lizenzpflichtig, Volltext: https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/conflictfree-hypergraph-matchings-and-coverings/40E8318628BA6C937FD4AA46CC8A7595 
|
| Author Notes: | Felix Joos, Dhruv Mubayi and Zak Smith |
| Summary: | Recent work showing the existence of conflict-free almost-perfect hypergraph matchings has found many applications. We show that, assuming certain simple degree and codegree conditions on the hypergraph H \mathcal{H} and the conflicts to be avoided, a conflict-free almost-perfect matching can be extended to one covering all vertices in a particular subset of V(H) V(\mathcal{H}), by using an additional set of edges; in particular, we ensure that our matching avoids all additional conflicts, which may consist of both old and new edges. This setup is useful for various applications in design theory and Ramsey theory. For example, our main result provides a crucial tool in the recent proof of the high-girth existence conjecture due to Delcourt and Postle. It also provides a black box which encapsulates many long and tedious calculations, greatly simplifying the proofs of results in generalised Ramsey theory. |
|---|---|
| Item Description: | Zuerst online veröffentlicht: 4. Dezember 2025 Gesehen am 25.02.2026 |
| Physical Description: | Online Resource |
| ISSN: | 1469-2163 |
| DOI: | 10.1017/S0963548325100291 |