Counting Perfect Matchings in Dirac Hypergraphs
Open Access
- 28 January 2026
- journal article
- research article
- Published by Springer Nature in Combinatorica
- Vol. 46 (1) , 5
Abstract
One of the foundational theorems of extremal graph theory is Dirac’s theorem , which says that if an n -vertex graph G has minimum degree at least n /2, then G has a Hamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy, Selkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles and perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise description of the numbers of Hamilton cycles and perfect matchings in a Dirac graph G (in terms of an entropy-like parameter of G ). In this paper we extend Cuckler and Kahn’s result to perfect matchings in hypergraphs. For positive integers $$d
d
<
k
, and for n divisible by k , let $$m_{d}(k,n)$$ be the minimum d -degree that ensures the existence of a perfect matching in an n -vertex k -uniform hypergraph. In general, it is an open question to determine (even asymptotically) the values of $$m_{d}(k,n)$$ , but we are nonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if an n -vertex k -uniform hypergraph G has minimum d -degree at least $$(1+\gamma )m_{d}(k,n)$$ (for any constant $$\gamma >0$$ ), then the number of perfect matchings in G is controlled by an entropy-like parameter of G . This strengthens cruder estimates arising from work of Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.
Keywords
All Related Versions
Funding Information
- Institute of Science and Technology
This publication has 19 references indexed in Scilit:
- Perfect Matchings in Random Sparsifications of Dirac HypergraphsCombinatorica, 2024
- Counting Hamilton Cycles in Dirac HypergraphsCombinatorica, 2023
- Asymptotics for Shamir's problemAdvances in Mathematics, 2023
- Recent advances on Dirac-type problems for hypergraphs2016
- Random triangle removalAdvances in Mathematics, 2015
- Large matchings in uniform hypergraphs and the conjectures of Erdős and SamuelsJournal of Combinatorial Theory, Series A, 2012
- Dirac-Type Questions For Hypergraphs — A Survey (Or More Problems For Endre To Solve)2010
- Entropy bounds for perfect matchings and Hamiltonian cyclesCombinatorica, 2009
- Hamiltonian cycles in Dirac graphsCombinatorica, 2009
- Perfect matchings in large uniform hypergraphs with large minimum collective degreeJournal of Combinatorial Theory, Series A, 2009