Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-14T03:21:46.687Z 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: [email protected], [email protected])
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, IL 60607, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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