Abstract: We develop a theory for the existence of perfect matchings in hypergraphs under quite general conditions. Informally speaking, the obstructions to perfect matchings are geometric, and are of two distinct types: 'space barriers' from convex geometry, and 'divisibility barriers' from arithmetic lattice-based constructions. To formulate precise results, we introduce the setting of simplicial complexes with minimum degree sequences, which is a generalisation of the usual minimum degree condition. We determine the essentially best possible minimum degree sequence for finding an almost perfect matching. Furthermore, our main result establishes the stability property: under the same degree assumption, if there is no perfect matching then there must be a space or divisibility barrier. This allows the use of the stability method in proving exact results. Besides recovering previous results, we apply our theory to the solution of two open problems on hypergraph packings: the minimum degree threshold for packing tetrahedra in 3-graphs, and Fischer's conjecture on a multipartite form of the Hajnal-Szemer'edi Theorem. Here we prove the exact result for tetrahedra and the asymptotic result for Fischer's conjecture; since the exact result for the latter is technical we defer it to a subsequent paper.
Recommendations
- Geometric graphs: matching, similarity and indexing
- On a hypergraph matching problem
- On matchings in hypergraphs
- Geometric simultaneous embeddings of a graph and a matching
- Geometric simultaneous embeddings of a graph and a matching
- scientific article; zbMATH DE number 1431747
- On a criterion for matchability in hypergraphs
- An algorithmic framework for the matching problem in some hypergraphs
- On the matching polynomial of hypergraphs
- scientific article; zbMATH DE number 7650916
Cites work
- \(F\)-factors in hypergraphs via absorption
- A Dirac-Type Theorem for 3-Uniform Hypergraphs
- A hypergraph blow-up lemma
- A multipartite Hajnal-Szemerédi theorem
- A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
- A note on codegree problems for hypergraphs
- A randomized embedding algorithm for trees
- An Ore-type theorem for perfect packings in graphs
- An upper bound for the Turán number \(t_3(n,4)\)
- Approximate multipartite version of the Hajnal-Szemerédi theorem
- Blow-up lemma
- Degrees giving independent edges in a hypergraph
- Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
- Embedding large subgraphs into dense graphs
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
- Extremal problems on set systems
- scientific article; zbMATH DE number 5942358 (Why is no real title available?)
- scientific article; zbMATH DE number 5485484 (Why is no real title available?)
- scientific article; zbMATH DE number 3821782 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Loose Hamilton cycles in hypergraphs
- Matchings in 3-uniform hypergraphs
- Matchings in hypergraphs of large minimum degree
- On perfect matchings in uniform hypergraphs with large minimum vertex degree
- On random sampling in uniform hypergraphs
- On Sets of Acquaintances and Strangers at any Party
- On the Minimal Density of Triangles in Graphs
- Packing k-partite k-uniform hypergraphs
- Paths, Trees, and Flowers
- Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
- Perfect matchings and K₄^3-tilings in hypergraphs of large codegree
- Perfect matchings in 3-uniform hypergraphs with large vertex degree
- Perfect matchings in 4-uniform hypergraphs
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Perfect matchings in uniform hypergraphs with large minimum degree
- Polynomial-time perfect matchings in dense hypergraphs
- Quadripartite version of the Hajnal-Szemerédi theorem
- Regular Partitions of Hypergraphs: Regularity Lemmas
- Regularity Lemma for k-uniform hypergraphs
- Regularity properties for triple systems
- Santa Claus Meets Hypergraph Matchings
- Some intersection theorems for ordered sets and graphs
- Some Theorems on Abstract Graphs
- Supersaturated graphs and hypergraphs
- The complexity of almost perfect matchings in uniform hypergraphs with high codegree
- The Complexity of Perfect Matching Problems on Dense Hypergraphs
- Tight co-degree condition for perfect matchings in 4-graphs
- Tripartite version of the Corrádi-Hajnal theorem
- Uniform edge distribution in hypergraphs is hereditary
- Variants of the Hajnal-Szemer�di Theorem
Cited in
(51)- Covering and tiling hypergraphs with tight cycles
- Tiling tripartite graphs with 3-colorable graphs: the extreme case
- On multipartite Hajnal-Szemerédi theorems
- On the König-Hall-Egerváry theorem for multidimensional matrices and multipartite hypergraphs
- Powers of Hamiltonian cycles in multipartite graphs
- Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
- Robust similarity between hypergraphs based on valuations and mathematical morphology operators
- Cyclic triangle factors in regular tournaments
- \(F\)-factors in hypergraphs via absorption
- Asymptotic multipartite version of the Alon-Yuster theorem
- On the co-degree threshold for the Fano plane
- Tiling multipartite hypergraphs in quasi-random hypergraphs
- Perfect packings in quasirandom hypergraphs. I.
- Codegree thresholds for covering 3-uniform hypergraphs
- Decision problem for perfect matchings in dense k-uniform hypergraphs
- The complexity of perfect packings in dense graphs
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- On perfect matchings in \(k\)-complexes
- On vertex independence number of uniform hypergraphs
- On perfect matchings and tilings in uniform hypergraphs
- Triangle‐factors in pseudorandom graphs
- Pseudorandom hypergraph matchings
- Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
- Covering and tiling hypergraphs with tight cycles
- Matching of given sizes in hypergraphs
- Dirac-type results for tilings and coverings in ordered graphs
- A degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs
- Almost all Steiner triple systems are almost resolvable
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Codegree conditions for tiling complete \(k\)-partite \(k\)-graphs and loose cycles
- On the matching polynomial of hypergraphs
- Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
- On directed versions of the Hajnal-Szemerédi theorem
- Perfect Packings in Quasirandom Hypergraphs II
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- Exact minimum codegree threshold for K^-_4-factors
- scientific article; zbMATH DE number 6297805 (Why is no real title available?)
- Near-perfect clique-factors in sparse pseudorandom graphs
- Transversal Ck-factors in subgraphs of the balanced blow-up of Ck
- Rainbow spanning structures in graph and hypergraph systems
- On sufficient conditions for spanning structures in dense graphs
- FF‐factors in Quasi‐random Hypergraphs
- A Ramsey–Turán theory for tilings in graphs
- Multidimensional threshold matrices and extremal matrices of order 2
- Partitioning a 2-edge-coloured graph of minimum degree \(2n/3 + o(n)\) into three monochromatic cycles
- H-factors in graphs with small independence number
- Sufficient conditions for perfect mixed tilings
- Approximate packing of independent transversals in locally sparse graphs
- Tiling dense hypergraphs (extended abstract)
- Matchings in multipartite hypergraphs
- A note on perfect matchings in uniform hypergraphs
This page was built for publication: A geometric theory for hypergraph matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5497101)
