×

Vertex degree sums for matchings in 3-uniform hypergraphs. (English) Zbl 1540.05148

A \(k\)-uniform hypergraph \(H\) is a pair \(((V(H), E(H))\) where \(V(H)\) is a finite set of vertices and \(E(H)\) is a family of \(k\)-element subsets of \(V(H)\). A matching of size \(s\) in \(H\) is a family of \(s\) pairwise disjoint edges of \(H\). Given a set \(S\subseteq V(H)\) the degree \(\deg(S)=\deg_H(S)\) is the number of edges of \(H\) containing \(S\).
The main result of this paper is this Ore-type theorem: Let \(n\), \(s\) be positive integers such that \(n\) is sufficiently large and \(n\geq 4s+7\). Suppose \(H\) is a 3-uniform hypergraph of order \(n\). If \(H\) contains no isolated vertices and \(\deg(u)+\deg(v)> 2\left(\binom{n-1}{2} -\binom{n-s}{2}\right)+1\) for any two vertices \(u\) and \(v\) contained in some edge of \(H\), then \(H\) either contains a matching of size \(s\) or is a subgraph of \(H_{n,s}\), where \(H_{n,s}\) is the \(3\)-uniform hypergraph of order \(n\) whose vertex-set is partitioned into two sets \(S\) and \(T\) of sizes \(n-2s+2\) and \(2s-1\), respectively, and whose edge-set consists of all triples with at least two vertices in \(T\). This result improves an earlier one by the same authors [ibid. 342, No. 6, 1731–1737 (2019; Zbl 1414.05244)].

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C65 Hypergraphs
05C07 Vertex degrees

Citations:

Zbl 1414.05244
Full Text: DOI

References:

[1] Aharoni, R.; Howard, D., A rainbow r-partite version of the Erdős-Ko-Rado theorem, Comb. Probab. Comput., 26, 321-337, 2017 · Zbl 1371.05195
[2] Alon, N.; Frankl, P.; Huang, H.; Rödl, V.; Ruciński, A.; Sudakov, B., Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, J. Comb. Theory, Ser. A, 119, 1200-1215, 2012 · Zbl 1242.05189
[3] Erdős, P., A problem on independent r-tuples, Ann. Univ. Sci. Bp. Eőtvős Sect. Math., 8, 93-95, 1965 · Zbl 0136.21302
[4] Frankl, P., An Erdő-Ko-Rado theorem for direct products, Eur. J. Comb., 17, 8, 727-730, 1996 · Zbl 0860.05068
[5] Frankl, P., On the maximum number of edges in a hypergraph with given matching number, Discrete Appl. Math., 216, 562-581, 2017 · Zbl 1358.05202
[6] Hàn, H.; Person, Y.; Schacht, M., On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math., 23, 732-748, 2009 · Zbl 1191.05074
[7] Han, J., Perfect matchings in hypergraphs and the Erdős matching conjecture, SIAM J. Discrete Math., 30, 1351-1357, 2016 · Zbl 1339.05310
[8] Khan, I., Perfect matching in 3-uniform hypergraphs with large vertex degree, SIAM J. Discrete Math., 27, 1021-1039, 2013 · Zbl 1272.05160
[9] Khan, I., Perfect matchings in 4-uniform hypergraphs, J. Comb. Theory, Ser. B, 116, 333-366, 2016 · Zbl 1327.05274
[10] Kühn, D.; Osthus, D., Matchings in hypergraphs of large minimum degree, J. Graph Theory, 51, 269-280, 2006 · Zbl 1087.05041
[11] Kühn, D.; Osthus, D.; Treglown, A., Matchings in 3-uniform hypergraphs, J. Comb. Theory, Ser. B, 103, 291-305, 2013 · Zbl 1262.05128
[12] Łuczak, T.; Mieczkowska, K., On Erdős’ extremal problem on matchings in hypergraphs, J. Comb. Theory, Ser. A, 124, 178-194, 2014 · Zbl 1283.05143
[13] Markström, K.; Ruciński, A., Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, Eur. J. Comb., 32, 677-687, 2011 · Zbl 1229.05231
[14] Ore, O., Note on Hamilton circuits, Am. Math. Mon., 67, 55, 1960 · Zbl 0089.39505
[15] Pikhurko, O., Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree, Graphs Comb., 24, 391-404, 2008 · Zbl 1205.05184
[16] Rödl, V.; Ruciński, A., Dirac-type questions for hypergraphs – a survey (or more problems for Endre to solve), (An Irregular Mind. An Irregular Mind, Bolyai Soc. Math. Studies, vol. 21, 2010), 561-590 · Zbl 1221.05255
[17] Rödl, V.; Ruciński, A.; Szemerédi, E., Perfect matchings in uniform hypergraphs with large minimum degree, Eur. J. Comb., 27, 1333-1349, 2006 · Zbl 1104.05051
[18] Rödl, V.; Ruciński, A.; Szemerédi, E., An approximate Dirac-type theorem for k-uniform hypergraphs, Combinatorica, 28, 229-260, 2008 · Zbl 1164.05051
[19] Rödl, V.; Ruciński, A.; Szemerédi, E., Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Comb. Theory, Ser. A, 116, 613-636, 2009 · Zbl 1214.05130
[20] Tang, Y.; Yan, G., An approximate Ore-type result for tight Hamilton cycles in uniform hypergraphs, Discrete Math., 340, 1528-1534, 2017 · Zbl 1361.05071
[21] Treglown, A.; Zhao, Y., Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Comb. Theory, Ser. A, 119, 1500-1522, 2012 · Zbl 1305.05194
[22] Treglown, A.; Zhao, Y., Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II, J. Comb. Theory, Ser. A, 120, 1463-1482, 2013 · Zbl 1314.05168
[23] Treglown, A.; Zhao, Y., A note on perfect matchings in uniform hypergraphs, Electron. J. Comb., 23, Article P1.16 pp., 2016 · Zbl 1329.05247
[24] Zhang, Y.; Lu, M., Some Ore-type results for matching and perfect matching in k-uniform hypergraphs, Acta Math. Sin. Engl. Ser., 34, 1795-1803, 2018 · Zbl 1404.05145
[25] Zhang, Y.; Lu, M., d-matching in 3-uniform hypergraphs, Discrete Math., 341, 748-758, 2018 · Zbl 1378.05175
[26] Zhang, Y.; Lu, M., Matching in 3-uniform hypergraphs, Discrete Math., 342, 1731-1737, 2019 · Zbl 1414.05244
[27] Zhang, Y.; Lu, M.; Liu, K., Perfect matching and Hamilton cycle decomposition of complete balanced \(k + 1\)-partite k-uniform hypergraphs, Appl. Math. Comput., 386, Article 125492 pp., 2020 · Zbl 1497.05224
[28] Zhang, Y.; Zhao, Y.; Lu, M., Vertex degree sums for perfect matchings in 3-uniform hypergraphs, Electron. J. Comb., 25, Article P3.45 pp., 2018 · Zbl 1395.05136
[29] Zhang, Y.; Zhao, Y.; Lu, M., Vertex degree sums for matchings in 3-uniform hypergraphs, Electron. J. Comb., 26, P4.5, 2019 · Zbl 1422.05088
[30] Zhao, Y., Recent advances on Dirac-type problems for hypergraphs, (Recent Trends in Combinatorics. Recent Trends in Combinatorics, The IMA Volumes in Mathematics and Its Applications, vol. 159, 2016, Springer: Springer New York) · Zbl 1354.05100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.