Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T19:50:48.877Z Has data issue: false hasContentIssue false
  • English
  • Français

Perfect Packings in Quasirandom Hypergraphs II

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  27 October 2015

JOHN LENZ  and
DHRUV MUBAYI
JOHN LENZ
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, IL 60607, USA (e-mail: lenz@math.uic.edu, mubayi@uic.edu)
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, IL 60607, USA (e-mail: lenz@math.uic.edu, mubayi@uic.edu)
Rights & Permissions [Opens in a new window]

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.

For each of the notions of hypergraph quasirandomness that have been studied, we identify a large class of hypergraphs F so that every quasirandom hypergraph H admits a perfect F-packing. An informal statement of a special case of our general result for 3-uniform hypergraphs is as follows. Fix an integer r ⩾ 4 and 0 < p < 1. Suppose that H is an n-vertex triple system with r|n and the following two properties:

  • • for every graph G with V(G) = V(H), at least p proportion of the triangles in G are also edges of H,

  • • for every vertex x of H, the link graph of x is a quasirandom graph with density at least p.

Then H has a perfect Kr(3)-packing. Moreover, we show that neither of the hypotheses above can be weakened, so in this sense our result is tight. A similar conclusion for this special case can be proved by Keevash's Hypergraph Blow-up Lemma, with a slightly stronger hypothesis on H.

MSC classification

Primary: 05C65: Hypergraphs
Secondary: 05C70: Factorization, matching, partitioning, covering and packing 05D40: Probabilistic methods
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 4 , July 2016 , pp. 595 - 611
Copyright
Copyright © Cambridge University Press 2015 

References

[1] Alon, N. and Yuster, R. (1996) H-factors in dense graphs. J. Combin. Theory Ser. B 66 269–282.Google Scholar
[2] Chung, F. (2012) Quasi-random hypergraphs revisited. Random Struct. Alg. 40 39–48.Google Scholar
[3] Chung, F. R. K. (1990) Quasi-random classes of hypergraphs. Random Struct. Alg. 1 363–382.CrossRefGoogle Scholar
[4] Chung, F. R. K. and Graham, R. L. (1990) Quasi-random hypergraphs. Random Struct. Alg. 1 105–124.Google Scholar
[5] Chung, F. R. K. and Graham, R. L. (1991) Quasi-random set systems. J. Amer. Math. Soc. 4 151–196.Google Scholar
[6] Chung, F. R. K. and Graham, R. L. (1992) Cohomological aspects of hypergraphs. Trans. Amer. Math. Soc. 334 365–388.Google Scholar
[7] Chung, F. R. K., Graham, R. L. and Wilson, R. M. (1989) Quasi-random graphs. Combinatorica 9 345–362.Google Scholar
[8] Conlon, D., Hàn, H., Person, Y. and Schacht, M. (2012) Weak quasi-randomness for uniform hypergraphs. Random Struct. Alg. 40 1–38.Google Scholar
[9] Czygrinow, A., DeBiasio, L. and Nagle, B. (2014) Tiling 3-uniform hypergraphs with k 4 3 - 2e. J. Graph Theory, 75 124–136.Google Scholar
[10] Dellamonica, D. Jr and Rödl, V. (2011) Hereditary quasirandom properties of hypergraphs. Combina-torica 31 165–182.CrossRefGoogle Scholar
[11] Hajnal, 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
[12] Hàn, H., Person, Y. and Schacht, M. (2009) On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math. 23 732–748.Google Scholar
[13] Keevash, P. The existence of designs. arXiv:1401.3665 Google Scholar
[14] Keevash, P. (2011) A Hypergraph Blow-up Lemma. Random Struct. Alg. 39 275–376.Google Scholar
[15] Keevash, P. and Mycroft, R. (2015) A geometric theory for hypergraph matching. Mem. Amer. Math. Soc., 233 1098, vi+95 pp. ISBN: 978-1-4704-0965.Google Scholar
[16] Khan, I. Perfect matchings in 4-uniform hypergraphs. arXiv:1101.5675 Google Scholar
[17] Khan, I. (2013) Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27 1021–1039.Google Scholar
[18] Kohayakawa, Y., Nagle, B., Rödl, V. and Schacht, M. (2010) Weak hypergraph regularity and linear hypergraphs. J. Combin. Theory Ser. B 100 151–160.CrossRefGoogle Scholar
[19] Kohayakawa, Y., Rödl, V. and Skokan, J. (2002) Hypergraphs, quasi-randomness, and conditions for regularity. J. Combin. Theory Ser. A 97 307–352.Google Scholar
[20] Komlós, J., Sárközy, G. N. and Szemerédi, E. (1997) Blow-up Lemma. Combinatorica 17 109–123.Google Scholar
[21] Komlós, J., Sárközy, G. N. and Szemerédi, E. (2001) Proof of the Alon–Yuster conjecture. Discrete Math. 235 255–269.Google Scholar
[22] 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.Google Scholar
[23] Kühn, D. and Osthus, D. (2009) The minimum degree threshold for perfect graph packings. Combinatorica 29 65–107.Google Scholar
[24] Kühn, D., Osthus, D. and Townsend, T. (2014) Fractional and integer matchings in uniform hypergraphs. European J. Combin. 38 83–96.Google Scholar
[25] Kühn, D., Osthus, D. and Treglown, A. (2013) Matchings in 3-uniform hypergraphs. J. Combin. Theory Ser. B 103 291–305.Google Scholar
[26] Lenz, J. and Mubayi, D. Eigenvalues of non-regular linear-quasirandom hypergraphs. Discrete Math., arXiv:1309.3584 Google Scholar
[27] Lenz, J. and Mubayi, D. Perfect packings in quasirandom hypergraphs. J. Combin. Theory Ser. B, to appear. arXiv:1402.0884 Google Scholar
[28] Lenz, J. and Mubayi, D. The poset of hypergraph quasirandomness. Random Struct. Alg., to appear. arXiv:1208.5978 Google Scholar
[29] Lenz, J. and Mubayi, D. (2015) Eigenvalues and linear quasirandom hypergraphs. Forum of Mathematics, Sigma 3.CrossRefGoogle Scholar
[30] Lo, A. and Markström, K. F-factors in hypergraphs via absorption. Graphs Combin. 31 (3), 679–712.CrossRefGoogle Scholar
[31] Lo, A. and Markström, K. (2013) Minimum codegree threshold for (K 4 3-e)-factors. J. Combin. Theory Ser. A 120 708–721.CrossRefGoogle Scholar
[32] Markström, K. and Ruciński, A. (2011) Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees. European J. Combin. 32 677–687.Google Scholar
[33] Pikhurko, O. (2008) Perfect matchings and K 3 4-tilings in hypergraphs of large codegree. Graphs Combin. 24 391–404.Google Scholar
[34] Rödl, V., Ruciński, A. and Szemerédi, E. (2009) Perfect matchings in large uniform hypergraphs with large minimum collective degree. J. Combin. Theory Ser. A 116 613–636.CrossRefGoogle Scholar
[35] Shapira, A. and Yuster, R. (2012) The quasi-randomness of hypergraph cut properties. Random Struct. Alg. 40 105–131.Google Scholar
[36] Thomason, A. (1987) Pseudorandom graphs. In Random Graphs '85, Vol. 144 of North-Holland Mathematics Studies, North-Holland, pp. 307–331.Google Scholar
[37] Thomason, A. (1987) Random graphs, strongly regular graphs and pseudorandom graphs. In Surveys in Combinatorics 1987, Vol. 123 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 173–195.Google Scholar
[38] Towsner, H. Sigma-algebras for quasirandom hypergraphs. Random Struct. Alg., arXiv:1312.4882 Google Scholar
[39] Treglown, A. and Zhao, Y. (2012) Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. J. Combin. Theory Ser. A 119 1500–1522.Google Scholar
[40] Treglown, A. and Zhao, Y. (2013) Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II. J. Combin. Theory Ser. A 120 1463–1482.Google Scholar