AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
A geometric theory for hypergraph matching
About this Title
Peter Keevash, Mathematical Institute, University of Oxford, Oxford, United Kingdom and Richard Mycroft, School of Mathematics, University of Birmingham, Birmingham, United Kingdom
Publication: Memoirs of the American Mathematical Society
Publication Year:
2015; Volume 233, Number 1098
ISBNs: 978-1-4704-0965-4 (print); 978-1-4704-1966-0 (online)
DOI: https://doi.org/10.1090/memo/1098
Published electronically: May 19, 2014
Keywords: hypergraphs,
perfect matchings
MSC: Primary 05C65, 05C70
Table of Contents
Chapters
- 1. Introduction
- 2. Results and examples
- 3. Geometric Motifs
- 4. Transferrals
- 5. Transferrals via the minimum degree sequence
- 6. Hypergraph Regularity Theory
- 7. Matchings in $k$-systems
- 8. Packing Tetrahedra
- 9. The general theory
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édi 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.- Noga Alon, Peter Frankl, Hao Huang, Vojtech Rödl, Andrzej Ruciński, and Benny Sudakov, Large matchings in uniform hypergraphs and the conjecture of Erdős and Samuels, J. Combin. Theory Ser. A 119 (2012), no. 6, 1200–1215. MR 2915641, DOI 10.1016/j.jcta.2012.02.004
- Arash Asadpour, Uriel Feige, and Amin Saberi, Santa Claus meets hypergraph matchings, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., vol. 5171, Springer, Berlin, 2008, pp. 10–20. MR 2538773, DOI 10.1007/978-3-540-85363-3_{2}
- Béla Bollobás, Combinatorics, Cambridge University Press, Cambridge, 1986. Set systems, hypergraphs, families of vectors and combinatorial probability. MR 866142
- F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer, Some intersection theorems for ordered sets and graphs, J. Combin. Theory Ser. A 43 (1986), no. 1, 23–37. MR 859293, DOI 10.1016/0097-3165(86)90019-1
- Fan Chung and Linyuan Lu, An upper bound for the Turán number $t_3(n,4)$, J. Combin. Theory Ser. A 87 (1999), no. 2, 381–389. MR 1704268, DOI 10.1006/jcta.1998.2961
- Béla Csaba and Marcelo Mydlarz, Approximate multipartite version of the Hajnal-Szemerédi theorem, J. Combin. Theory Ser. B 102 (2012), no. 2, 395–410. MR 2885426, DOI 10.1016/j.jctb.2011.10.003
- Andrzej Czygrinow and Vikram Kamat, Tight co-degree condition for perfect matchings in 4-graphs, Electron. J. Combin. 19 (2012), no. 2, Paper 20, 16. MR 2928635, DOI 10.37236/2338
- Andrzej Czygrinow and Brendan Nagle, A note on codegree problems for hypergraphs, Bull. Inst. Combin. Appl. 32 (2001), 63–69. MR 1829685
- Andrzej Czygrinow and Brendan Nagle, On random sampling in uniform hypergraphs, Random Structures Algorithms 38 (2011), no. 4, 422–440. MR 2829310, DOI 10.1002/rsa.20326
- David E. Daykin and Roland Häggkvist, Degrees giving independent edges in a hypergraph, Bull. Austral. Math. Soc. 23 (1981), no. 1, 103–109. MR 615135, DOI 10.1017/S0004972700006924
- G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952), 69–81. MR 47308, DOI 10.1112/plms/s3-2.1.69
- Jack Edmonds, Paths, trees, and flowers, Canadian J. Math. 17 (1965), 449–467. MR 177907, DOI 10.4153/CJM-1965-045-4
- Paul Erdős and Miklós Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), no. 2, 181–192. MR 726456, DOI 10.1007/BF02579292
- Eldar Fischer, Variants of the Hajnal-Szemerédi theorem, J. Graph Theory 31 (1999), no. 4, 275–282. MR 1698745, DOI 10.1002/(SICI)1097-0118(199908)31:4<275::AID-JGT2>3.3.CO;2-6
- Peter Frankl and Vojtěch Rödl, Extremal problems on set systems, Random Structures Algorithms 20 (2002), no. 2, 131–164. MR 1884430, DOI 10.1002/rsa.10017.abs
- A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783. MR 107610, DOI 10.2307/2310464
- W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. of Math. (2) 166 (2007), no. 3, 897–946. MR 2373376, DOI 10.4007/annals.2007.166.897
- A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 601–623. MR 0297607
- Hiệp Hàn, Yury Person, and Mathias Schacht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math. 23 (2009), no. 2, 732–748. MR 2496914, DOI 10.1137/080729657
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847
- Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
- Peter Keevash, A hypergraph blow-up lemma, Random Structures Algorithms 39 (2011), no. 3, 275–376. MR 2816936, DOI 10.1002/rsa.20362
- Peter Keevash, Hypergraph Turán problems, Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 83–139. MR 2866732
- P. Keevash, F. Knox and R. Mycroft, Polynomial-time perfect matchings in dense hypergraphs, Proc. 45th STOC, to appear.
- Peter Keevash, Daniela Kühn, Richard Mycroft, and Deryk Osthus, Loose Hamilton cycles in hypergraphs, Discrete Math. 311 (2011), no. 7, 544–559. MR 2765622, DOI 10.1016/j.disc.2010.11.013
- P. Keevash and R. Mycroft, A multipartite Hajnal-Szemerédi theorem, arXiv:1201.1882.
- I. Khan, Perfect Matching in 3 uniform hypergraphs with large vertex degree, arXiv:1101.5830.
- I. Khan, Perfect matchings in 4-uniform hypergraphs, arXiv:1101.5675.
- János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Blow-up lemma, Combinatorica 17 (1997), no. 1, 109–123. MR 1466579, DOI 10.1007/BF01196135
- Daniela Kühn and Deryk Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (2006), no. 4, 269–280. MR 2207573, DOI 10.1002/jgt.20139
- Daniela Kühn and Deryk Osthus, The minimum degree threshold for perfect graph packings, Combinatorica 29 (2009), no. 1, 65–107. MR 2506388, DOI 10.1007/s00493-009-2254-3
- Daniela Kühn and Deryk Osthus, Embedding large subgraphs into dense graphs, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 137–167. MR 2588541
- Daniela Kühn, Deryk Osthus, and Andrew Treglown, Matchings in 3-uniform hypergraphs, J. Combin. Theory Ser. B 103 (2013), no. 2, 291–305. MR 3018071, DOI 10.1016/j.jctb.2012.11.005
- Marek Karpiński, Andrzej Ruciński, and Edyta Szymańska, The complexity of perfect matching problems on dense hypergraphs, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 5878, Springer, Berlin, 2009, pp. 626–636. MR 2792760, DOI 10.1007/978-3-642-10631-6_{6}4
- A. Lo and K. Markström, $F$-factors in hypergraphs via absorption, arXiv:1105.3411.
- A. Lo and K. Markström, A multipartite version of the Hajnal-Szemerédi theorem for graphs and hypergraphs, arXiv:1108.4184.
- L. Lovász and M. Simonovits, On the number of complete subgraphs of a graph. II, Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 459–495. MR 820244
- Csaba Magyar and Ryan R. Martin, Tripartite version of the Corrádi-Hajnal theorem, Discrete Math. 254 (2002), no. 1-3, 289–308. MR 1910115, DOI 10.1016/S0012-365X(01)00373-9
- Klas Markström and Andrzej Ruciński, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, European J. Combin. 32 (2011), no. 5, 677–687. MR 2788783, DOI 10.1016/j.ejc.2011.02.001
- Ryan Martin and Endre Szemerédi, Quadripartite version of the Hajnal-Szemerédi theorem, Discrete Math. 308 (2008), no. 19, 4337–4360. MR 2433861, DOI 10.1016/j.disc.2007.08.019
- Dhruv Mubayi and Vojtĕch Rödl, Uniform edge distribution in hypergraphs is hereditary, Electron. J. Combin. 11 (2004), no. 1, Research Paper 55, 32. MR 2097321
- R. Mycroft, Packing $k$-partite $k$-graphs, in preparation.
- Brendan Nagle and Vojtěch Rödl, Regularity properties for triple systems, Random Structures Algorithms 23 (2003), no. 3, 264–332. MR 1999038, DOI 10.1002/rsa.10094
- Oleg Pikhurko, Perfect matchings and $K^3_4$-tilings in hypergraphs of large codegree, Graphs Combin. 24 (2008), no. 4, 391–404. MR 2438870, DOI 10.1007/s00373-008-0787-7
- Alexander A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603–618. MR 2433944, DOI 10.1017/S0963548308009085
- Vojtech Rödl and Andrzej Ruciński, Dirac-type questions for hypergraphs—a survey (or more problems for Endre to solve), An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 561–590. MR 2815614, DOI 10.1007/978-3-642-14444-8_{1}6
- Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), no. 1-2, 229–251. MR 2195584, DOI 10.1017/S0963548305007042
- Vojtech Rödl, Andrzej Ruciński, and Endre Szemerédi, Perfect matchings in uniform hypergraphs with large minimum degree, European J. Combin. 27 (2006), no. 8, 1333–1349. MR 2260124, DOI 10.1016/j.ejc.2006.05.008
- Vojtech Rödl, Andrzej Ruciński, and Endre Szemerédi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116 (2009), no. 3, 613–636. MR 2500161, DOI 10.1016/j.jcta.2008.10.002
- Vojtěch Rödl and Mathias Schacht, Regular partitions of hypergraphs: regularity lemmas, Combin. Probab. Comput. 16 (2007), no. 6, 833–885. MR 2351688, DOI 10.1017/s0963548307008553
- Vojtěch Rödl and Mathias Schacht, Property testing in hypergraphs and the removal lemma [extended abstract], STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 488–495. MR 2402474, DOI 10.1145/1250790.1250862
- Vojtěch Rödl and Jozef Skokan, Regularity lemma for $k$-uniform hypergraphs, Random Structures Algorithms 25 (2004), no. 1, 1–42. MR 2069663, DOI 10.1002/rsa.20017
- Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
- Benny Sudakov and Jan Vondrák, A randomized embedding algorithm for trees, Combinatorica 30 (2010), no. 4, 445–470. MR 2728498, DOI 10.1007/s00493-010-2422-5
- Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
- Edyta Szymańska, The complexity of almost perfect matchings in uniform hypergraphs with high codegree, Combinatorial algorithms, Lecture Notes in Comput. Sci., vol. 5874, Springer, Berlin, 2009, pp. 438–449. MR 2577959, DOI 10.1007/978-3-642-10217-2_{4}3
- Andrew Treglown and Yi Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A 119 (2012), no. 7, 1500–1522. MR 2925939, DOI 10.1016/j.jcta.2012.04.006
- P. Turán, On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok 48 (1941), 436–452.