×

Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs. (English) Zbl 1404.05145

Summary: Let \(S_1\) and \(S_2\) be two \((k - 1)\)-subsets in a \(k\)-uniform hypergraph \(H\). We call \(S_1\) and \(S_2\) strongly or middle or weakly independent if \(H\) does not contain an edge \(e \in E(H)\) such that \(S_1 \cap e \neq \varnothing\) and \(S_2 \cap e \neq \varnothing\) or \(e \subseteq S_1 \cup S_2\) or \(e \supseteq S_1 \cup S_2\), respectively. In this paper, we obtain the following results concerning these three independence. (1) For any \(n \geq 2k^2 - k\) and \(k \geq 3\), there exists an \(n\)-vertex \(k\)-uniform hypergraph, which has degree sum of any two strongly independent \((k - 1)\)-sets equal to \(2n-4(k-1)\), contains no perfect matching; (2) Let \(d \geq 1\) be an integer and \(H\) be a \(k\)-uniform hypergraph of order \(n \geq kd+(k-2)k\). If the degree sum of any two middle independent \((k-1)\)-subsets is larger than \(2(d-1)\), then \(H\) contains a \(d\)-matching; (3) For all \(k \geq 3\) and sufficiently large \(n\) divisible by \(k\), we completely determine the minimum degree sum of two weakly independent \((k - 1)\)-subsets that ensures a perfect matching in a \(k\)-uniform hypergraph \(H\) of order \(n\).

MSC:

05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI

References:

[1] Alon, N.; Frankl, P.; Huang, H.; etal., Large matchings in uniform hypergraphs and the conjecture of Erdős and Samuels, J. Combin. Theory Ser. A, 119, 1200-1215, (2012) · Zbl 1242.05189 · doi:10.1016/j.jcta.2012.02.004
[2] Edmonds, J., Paths, trees, and flowers, Canad. J. Math., 17, 449-467, (1965) · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[3] Hàn, H.; Person, Y. S. M., On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math., 23, 732-748, (2009) · Zbl 1191.05074 · doi:10.1137/080729657
[4] Han, J., Perfect matchings in hypergraphs and the Erdős matching conjecture, SIAM J. Discrete Math., 30, 1351-1357, (2016) · Zbl 1339.05310 · doi:10.1137/16M1056079
[5] Karp, R. M., Reducibility among combinatorial problems, 85-103, (1972), New York · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9
[6] Khan, I., Perfect matchings in 3-uniform hypergraphs with large vertex degree, SIAM J. Discrete Math., 27, 1021-1039, (2013) · Zbl 1272.05160 · doi:10.1137/10080796X
[7] Khan, I., Perfect matchings in 4-uniform hypergraphs, J. Combin. Theory Ser. B, 116, 333-366, (2016) · Zbl 1327.05274 · doi:10.1016/j.jctb.2015.09.005
[8] Kühn, D.; Osthus, D., Matchings in hypergraphs of large minimum degree, J. Graph Theory, 51, 269-280, (2006) · Zbl 1087.05041 · doi:10.1002/jgt.20139
[9] Kühn, D.; Osthus, D., Embedding large subgraphs into dense graphs, 137-167, (2009), Cambridge · Zbl 1182.05098
[10] Kühn, D.; Osthus, D.; Treglown, A., Matchings in 3-uniform hypergraphs, J. Combin. Theory Ser. B, 103, 291-305, (2013) · Zbl 1262.05128 · doi:10.1016/j.jctb.2012.11.005
[11] Kühn, D.; Osthus, D.; Townsend, T., Fractional and integer matchings in uniform hypergraphs, European J. Combin., 38, 83-96, (2014) · Zbl 1282.05172 · doi:10.1016/j.ejc.2013.11.006
[12] Markström, K.; Ruciński, A., Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, European J. Combin., 32, 677-687, (2011) · Zbl 1229.05231 · doi:10.1016/j.ejc.2011.02.001
[13] Pikhurko, O., Perfect matchings and K_{4}3-tilings in hypergraphs of large codegree, Graphs Combin., 24, 391-404, (2008) · Zbl 1205.05184 · doi:10.1007/s00373-008-0787-7
[14] Rödl, V.; Ruciński, A.; Szemerédi, E., Perfect matchings in uniform hypergraphs with large minimum degree, European J. Combin., 27, 1333-1349, (2006) · Zbl 1104.05051 · doi:10.1016/j.ejc.2006.05.008
[15] 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 · doi:10.1007/s00493-008-2295-z
[16] Rödl, V.; Ruciński, A.; Szemerédi, E., Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A, 116, 613-636, (2009) · Zbl 1214.05130 · doi:10.1016/j.jcta.2008.10.002
[17] 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 · doi:10.1016/j.disc.2017.02.018
[18] Treglown, A.; Zhao, Y., Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A, 119, 1500-1522, (2012) · Zbl 1305.05194 · doi:10.1016/j.jcta.2012.04.006
[19] Treglown, A.; Zhao, Y., Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II, J. Combin. Theory Ser. A, 120, 1463-1482, (2013) · Zbl 1314.05168 · doi:10.1016/j.jcta.2013.04.008
[20] Treglown, A.; Zhao, Y., A note on perfect matchings in uniform hypergraphs, Electron. J. Combin., 23, 1-16, (2016) · Zbl 1329.05247
[21] Tutte, W. T., The factorization of linear graphs, J. London Math. Soc., 22, 107-111, (1947) · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107
[22] Zhang, Y.; Lu, M., d-matching in k-uniform hypergraphs, Discrete Math. Algorithms Appl., 9, 1750072, (2017) · Zbl 1386.05128 · doi:10.1142/S1793830917500720
[23] Zhang, Y.; Lu, M., d-matching in 3-uniform hypergraphs, Discrete Math., 341, 748-758, (2018) · Zbl 1378.05175 · doi:10.1016/j.disc.2017.11.014
[24] Zhang, Y., Lu, M.: Matching in 3-uniform hypergraphs, submitted · Zbl 1378.05175
[25] Zhang, Y., Zhao, Y., Lu, M.: Vertex degree sums for perfect matchings in 3-uniform hypergraphs, submitted · Zbl 1395.05136
[26] Zhao, Y., Recent advances on dirac-type problems for hypergraphs, (2016), 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.