Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Decision problem for perfect matchings in dense $ k$-uniform hypergraphs


Author: Jie Han
Journal: Trans. Amer. Math. Soc. 369 (2017), 5197-5218
MSC (2010): Primary 05C70, 05C65
DOI: https://doi.org/10.1090/tran/6999
Published electronically: March 17, 2017
MathSciNet review: 3632565
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For any $ \gamma >0$, Keevash, Knox and Mycroft (2015) constructed a polynomial-time algorithm which determines the existence of perfect matchings in any $ n$-vertex $ k$-uniform hypergraph whose minimum codegree is at least $ n/k+\gamma n$. We prove a structural theorem that enables us to determine the existence of a perfect matching for any $ k$-uniform hypergraph with minimum codegree at least $ n/k$. This solves a problem of Karpiński, Ruciński and Szymańska completely. Our proof uses a lattice-based absorbing method.


References [Enhancements On Off] (What's this?)

  • [1] Noga Alon, Peter Frankl, Hao Huang, Vojtech Ruciński, 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. no. 6, 1200-1215. MR 2915641
  • [2] Andrzej Czygrinow and Vikram Kamat, Tight co-degree condition for perfect matchings in 4-graphs, Electron. J. Combin. 19 (2012), no. no. 2, Paper 20, 16. MR 2928635
  • [3] Jack Edmonds, Paths, trees, and flowers, Canad. J. Math. 17 (1965), 449-467. MR 0177907
  • [4] 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. no. 2, 732-748. MR 2496914
  • [5] Jie Han, Near perfect matchings in $ k$-uniform hypergraphs, Combin. Probab. Comput. 24 (2015), no. no. 5, 723-732. MR 3371500
  • [6] Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (1972), 85-103. MR 0378476
  • [7] Marek Karpiński, Andrzej Ruciński, and Edyta Szymańska, Computational complexity of the perfect matching problem in hypergraphs with subcritical density, Internat. J. Found. Comput. Sci. 21 (2010), no. no. 6, 905-924. MR 2740002
  • [8] Peter Keevash, Fiachra Knox, and Richard Mycroft, Polynomial-time perfect matchings in dense hypergraphs, Proceedings of the 2013 ACM Symposium on Theory of Computing (2013), 311-320. MR 3210792
  • [9] Peter Keevash, Fiachra Knox, and Richard Mycroft, Polynomial-time perfect matchings in dense hypergraphs, Adv. Math. 269 (2015), 265-334. MR 3281137
  • [10] Peter Keevash and Richard Mycroft, A geometric theory for hypergraph matching, Mem. Amer. Math. Soc. 233 (2015), no. no. 1098, vi+95. MR 3290271
  • [11] Imdadullah Khan, Perfect matchings in 3-uniform hypergraphs with large vertex degree, SIAM J. Discrete Math. 27 (2013), no. no. 2, 1021-1039. MR 3061464
  • [12] Imdadullah Khan, Perfect matchings in 4-uniform hypergraphs, J. Combin. Theory Ser. B 116 (2016), 333-366. MR 3425249
  • [13] Daniela Kühn and Deryk Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (2006), no. no. 4, 269-280. MR 2207573
  • [14] Daniela Kühn, Deryk Osthus, and Andrew Treglown, Matchings in 3-uniform hypergraphs, J. Combin. Theory Ser. B 103 (2013), no. no. 2, 291-305. MR 3018071
  • [15] Allan Lo and Klas Markström, Minimum codegree threshold for $ (K_4^3-e)$-factors, J. Combin. Theory Ser. A 120 (2013), no. no. 3, 708-721. MR 3007146
  • [16] Allan Lo and Klas Markström, $ F$-factors in hypergraphs via absorption, Graphs Combin. 31 (2015), no. no. 3, 679-712. MR 3338027
  • [17] Klas Markström and Andrzej Ruciński, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, European J. Combin. 32 (2011), no. no. 5, 677-687. MR 2788783
  • [18] Oleg Pikhurko, Perfect matchings and $ K^3_4$-tilings in hypergraphs of large codegree, Graphs Combin. 24 (2008), no. no. 4, 391-404. MR 2438870
  • [19] 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
  • [20] 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. no. 1-2, 229-251. MR 2195584
  • [21] 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. no. 8, 1333-1349. MR 2260124
  • [22] 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. no. 3, 613-636. MR 2500161
  • [23] Edyta Szymańska, The complexity of almost perfect matchings and other packing problems in uniform hypergraphs with high codegree, European J. Combin. 34 (2013), no. no. 3, 632-646. MR 2997414
  • [24] Andrew Treglown and Yi Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A 119 (2012), no. no. 7, 1500-1522. MR 2925939
  • [25] Andrew Treglown and Yi Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II, J. Combin. Theory Ser. A 120 (2013), no. no. 7, 1463-1482. MR 3092677
  • [26] W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107-111. MR 0023048

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C70, 05C65

Retrieve articles in all journals with MSC (2010): 05C70, 05C65


Additional Information

Jie Han
Affiliation: Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil
Email: jhan@ime.usp.br

DOI: https://doi.org/10.1090/tran/6999
Keywords: Perfect matching, hypergraph, absorbing method
Received by editor(s): October 15, 2014
Received by editor(s) in revised form: June 17, 2016
Published electronically: March 17, 2017
Additional Notes: The author was supported by FAPESP (2014/18641-5, 2015/07869-8).
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society