Transactions of the American Mathematical Society · 2016 · 40 citations · 22 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsHypergraph TheoryMatching TheoryAnnotation EncodingGraph MatchingMatching AlgorithmsMatching ProblemsMatching Theory In HypergraphsPolynomial Time ComplexityPolynomial-time Algorithms
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>></mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\gamma >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.
22
Jack Edmonds · Canadian Journal of Mathematics · 1965 · 2.4K citations · Full text
The Factorization of Linear Graphs
W. T. Tutte · Journal of the London Mathematical Society · 1947 · 939 citations