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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$d<k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo><</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>, and for n divisible by k, let <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$m_{d}(k,n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>m</mi> <mi>d</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$m_{d}(k,n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>m</mi> <mi>d</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$(1+\gamma )m_{d}(k,n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>γ</mi> <mo stretchy="false">)</mo> </mrow> <msub> <mi>m</mi> <mi>d</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> (for any constant <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\gamma >0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>γ</mi> <mo>></mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>), 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.

Counting Perfect Matchings in Dirac Hypergraphs

期刊论文
出版模式：

开放获取
发表日期：

2026年1月28日

查看全文

Matthew Kwan,
Roodabeh Safavi,
Yiting Wang

摘要

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$ $d < k$ , and for n divisible by k, let $m_{d}(k,n)$ $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)$ $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)$ $(1 + γ) m_{d} (k, n)$ (for any constant $\gamma >0$ $γ > 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.