A geometric theory for hypergraph matching
From MaRDI portal
Publication:5497101
DOI10.1090/MEMO/1098zbMATH Open1306.05172arXiv1108.1757OpenAlexW2963988718MaRDI QIDQ5497101FDOQ5497101
Authors: Peter Keevash, Richard Mycroft 
Publication date: 3 February 2015
Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1108.1757
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
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(F\)-factors in hypergraphs via absorption
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Title not available (Why is that?)
- A Dirac-Type Theorem for 3-Uniform Hypergraphs
- An Ore-type theorem for perfect packings in graphs
- Embedding large subgraphs into dense graphs
- Regularity Lemma for k-uniform hypergraphs
- Paths, Trees, and Flowers
- Some Theorems on Abstract Graphs
- Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Some intersection theorems for ordered sets and graphs
- Blow-up lemma
- Matchings in 3-uniform hypergraphs
- Perfect matchings in 3-uniform hypergraphs with large vertex degree
- On perfect matchings in uniform hypergraphs with large minimum vertex degree
- Title not available (Why is that?)
- 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
- A hypergraph blow-up lemma
- Regular Partitions of Hypergraphs: Regularity Lemmas
- On Sets of Acquaintances and Strangers at any Party
- Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
- Regularity properties for triple systems
- Extremal problems on set systems
- Loose Hamilton cycles in hypergraphs
- Supersaturated graphs and hypergraphs
- On the Minimal Density of Triangles in Graphs
- Title not available (Why is that?)
- An upper bound for the Turán number \(t_3(n,4)\)
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Uniform edge distribution in hypergraphs is hereditary
- A note on codegree problems for hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- Perfect matchings in uniform hypergraphs with large minimum degree
- Tripartite version of the Corrádi-Hajnal theorem
- Degrees giving independent edges in a hypergraph
- Approximate multipartite version of the Hajnal-Szemerédi theorem
- Variants of the Hajnal-Szemer�di Theorem
- Tight co-degree condition for perfect matchings in 4-graphs
- A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
- Title not available (Why is that?)
- Matchings in hypergraphs of large minimum degree
- Quadripartite version of the Hajnal-Szemerédi theorem
- The Complexity of Perfect Matching Problems on Dense Hypergraphs
- Santa Claus Meets Hypergraph Matchings
- The complexity of almost perfect matchings in uniform hypergraphs with high codegree
- Packing \(k\)-partite \(k\)-uniform hypergraphs
- A randomized embedding algorithm for trees
- Title not available (Why is that?)
- On random sampling in uniform hypergraphs
Cited In (47)
- A note on perfect matchings in uniform hypergraphs
- Title not available (Why is that?)
- Covering and tiling hypergraphs with tight cycles
- Powers of Hamiltonian cycles in multipartite graphs
- Covering and tiling hypergraphs with tight cycles
- Cyclic triangle factors in regular tournaments
- Perfect packings in quasirandom hypergraphs. I.
- Perfect Packings in Quasirandom Hypergraphs II
- On Perfect Matchings and Tilings in Uniform Hypergraphs
- Robust similarity between hypergraphs based on valuations and mathematical morphology operators
- Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
- On vertex independence number of uniform hypergraphs
- Multidimensional threshold matrices and extremal matrices of order 2
- Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
- Tiling tripartite graphs with 3-colorable graphs: the extreme case
- On the König-Hall-Egerváry theorem for multidimensional matrices and multipartite hypergraphs
- On multipartite Hajnal-Szemerédi theorems
- Rainbow spanning structures in graph and hypergraph systems
- On directed versions of the Hajnal-Szemerédi theorem
- Title not available (Why is that?)
- Transversal Ck-factors in subgraphs of the balanced blow-up of Ck
- Partitioning a 2-edge-coloured graph of minimum degree \(2n/3 + o(n)\) into three monochromatic cycles
- Codegree thresholds for covering 3-uniform hypergraphs
- Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles
- A Ramsey–Turán theory for tilings in graphs
- \(H\)-factors in graphs with small independence number
- Triangle‐factors in pseudorandom graphs
- \(F\)-factors in hypergraphs via absorption
- On the co-degree threshold for the Fano plane
- Asymptotic multipartite version of the Alon-Yuster theorem
- The complexity of perfect packings in dense graphs
- Pseudorandom hypergraph matchings
- Tiling multipartite hypergraphs in quasi-random hypergraphs
- Sufficient conditions for perfect mixed tilings
- Almost all Steiner triple systems are almost resolvable
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- Dirac-type results for tilings and coverings in ordered graphs
- Near-perfect clique-factors in sparse pseudorandom graphs
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- On sufficient conditions for spanning structures in dense graphs
- Matching of Given Sizes in Hypergraphs
- Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles
- F$F$‐factors in Quasi‐random Hypergraphs
- A Degree Sequence Strengthening of the Vertex Degree Threshold for a Perfect Matching in 3-Uniform Hypergraphs
- Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Exact minimum codegree threshold for \(K^-_4\)-factors
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)
