Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs

Han, Jie

doi:10.1090/tran/6999

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