Conflict-free hypergraph matchings

Abstract

A celebrated theorem of Pippenger, and Frankl and R & ouml;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 subset of E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M subset of 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'.