Decision problem for perfect matchings in dense $k$-uniform hypergraphs
HTML articles powered by AMS MathViewer
- by Jie Han PDF
- Trans. Amer. Math. Soc. 369 (2017), 5197-5218 Request permission
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
- 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
- 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
- Jack Edmonds, Paths, trees, and flowers, Canadian J. Math. 17 (1965), 449–467. MR 177907, DOI 10.4153/CJM-1965-045-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. 2, 732–748. MR 2496914, DOI 10.1137/080729657
- Jie Han, Near perfect matchings in $k$-uniform hypergraphs, Combin. Probab. Comput. 24 (2015), no. 5, 723–732. MR 3371500, DOI 10.1017/S0963548314000613
- 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
- 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. 6, 905–924. MR 2740002, DOI 10.1142/S0129054110007635
- Peter Keevash, Fiachra Knox, and Richard Mycroft, Polynomial-time perfect matchings in dense hypergraphs, STOC’13—Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 311–320. MR 3210792, DOI 10.1145/2488608.2488647
- Peter Keevash, Fiachra Knox, and Richard Mycroft, Polynomial-time perfect matchings in dense hypergraphs, Adv. Math. 269 (2015), 265–334. MR 3281137, DOI 10.1016/j.aim.2014.10.009
- Peter Keevash and Richard Mycroft, A geometric theory for hypergraph matching, Mem. Amer. Math. Soc. 233 (2015), no. 1098, vi+95. MR 3290271, DOI 10.1090/memo/1098
- Imdadullah Khan, Perfect matchings in 3-uniform hypergraphs with large vertex degree, SIAM J. Discrete Math. 27 (2013), no. 2, 1021–1039. MR 3061464, DOI 10.1137/10080796X
- Imdadullah Khan, Perfect matchings in 4-uniform hypergraphs, J. Combin. Theory Ser. B 116 (2016), 333–366. MR 3425249, DOI 10.1016/j.jctb.2015.09.005
- 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, 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
- Allan Lo and Klas Markström, Minimum codegree threshold for $(K_4^3-e)$-factors, J. Combin. Theory Ser. A 120 (2013), no. 3, 708–721. MR 3007146, DOI 10.1016/j.jcta.2012.12.005
- Allan Lo and Klas Markström, $F$-factors in hypergraphs via absorption, Graphs Combin. 31 (2015), no. 3, 679–712. MR 3338027, DOI 10.1007/s00373-014-1410-8
- 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
- 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
- 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
- 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. 3, 632–646. MR 2997414, DOI 10.1016/j.ejc.2011.12.009
- 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
- Andrew Treglown and Yi Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II, J. Combin. Theory Ser. A 120 (2013), no. 7, 1463–1482. MR 3092677, DOI 10.1016/j.jcta.2013.04.008
- W. T. Tutte, The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111. MR 23048, DOI 10.1112/jlms/s1-22.2.107
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
- 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).
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 5197-5218
- MSC (2010): Primary 05C70, 05C65
- DOI: https://doi.org/10.1090/tran/6999
- MathSciNet review: 3632565