Counting perfect matchings in Dirac hypergraphs
Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 46, 5.
Download
Journal Article
| Published
| English
Scopus indexed
Corresponding author has ISTA affiliation
Department
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 < k,
and for n divisible by k, let md (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 md (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+γ )md (k, n)
(for any constantγ > 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.
Publishing Year
Date Published
2026-02-01
Journal Title
Combinatorica
Publisher
Springer Nature
Acknowledgement
We would like to thank the referees for a number of helpful comments and suggestions, which have substantially improved the paper. Open access funding provided by Institute of Science and Technology (IST Austria).
Volume
46
Article Number
5
ISSN
eISSN
IST-REx-ID
Cite this
Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8
Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8
Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature, 2026. https://doi.org/10.1007/s00493-025-00194-8.
M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.
Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 46, 5.
Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2026_Combinatorica_Kwan.pdf
539.65 KB
Access Level
Open Access
Date Uploaded
2026-02-16
MD5 Checksum
47b0031d90b0e6b9a843f422a1486089
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2408.09589
