Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This note explores the generalization of Dirac's theorem for perfect matchings in graphs to hypergraphs, connecting fractional perfect matchings with a probabilistic inequality for nonnegative random variables. It presents a concise, self-contained proof of Feige's conjecture, which establishes a lower bound on the minimum degree required for a hypergraph to guarantee a perfect matching. The work aims to provide an accessible classroom resource on this topic.
A hypergraph's minimum degree dictates its perfect matching existence, with a novel proof connecting fractional matchings to a key probabilistic inequality.
How large of a minimum degree does an $n$-vertex graph need before we are sure that it contains a perfect matching? Dirac's theorem states that a graph on an even number of vertices in which each vertex has degree at least $n/2$ has this property. In this short expository note, intended to be used in the classroom, we discuss how this statement generalizes to hypergraphs. In particular, we highlight an elegant connection between fractional perfect matchings in hypergraphs and a probabilistic inequality about nonnegative random variables, which was conjectured by Feige. We also present a very short self-contained proof of Feige's conjecture.