***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Speaker: Stefan Glock (ETH Zurich)

Thursday 14th April, 3:00 via Zoom. The link is
https://princeton.zoom.us/j/95287578008.


Title: Hypergraph matchings with(out) conflicts

Abstract:
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.


		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)