No CrossRef data available.
Article contents
Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles
Part of:
Graph theory
Published online by Cambridge University Press: 09 July 2019
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
Given two k-graphs (k-uniform hypergraphs) F and H, a perfect F-tiling (or F-factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H. For all complete k-partite k-graphs K, Mycroft proved a minimum codegree condition that guarantees a K-factor in an n-vertex k-graph, which is tight up to an error term o(n). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K(k)(1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.
MSC classification
Secondary:
05C65: Hypergraphs
Information
- Type
- Paper
- Information
- Copyright
- © Cambridge University Press 2019
Footnotes
†
Supported by FAPESP (Proc. 2013/03447-6, 2014/18641-5, 2015/07869-8) and Simons Foundation Collaboration Grant # 630884.
‡
Partially supported by NSF grants DMS-1400073 and DMS 1700622.
References
Alon, N. and Yuster, R. (1996) H-factors in dense graphs. J. Combin. Theory Ser. B 66 269–282.CrossRefGoogle Scholar
Buß, E., Hàn, H. and Schacht, M. (2013) Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs. J. Combin. Theory Ser. B 103 658–678.CrossRefGoogle Scholar
Chvátal, V. (1983) Linear Programming, A Series of Books in the Mathematical Sciences, Freeman.Google Scholar
Czygrinow, A. (2016). Tight co-degree condition for packing of loose cycles in 3-graphs. J. Graph Theory 83 317–333.CrossRefGoogle Scholar
Czygrinow, A., DeBiasio, L. and Nagle, B. (2014) Tiling 3-uniform hypergraphs with 
$K_4^3$ − 2e. J. Graph Theory 75 124–136.CrossRefGoogle Scholar
$K_4^3$ − 2e. J. Graph Theory 75 124–136.CrossRefGoogle ScholarErdös, P. (1964) On extremal problems of graphs and generalized graphs. Israel J. Math. 2 183–190.CrossRefGoogle Scholar
Erdös, P. and Graham, R. L. (1972) On a linear diophantine problem of Frobenius. Acta Arith. 21 399–408.CrossRefGoogle Scholar
Frankl, P. and Füredi, Z. (1985). Forbidding just one intersection. J. Combin. Theory Ser. A 39 160–176.CrossRefGoogle Scholar
Gao, W. and Han, J. (2017) Minimum codegree threshold for $$\mathop C\nolimits_6^3 $$-factors in 3-uniform hypergraphs. Combin. Probab. Comput. 26 536–559.CrossRefGoogle Scholar
$$\mathop C\nolimits_6^3 $$-factors in 3-uniform hypergraphs. Combin. Probab. Comput. 26 536–559.CrossRefGoogle ScholarHajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdös. In Combinatorial Theory and its Applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, pp. 601–623.Google Scholar
Hàn, H. and Schacht, M. (2010) Dirac-type results for loose Hamilton cycles in uniform hypergraphs. J. Combin. Theory Ser. B 100 332–346.CrossRefGoogle Scholar
Han, J. (2017) Decision problem for perfect matchings in dense k-uniform hypergraphs. Trans. Amer. Math. Soc. 369 5197–5218.CrossRefGoogle Scholar
Han, J., Lo, A., Treglown, A. and Zhao, Y. (2017) Exact minimum codegree threshold for $$\mathop K\nolimits_4^ - $$-factors. Combin. Probab. Comput. 26 856–885.CrossRefGoogle Scholar
$$\mathop K\nolimits_4^ - $$-factors. Combin. Probab. Comput. 26 856–885.CrossRefGoogle ScholarHan, J. and Treglown, A. The complexity of perfect matchings and packings in dense graphs and hypergraphs. J. Combin. Theory Ser. B, to appear. Preprint.Google Scholar
Han, J., Zang, C. and Zhao, Y. (2017) Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs. J. Combin. Theory Ser. A 149 115–147.CrossRefGoogle Scholar
Han, J. and Zhao, Y. (2015) Minimum vertex degree threshold for $\mathop C\nolimits_4^3 $-tiling. J. Graph Theory 79 300–317.CrossRefGoogle Scholar
$\mathop C\nolimits_4^3 $-tiling. J. Graph Theory 79 300–317.CrossRefGoogle ScholarHuxley, M. N. and Iwaniec, H. (1975) Bombieri’s theorem in short intervals. Mathematika 22 188–194.CrossRefGoogle Scholar
Keevash, P. The existence of designs. Preprint.Google Scholar
Keevash, P. and Mycroft, R. (2015) A Geometric Theory for Hypergraph Matching, Vol. 233 of Memoirs of the American Mathematical Society, AMS.Google Scholar
Komlós, J., Sárközy, G. and Szemerédi, E. (2001) Proof of the Alon-Yuster conjecture. Discrete Math. 235 255–269.CrossRefGoogle Scholar
Kühn, D. and Osthus, D. (2006) Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree. J. Combin. Theory Ser. B 96 767–821.CrossRefGoogle Scholar
Kühn, D. and Osthus, D. (2009) Embedding large subgraphs into dense graphs. In Surveys in Combinatorics 2009, Vol. 365 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 137–167.CrossRefGoogle Scholar
Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65–107.CrossRefGoogle Scholar
Lo, A. and Markström, K. (2013), Minimum codegree threshold for $$\left( {\mathop K\nolimits_4^3 - e} \right)$$-factors. J. Combin. Theory Ser. A 120 708–721.CrossRefGoogle Scholar
$$\left( {\mathop K\nolimits_4^3 - e} \right)$$-factors. J. Combin. Theory Ser. A 120 708–721.CrossRefGoogle ScholarLo, A. and Markström, K. (2015) F-factors in hypergraphs via absorption. Graphs Combin. 31 679–712.CrossRefGoogle Scholar
Lu, L. and Székely, L. (2007) Using Lovász local lemma in the space of random injections. Electron. J. Combin. 13 R63.Google Scholar
Mubayi, D. (2002), Some exact results and new asymptotics for hypergraph Turán numbers. Combin. Probab. Comput. 11 299–309.CrossRefGoogle Scholar
Mycroft, R. (2016) Packing k-partite k-uniform hypergraphs. J. Combin. Theory Ser. A 138 60–132.CrossRefGoogle Scholar
Rödl, V. and Ruciński, A. (2010) Dirac-type questions for hypergraphs: A survey (or more problems for Endre to solve). In An Irregular Mind: Szemerédi is 70, Vol. 21 of Bolyai Society Mathematical Studies, Springer, pp. 561–590.CrossRefGoogle Scholar
Rödl, V., Ruciński, A. and Szemerédi, E. (2006) A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput. 15 229–251.CrossRefGoogle Scholar
Szemerédi, E. (1978) Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Vol. 260 of Colloq. Internat. CNRS, CNRS, Paris, pp. 399–401.Google Scholar
Vitek, Y. (1975) Bounds for a linear diophantine problem of Frobenius. J. London Math. Soc. (2) 10 79–85.CrossRefGoogle Scholar
Zhao, Y. (2015) Recent advances on Dirac-type problems for hypergraphs. In Recent Trends in Combinatorics, Vol. 159 of the IMA Volumes in Mathematics and its Applications, Springer.Google Scholar
You have
Access
- 4
- Cited by