Polynomial-time perfect matchings in dense hypergraphs

DOI10.1016/J.AIM.2014.10.009zbMath1303.05155arXiv1307.2608OpenAlexW2047917450MaRDI QIDQ475264

Peter Keevash, Fiachra Knox, Richard Mycroft

Publication date: 26 November 2014

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.2608

zbMATH Keywords

algorithmshypergraphsmatchings

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)

Related Items (10)

Near Perfect Matchings in ${k}$-Uniform Hypergraphs II ⋮ Embedding clique-factors in graphs with low \(\ell\)-independence number ⋮ Graph Tilings in Incompatibility Systems ⋮ Packing \(k\)-partite \(k\)-uniform hypergraphs ⋮ Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs ⋮ The Complexity of Perfect Packings in Dense Graphs ⋮ On Perfect Matchings and Tilings in Uniform Hypergraphs ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ Hamilton cycles in hypergraphs below the Dirac threshold ⋮ Cyclic triangle factors in regular tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Perfect matchings in 3-partite 3-uniform hypergraphs
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Tight co-degree condition for perfect matchings in 4-graphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree
• Matchings in 3-uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Perfect matchings in \(r\)-partite \(r\)-graphs
• Perfect Matchings in 3-Uniform Hypergraphs with Large Vertex Degree
• Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs
• COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
• Limit Theorems for the Number of Empty Cells in an Equiprobable Scheme for Group Allocation of Particles
• Santa Claus Meets Hypergraph Matchings
• On Perfect Matchings in Uniform Hypergraphs with Large Minimum Vertex Degree
• The Complexity of Almost Perfect Matchings in Uniform Hypergraphs with High Codegree
• Degrees giving independent edges in a hypergraph
• Regularity lemmas for hypergraphs and quasi-randomness
• Reducibility among Combinatorial Problems
• Paths, Trees, and Flowers
• Matchings in hypergraphs of large minimum degree
• Polynomial-time perfect matchings in dense hypergraphs
• The Factorization of Linear Graphs
• Some Theorems on Abstract Graphs

This page was built for publication: Polynomial-time perfect matchings in dense hypergraphs