ARTICLE

Minimum codegree condition for perfect matchings in k-partite k-graphs

Corresponding Author

Hongliang Lu

[email protected]

orcid.org/0000-0003-4447-2416

School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, China

Correspondence Hongliang Lu, School of Mathematics and Statistics, Xi'an Jiaotong University, 710049 Xi'an, Shaanxi, China. Email: [email protected]

Search for more papers by this author

Yan Wang,

Yan Wang

School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia

Search for more papers by this author

Xingxing Yu,

Xingxing Yu

School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia

Search for more papers by this author

Hongliang Lu,

Corresponding Author

Hongliang Lu

[email protected]

orcid.org/0000-0003-4447-2416

School of Mathematics and Statistics, Xi'an Jiaotong University, Xi'an, China

Correspondence Hongliang Lu, School of Mathematics and Statistics, Xi'an Jiaotong University, 710049 Xi'an, Shaanxi, China. Email: [email protected]

Search for more papers by this author

Yan Wang,

Yan Wang

School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia

Search for more papers by this author

Xingxing Yu,

Xingxing Yu

School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia

Search for more papers by this author

First published: 14 January 2019

https://doi.org/10.1002/jgt.22448

Citations: 2

Share a link

Email
Wechat
Bluesky

Abstract

Let $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0003$ be a $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0004$ -partite $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0005$ -graph with $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0006$ vertices in each partition class, and let $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0007$ denote the minimum codegree of $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0008$ . We characterize those $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0009$ with $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0010$ and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rödl and Ruciński: if $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0011$ is even or $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0012$ , does $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0013$ imply that $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0014$ has a perfect matching? We also give an example indicating that it is not sufficient to impose this degree bound on only two types of $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-0015$ -sets.

REFERENCES

1R. Aharoni, A. Georgakopoulos, and P. Sprüssel, Perfect matchings in $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-1428$ -partite $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-1429$ -graphs, European J. Combin. 30 (2009), 39–42.
10.1016/j.ejc.2008.02.011
Web of Science® Google Scholar
2B. Bollobás, D. E. Daykin, and P. Erdös, Sets of independent edges of a hypergraphs, Quart. J. Math. Oxoford Ser. 27 (1976), 25–32.
10.1093/qmath/27.1.25
Web of Science® Google Scholar
3J. Han, Near perfect matching in $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-1430$ -uniform hypergraph, Combin. Probab. Comput. 24 (2015), 723–732.
10.1017/S0963548314000613
Web of Science® Google Scholar
4H. Hán, Y. Person, and M. Schacht, On perfect matchings inuniform hypergraphs with large minimum vertex degree, SIAM J. Discret. Math. 23 (2009), 732–748.
10.1137/080729657
Web of Science® Google Scholar
5J. Han, C. Zang, and Y. Zhao, Matchings in k-partite k-uniform hypergraphs, Combinatorics. https://arxiv.org/pdf/1611.00290v2.pdf
Google Scholar
6D. Kühn, and D. Osthus, Matchings in hypergraphs of large minimum degree, J. Graph Theory 51 (2006), 269–280.
10.1002/jgt.20139
Web of Science® Google Scholar
7D. Kühn, D. Osthus, and A. Treglown, Matchings in 3-uniform hypergraphs, J. Combin. Theory, Ser. B 103 (2013), 291–305.
10.1016/j.jctb.2012.11.005
Web of Science® Google Scholar
8A. Lo, and K. Markström, Perfect matchings in 3-partite 3-uniform hypergraphs, J. Combin. Theory Ser. A 127 (2014), 22–57.
10.1016/j.jcta.2014.05.004
Web of Science® Google Scholar
9H. Lu, Y. Wang, and X. Yu, Almost perfect matchings in $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-1431$ -partite $urn:x-wiley:03649024:media:jgt22448:jgt22448-math-1432$ -graphs, SIAM J. Discrete Math. 32 (2018), 522–533.
10.1137/16M1097948
Web of Science® Google Scholar
10M. Mitzenmacher, and E. Upfal, Probability and computing: randomized algorithms and probabilistic analysis, Cambridge University Press, Cambridge, UK, 2005.
10.1017/CBO9780511813603
Google Scholar
11V. Rödl, and A. Ruciński, Dirac-type questions for hypergraphs-asurvey (or more problems for Endre to solve), I. Barany and J. Solymosi (eds.), An irregular mind, Springer, Berlin Heidelberg, 2010, pp. 561–590.
10.1007/978-3-642-14444-8_16
Google Scholar
12V. Rödl, A. Ruciński, and E. Szemerédi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116 (2009), 616–636.
10.1016/j.jcta.2008.10.002
Web of Science® Google Scholar
13A. Treglown, and Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A 119 (2012), 1500–1522.
10.1016/j.jcta.2012.04.006
Web of Science® Google Scholar
14A. Treglown, and Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II, J. Combin. Theory Ser. A 120 (2013), 1463–1482.
10.1016/j.jcta.2013.04.008
Web of Science® Google Scholar