Online Talk 

A celebrated theorem of Pippenger, and Frankl and Rödl, states that every regular hypergraph with small codegrees has an almost-perfect matching. We develop an extension of this that takes `conflicts' into account, where conflicts are encoded via a collection of subsets of edges. We say that a matching is conflict-free if no element of the given collection is a subset of the matching. Under natural assumptions on the given collection of conflicts, we prove that a conflict-free almost-perfect matching exists. 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'. In the talk, I will motivate this concept of conflict-free matchings by illustrating that several earlier results, seemingly unrelated, can be derived from it, as well as presenting some new applications. I will explain how the algorithm works and sketch how to analyze it.

This is joint work with Felix Joos, Jaehoon Kim, Marcus Kühn and Lyuben Lichev.