\(d\)-matching in \(k\)-uniform hypergraphs. (English) Zbl 1386.05128
Summary: A matching of a \(k\)-uniform hypergraph is a set of pairwise disjoint edges. A \(d\)-matching in a \(k\)-uniform hypergraph \(H\) is a matching of size \(d\). Let \(H\) be a \(k\)-uniform hypergraph of order \(n > 2 k^3(d + 1)\) and \(m(n, d, k) = \left(\frac{n - 1}{k - 1}\right) - \left(\frac{n - d}{k - 1}\right)\). If \(d_H(u) + d_H(v) > 2 m(n, d, k)\) for any two adjacent vertices \(u, v \in V(H)\), and \(| \{u \in V(H) \mid d_H(u) \leq m(n, d, k) \} | \leq k - 1\), then \(H\) contains a \(d\)-matching. This result is an extension of a work of B. Bollobás et al. [Q. J. Math., Oxf. II. Ser. 27, 25–32 (1976; Zbl 0337.05135)].
MSC:
| 05C65 | Hypergraphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Citations:
Zbl 0337.05135References:
| [1] | Bollobás, B., Daykin, D. and Erdős, P., Sets of independent edges of a hypergraph, Quart. J. Math. Oxford21 (1976) 25-32. · Zbl 0337.05135 |
| [2] | Daykin, D. and Häggkvist, R., Degrees giving independent edges in a hypergraph, Bull. Austral. Math. Soc.23 (1981) 103-109. · Zbl 0442.05050 |
| [3] | Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc.2 (1952) 69-81. · Zbl 0047.17001 |
| [4] | Edmonds, J., Paths, trees and flowers, Cannad. J. Math.17 (1965) 449-467. · Zbl 0132.20903 |
| [5] | Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). · Zbl 0411.68039 |
| [6] | Hàn, H., Person, Y. and Schacht, M., On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math.23 (2009) 732-748. · Zbl 1191.05074 |
| [7] | Khan, I., Perfect matching in 3 uniform hypergraphs with large vertex degree, SIAM J. Discrete Math.27 (2013) 1021-1039. · Zbl 1272.05160 |
| [8] | Kühn, D. and Osthus, D., Matchings in hypergraphs of large minimum degree, J. Graph Theory51 (2006) 269-280. · Zbl 1087.05041 |
| [9] | Kühn, D., Osthus, D. and Treglowns, A., Matchings in 3-uniform hypergraphs, J. Combin. Theory Ser. B103 (2013) 291-305. · Zbl 1262.05128 |
| [10] | Markström, K. and Ruciński, A., Perfect matchings(and Hamilton cycles) in hypergraphs with large degrees, European J. Combin.32 (2011) 677-687. · Zbl 1229.05231 |
| [11] | Pikhurko, O., Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree, Graphs Combin.24 (2008) 391-404. · Zbl 1205.05184 |
| [12] | Rödl, V., Rucinski, A. and Szemerédi, E., Perfect matchings in uniform hypergraphs with large minimum degree, European J. Combin.27 (2006) 1333-1349. · Zbl 1104.05051 |
| [13] | Rödl, V., Rucinski, A. and Szemerédi, E., An approximate Dirac-type theorem for \(k\)-uniform hypergraphs, Combinatorica28 (2008) 229-260. · Zbl 1164.05051 |
| [14] | Rödl, V., Rucinski, A. and Szemerédi, E., Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A116 (2009) 613-636. · Zbl 1214.05130 |
| [15] | Treglown, A. and Zhao, Y., Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A119 (2012) 1500-1522. · Zbl 1305.05194 |
| [16] | Tutte, W. T., The factorization of linear graphs, J. Lond. Math. Soc.22 (1947) 107-111. · Zbl 0029.23301 |
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.
