Skip to content
DraconiticResearch
Search Sources API
197,788 studies31 sourcesUpdated 16 min ago
PreprintCC BY 4.0arXiv

Perfect matchings in hypergraphs and Feige's inequality

  • Aleksa Milojević
  • Benny Sudakov
Open at sourcePDFDOICite

Abstract

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.

Related

  1. Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
    Ali Ghalavand
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. A simplified proof of the FPRAS for counting perfect matchings
    Chenghua Liu, Boning Meng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
    Huaibin Zhou, Xiumei Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
    G. Arunkumar, Puja Samanta
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. A rate for the average vacancy of uniformly random matchings in linear hypergraphs
    Anish Gupta
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{milojevic2026perfect,
  title = {{Perfect matchings in hypergraphs and Feige's inequality}},
  author = {Aleksa Milojević and Benny Sudakov},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.10380},
  eprint = {2610.10380},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.10380},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Perfect matchings in hypergraphs and Feige's inequality
AU  - Aleksa Milojević
AU  - Benny Sudakov
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.10380
UR  - https://arxiv.org/abs/2610.10380
AB  - 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.
ER  -