A Geometric Theory for Hypergraph Matching
By Peter Keevash, Richard Mycroft. 2011
106 citations recorded by the source corpus.
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-Szemeredi 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.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/21be5625a48fea8fccbd0bfd0296771fa14509dd
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
In Geometry and Topology
Citations in the corpus
- Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs (2014, methodology): “10], which was proved by partitioning the k-graph H into a number of k-partite k-graphs, before finding a perfect matching in each of these k-partite k-graphs by using a theorem of Keevash and Mycroft [10].”
- The existence of designs (2014, methodology): “For dense hypergraphs, we have given structural characterisations of the perfect matching problem with Mycroft [25] and Knox and Mycroft [24] (see also the survey by Rödl and Ruciński [36] for many further references).”
- $F$-factors in hypergraphs via absorption (2011, methodology): “During the submission of this paper, we learned that Keevash and Mycroft [11] determined the exact value of t3(n, 4) for n sufficiently large using a different method.”
- Almost all Steiner triple systems have perfect matchings (2016, unknown): “The existence of perfect matchings is one of the most central questions in the theory of graphs and hypergraphs; in particular, some of the most important recent developments in the field are the work of Johansson, Kahn and Vu [24] on perfect matchings in random hypergraphs, and the theory of Keevas”