Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-16T22:23:00.259Z Has data issue: false hasContentIssue false

Covering and tiling hypergraphs with tight cycles

Published online by Cambridge University Press:  13 October 2020

Jie Han
Affiliation:
Department of Mathematics, University of Rhode Island, Kingston, RI 02881, USA
Allan Lo
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK
Nicolás Sanhueza-Matamala*
Affiliation:
School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK
*
*Corresponding author. Email: [email protected]

Abstract

A k-uniform tight cycle $C_s^k$ is a hypergraph on s > k vertices with a cyclic ordering such that every k consecutive vertices under this ordering form an edge. The pair (k, s) is admissible if gcd (k, s) = 1 or k / gcd (k,s) is even. We prove that if $s \ge 2{k^2}$ and H is a k-uniform hypergraph with minimum codegree at least (1/2 + o(1))|V(H)|, then every vertex is covered by a copy of $C_s^k$. The bound is asymptotically sharp if (k, s) is admissible. Our main tool allows us to arbitrarily rearrange the order in which a tight path wraps around a complete k-partite k-uniform hypergraph, which may be of independent interest.

For hypergraphs F and H, a perfect F-tiling in H is a spanning collection of vertex-disjoint copies of F. For $k \ge 3$, there are currently only a handful of known F-tiling results when F is k-uniform but not k-partite. If s ≢ 0 mod k, then $C_s^k$ is not k-partite. Here we prove an F-tiling result for a family of non-k-partite k-uniform hypergraphs F. Namely, for $s \ge 5{k^2}$, every k-uniform hypergraph H with minimum codegree at least (1/2 + 1/(2s) + o(1))|V(H)| has a perfect $C_s^k$-tiling. Moreover, the bound is asymptotically sharp if k is even and (k, s) is admissible.

Type
Paper
Copyright
© The Author(s), 2020. Published by Cambridge University Press

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.)

Footnotes

The research leading to these results was partially supported by FAPESP (Proc. 2013/03447-6, 2014/18641-5, 2015/07869-8) (J. Han) EPSRC, grant EP/P002420/1 (A. Lo) and the Becas Chile scholarship scheme from CONICYT (N. Sanhueza-Matamala).

References

Abbasi, S. (1998) The solution of the El-Zahar problem. PhD thesis, Rutgers University.Google Scholar
Allen, P., Böttcher, J., Cooley, O. and Mycroft, R. (2017) Tight cycles and regular slices in dense hypergraphs. J. Combin. Theory Ser. A 149 30–100.Google Scholar
Alon, N. and Yuster, R. (1996) H-factors in dense graphs. J. Combin. Theory Ser. B 66 269–282.Google Scholar
Cooley, O., Fountoulakis, N., Kühn, D. and Osthus, D. (2009) Embeddings and Ramsey numbers of sparse k-uniform hypergraphs. Combinatorica 29 263–297.CrossRefGoogle Scholar
Corrádi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Hungar. 14 423–439.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. and Nagle, B. (2001) A note on codegree problems for hypergraphs. Bull. Inst. Combin. Appl. 32 63–69.Google Scholar
Dirac, G. A. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. 3 69–81.Google Scholar
El-Zahar, M. H. (1984) On circuits in graphs. Discrete Math. 50 227–230.CrossRefGoogle Scholar
Erdős, P. (1964) On extremal problems of graphs and generalized graphs. Israel J. Math. 2 183–190.Google Scholar
Falgas-Ravry, V. and Zhao, Y. (2016) Codegree thresholds for covering 3-uniform hypergraphs. SIAM J. Discrete Math. 30 1899–1917.Google Scholar
Gao, W., Han, J. and Zhao, Y. (2019) Codegree conditions for tiling complete k-partite k-graphs and loose cycles. Combin. Probab. Comput. 28 840–870.Google Scholar
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), pp. 601–623. North-Holland.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.Google Scholar
Haxell, P. E., Łuczak, T., Peng, Y., Rödl, V., Ruciński, A. and Skokan, J. (2009) The Ramsey number for 3-uniform tight hypergraph cycles. Combin. Probab. Comput. 18 165–203.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience.CrossRefGoogle Scholar
Keevash, P. and Mycroft, R. (2015) A Geometric Theory for Hypergraph Matching, Vol. 233, no. 1098 of Memoirs of the American Mathematical Society. AMS.CrossRefGoogle Scholar
Komlós, J. (2000) Tiling Turán theorems. Combinatorica 20 203–218.CrossRefGoogle 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ővári, T., Sós, V. and Turán, P. (1954) On a problem of K. Zarankiewicz. Colloq. Math. 3 50–57.Google Scholar
Kühn, D., Mycroft, R. and Osthus, D. (2010) Hamilton -cycles in uniform hypergraphs. J. Combin. Theory Ser. A 117 910–927.Google Scholar
Kühn, D. and Osthus, D. (2006) Matchings in hypergraphs of large minimum degree. J. Graph Theory 51 269–280.CrossRefGoogle Scholar
Lo, A. and Markström, K. (2015) F-factors in hypergraphs via absorption. Graphs Combin. 31 679–712.CrossRefGoogle Scholar
Mycroft, R. (2016) Packing k-partite k-uniform hypergraphs. J. Combin. Theory Ser. A 138 60–132.Google Scholar
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.Google Scholar
Szemerédi, E. (2013) Is laziness paying off? (‘absorbing’ method). In Colloquium De Giorgi 2010–2012 (U. Zannier, ed.), pp. 17–34. Scuola Normale Superiore, Pisa.CrossRefGoogle Scholar
Wang, H. (2010) Proof of the Erdős–Faudree conjecture on quadrilaterals. Graphs Combin. 26 833–877.CrossRefGoogle Scholar
Wang, H. (2012) Disjoint 5-cycles in a graph. Discuss. Math. Graph Theory 32 221–242.CrossRefGoogle Scholar
Zhao, Y. (2016) Recent advances on Dirac-type problems for hypergraphs. In Recent Trends in Combinatorics (A. Beveridge et al., eds), pp. 145–165. Springer.CrossRefGoogle Scholar