Author name cluster
Marcus Kühn
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
Possible papers
2SODA Conference 2023 Conference Paper
Conflict-free hypergraph matchings
- Stefan Glock
- Felix Joos
- Jaehoon Kim
- Marcus Kühn
- Lyuben Lichev
A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost-regular, uniform hypergraph 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 of subsets C ⊆ E ( H ). We say that a matching M ⊆ E ( H ) is conflict-free if M does not contain an element of C as a subset. Under natural assumptions on C, we prove that 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 polynomial time random greedy algorithm which we call the “conflict-free matching process”. * The full version of the paper can be accessed at https: //arxiv. org/abs/2205. 05564