More Web Proxy on the site http://driver.im/

research-article

Tiling multipartite hypergraphs in quasi-random hypergraphs

Authors:

Wenling ZhouAuthors Info & Claims

Volume 160, Issue C

Pages 36 - 65

https://doi.org/10.1016/j.jctb.2022.12.005

Published: 01 May 2023 Publication History

Abstract

Given k ≥ 2 and two k-graphs (k-uniform hypergraphs) F and H, an F-factor in H is a set of vertex disjoint copies of F that together covers the vertex set of H. Lenz and Mubayi studied the F-factor problems in quasi-random k-graphs with minimum degree Ω ( n k − 1 ). In particular, they constructed a sequence of 1/8-dense quasi-random 3-graphs H ( n ) with minimum degree Ω ( n 2 ) and minimum codegree Ω ( n ) but with no K 2, 2, 2-factor. We prove that if p > 1 / 8 and F is a 3-partite 3-graph with f vertices, then for sufficiently large n, all p-dense quasi-random 3-graphs of order n with minimum codegree Ω ( n ) and f | n have F-factors. That is, 1/8 is the density threshold for ensuring all 3-partite 3-graphs F-factors in quasi-random 3-graphs given a minimum codegree condition Ω ( n ). Moreover, we show that one can not replace the minimum codegree condition by a minimum vertex degree condition. In fact, we find that for any p ∈ ( 0, 1 ) and n ≥ n 0, there exist p-dense quasi-random 3-graphs of order n with minimum degree Ω ( n 2 ) having no K 2, 2, 2-factor. In particular, we study the optimal density threshold of F-factors for each 3-partite 3-graph F in quasi-random 3-graphs given a minimum codegree condition Ω ( n ).

In addition, we also study F-factor problems for k-partite k-graphs F with stronger quasi-random assumption and minimum degree Ω ( n k − 1 ).

References

[1]

E. Aigner-Horev, D. Conlon, H. Hàn, Y. Person, M. Schacht, Quasirandomness in hypergraphs, Electron. J. Comb. 25 (3) (2018).

[2]

F. Chung, Quasi-random hypergraphs revisited, Random Struct. Algorithms 40 (1) (2012) 39–48.

[3]

F.R.K. Chung, Quasi-random classes of hypergraphs, Random Struct. Algorithms 1 (4) (1990) 363–382.

[4]

F.R.K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Struct. Algorithms 2 (2) (1991) 241–252.

[5]

F.R.K. Chung, R.L. Graham, Quasi-random hypergraphs, Random Struct. Algorithms 1 (1) (1990) 105–124.

[6]

F.R.K. Chung, R.L. Graham, R.M. Wilson, Quasi-random graphs, Combinatorica 9 (4) (1989) 345–362.

[7]

D. Conlon, H. Hàn, Y. Person, M. Schacht, Weak quasi-randomness for uniform hypergraphs, Random Struct. Algorithms 40 (1) (2012) 1–38.

[8]

O. Cooley, N. Fountoulakis, D. Kühn, D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, Combinatorica 29 (3) (2009) 263–297.

[9]

K. Corradi, A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hung. 14 (1963) 423–439.

[10]

L. Ding, J. Han, S. Sun, G. Wang, W. Zhou, F-factors in quasi-random hypergraphs, J. Lond. Math. Soc. 2 (2022) 1–34.

[11]

P. Erdős, On extremal problems of graphs and generalized graphs, Isr. J. Math. 2 (1964) 183–190.

[12]

P. Erdős, A. Hajnal, On Ramsey like theorems. Problems and results, in: Combinatorics, Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972, 1972, pp. 123–140.

[13]

P. Erdős, V.T. Sós, On Ramsey-Turán type theorems for hypergraphs, Combinatorica 2 (3) (1982) 289–295.

[14]

R. Glebov, D. Král', J. Volec, A problem of Erdős and Sós on 3-graphs, Isr. J. Math. 211 (1) (2016) 349–366.

[15]

Glock, S.; Kühn, D.; Lo, A.; Osthus, D. (2016): The existence of designs via iterative absorption: hypergraph f-designs for arbitrary f . arXiv:1611.06827.

[16]

W.T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Comb. Probab. Comput. 15 (1–2) (2006) 143–184.

[17]

W.T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. Math. 166 (3) (2007) 897–946.

[18]

A. Hajnal, E. Szemerédi, Proof of a conjecture of P. Erdős, in: Combinatorial Theory and Its Applications, II, Proc. Colloq., Balatonfüred, 1969, 1970, pp. 601–623.

[19]

J. Han, Decision problem for perfect matchings in dense k-uniform hypergraphs, Trans. Am. Math. Soc. 369 (7) (2017) 5197–5218.

[20]

J. Han, On perfect matchings and tilings in uniform hypergraphs, SIAM J. Discrete Math. 32 (2) (2018) 919–932.

[21]

J. Han, A. Treglown, The complexity of perfect matchings and packings in dense hypergraphs, J. Comb. Theory, Ser. B 141 (2020) 72–104.

[22]

J. Han, C. Zang, Y. Zhao, Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs, J. Comb. Theory, Ser. A 149 (2017) 115–147.

[23]

A. Johansson, J. Kahn, V. Vu, Factors in random graphs, Random Struct. Algorithms 33 (1) (2008) 1–28.

[24]

Keevash, P. (2014): The existence of designs. arXiv:1401.3665.

[25]

P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, Mem. Am. Math. Soc. 233 (1098) (2015) vi+95.

[26]

Y. Kohayakawa, B. Nagle, V. Rödl, M. Schacht, Weak hypergraph regularity and linear hypergraphs, J. Comb. Theory, Ser. B 100 (2) (2010) 151–160.

[27]

Y. Kohayakawa, V. Rödl, J. Skokan, Hypergraphs, quasi-randomness, and conditions for regularity, J. Comb. Theory, Ser. A 97 (2) (2002) 307–352.

[28]

J. Komlós, G.N. Sárközy, E. Szemerédi, Blow-up lemma, Combinatorica 17 (1) (1997) 109–123.

[29]

D. Kühn, R. Mycroft, D. Osthus, Hamilton l-cycles in uniform hypergraphs, J. Comb. Theory, Ser. A 117 (7) (2010) 910–927.

[30]

J. Lenz, D. Mubayi, Eigenvalues and linear quasirandom hypergraphs, Forum Math. Sigma 3 (e2) (2015) 26.

[31]

J. Lenz, D. Mubayi, The poset of hypergraph quasirandomness, Random Struct. Algorithms 46 (4) (2015) 762–800.

[32]

J. Lenz, D. Mubayi, Perfect packings in quasirandom hypergraphs I, J. Comb. Theory, Ser. B 119 (2016) 155–177.

[33]

J. Lenz, D. Mubayi, Perfect packings in quasirandom hypergraphs II, Comb. Probab. Comput. 25 (4) (2016) 595–611.

[34]

A. Lo, K. Markström, F-factors in hypergraphs via absorption, Graphs Comb. 31 (3) (2015) 679–712.

[35]

R. Mycroft, Packing k-partite k-uniform hypergraphs, J. Comb. Theory, Ser. A 138 (2016) 60–132.

[36]

C. Reiher, V. Rödl, M. Schacht, Embedding tetrahedra into quasirandom hypergraphs, J. Comb. Theory, Ser. B 121 (2016) 229–247.

[37]

C. Reiher, V. Rödl, M. Schacht, Hypergraphs with vanishing Turán density in uniformly dense hypergraphs, J. Lond. Math. Soc. (2) 97 (1) (2018) 77–97.

[38]

C. Reiher, V. Rödl, M. Schacht, On a generalisation of Mantel's theorem to uniformly dense hypergraphs, Int. Math. Res. Not. 16 (2018) 4899–4941.

[39]

C. Reiher, V. Rödl, M. Schacht, On a Turán problem in weakly quasirandom 3-uniform hypergraphs, J. Eur. Math. Soc. 20 (5) (2018) 1139–1159.

[40]

C. Reiher, V. Rödl, M. Schacht, Some remarks on ▪, in: Connections in Discrete Mathematics, 2018, pp. 214–239.

[41]

C. Reiher, M. Schacht, Clique factors in locally dense graphs, Random Struct. Algorithms 49 (4) (2016) 669–693. Appendix to Triangle factors of graphs without large independent sets and of weighted graphs by J. Balogh, T. Molla and M. Sharifzadeh.

[42]

V. Rödl, A. Ruciński, E. Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, Comb. Probab. Comput. 15 (1–2) (2006) 229–251.

[43]

V. Rödl, M. Schacht, Regular partitions of hypergraphs: counting lemmas, Comb. Probab. Comput. 16 (6) (2007) 887–901.

[44]

V. Rödl, M. Schacht, Regular partitions of hypergraphs: regularity lemmas, Comb. Probab. Comput. 16 (6) (2007) 833–885.

[45]

V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Struct. Algorithms 25 (1) (2004) 1–42.

[46]

K. Staden, A. Treglown, The bandwidth theorem for locally dense graphs, Forum Math. Sigma 8 (2020).

[47]

H. Towsner, σ-algebras for quasirandom hypergraphs, Random Struct. Algorithms 50 (1) (2017) 114–139.

[48]

Y. Zhao, Recent advances on Dirac-type problems for hypergraphs, in: Recent Trends in Combinatorics, in: IMA Vol. Math. Appl., vol. 159, 2016, pp. 145–165.

Recommendations

Perfect packings in quasirandom hypergraphs I

Let k 2 and F be a linear k-uniform hypergraph with v vertices. We prove that if n is sufficiently large and v | n , then every quasirandom k-uniform hypergraph on n vertices with constant edge density and minimum degree ( n k - 1 ) admits a perfect F-...
On the Number of Linear Multipartite Hypergraphs with Given Size
Abstract
For any given integer $r ⩾ 3$ , let $k = k (n)$ be an integer with $r ⩽ k ⩽ n$ . A hypergraph is r-uniform if each edge is a set of r vertices, and is said to be linear if two edges intersect in at most one vertex. Let $A_{1}, \dots, A_{k}$ be a given k-partition of [n] with $| A_{...}_{}$ $_{}$ $^{\frac{}{}}$ $^{\frac{}{}}$
On Perfect Matchings and Tilings in Uniform Hypergraphs

In this paper we study some variants of Dirac-type problems in hypergraphs. First, we show that for $k\ge 3$, if $H$ is a $k$-graph on $n\in k\mathbb N$ vertices with independence number at most $n/p$ and minimum codegree at least $(1/p+o(1))n$, where $p$...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Theory Series B

Journal of Combinatorial Theory Series B Volume 160, Issue C

May 2023

215 pages

ISSN:0095-8956

Issue’s Table of Contents

Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 May 2023

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents