Exact positive codegree thresholds for perfect matching.

Abstract: Rödl, Ruciński and Szemerédi found best-possible codegree conditions that force the existence of perfect matchings in $k$-graphs. Given that the codegree is too strong for many applications, we study this question for a weaker, but more versatile degree condition, which maintains the codegree’s constructive power: the positive codegree. For a $k$-graph, this corresponds to the minimum degree over all sets of size $k-1$ with degree at least one.

For $k\geq 3$ , we show exact minimum positive codegree conditions for the existence of perfect matchings in $k$-graphs with no isolated vertices. Our threshold is best possible and improves a previous result by Halfpap and Magnan.

Posted on Apr 13, 2026 in Seminario de Grafos, Seminars