Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs

Jie Han

Transactions of the American Mathematical Society · 2016 · 40 citations · 22 references

DOIFull text

Open access

Concepts

Abstract

For any <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="gamma greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi> γ </mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\gamma &gt;0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , Keevash, Knox and Mycroft (2015) constructed a polynomial-time algorithm which determines the existence of perfect matchings in any <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -vertex <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -uniform hypergraph whose minimum codegree is at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n slash k plus gamma n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mi> γ </mml:mi> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n/k+\gamma n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We prove a structural theorem that enables us to determine the existence of a perfect matching for any <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -uniform hypergraph with minimum codegree at least <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n slash k"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n/k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . This solves a problem of Karpiński, Ruciński and Szymańska completely. Our proof uses a lattice-based absorbing method.

References

22