Nothing Special   »   [go: up one dir, main page]

skip to main content
rapid-communication

A note on minimum degree condition for Hamilton (a,b)-cycles in hypergraphs

Published: 01 January 2023 Publication History

Abstract

Let k, a, b be positive integers with a + b = k. A k-uniform hypergraph is called an ( a, b )-cycle if there is a partition ( A 0, B 0, A 1, B 1, …, A t − 1, B t − 1 ) of the vertex set with | A i | = a, | B i | = b such that A i ∪ B i and B i ∪ A i + 1 (subscripts module t) are edges for all i = 0, 1, …, t − 1. Let H be a k-uniform n-vertex hypergraph with n ≥ 5 k and n divisible by k. By applying the concentration inequality for intersections of a uniform hypergraph with a random matching developed by Frankl and Kupavskii, we show that if there exists α ∈ ( 0, 1 ) such that δ a ( H ) ≥ ( α + o ( 1 ) ) ( n − a b ) and δ b ( H ) ≥ ( 1 − α + o ( 1 ) ) ( n − b a ), then H contains a Hamilton ( a, b )-cycle. As a corollary, we prove that if δ ℓ ( H ) ≥ ( 1 / 2 + o ( 1 ) ) ( n − ℓ k − ℓ ) for some ℓ ≥ k / 2, then H contains a Hamilton ( k − ℓ, ℓ )-cycle and this is asymptotically best possible.

References

[1]
G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. 2 (1952) 69–81.
[2]
Frankl, P.; Kupavskii, A. : The Erdős matching conjecture and concentration inequalities. arXiv:1806.08855.
[3]
H. Hàn, J. Han, Y. Zhao, Minimum degree thresholds for Hamilton ( k / 2 )-cycles in k-uniform hypergraphs, J. Comb. Theory, Ser. B 153 (2022) 105–148.
[4]
G. Katona, H. Kierstead, Hamiltonian chains in hypergraphs, J. Graph Theory 30 (1999) 205–212.
[5]
D. Kühn, D. Osthus, Hamilton cycles in graphs and hypergraphs: an extremal perspective, in: Proceedings of the International Congress of Mathematicians, 2014, pp. 381–406.
[6]
J. Moon, L. Moser, On Hamiltonian bipartite graphs, Isr. J. Math. 1 (1963) 163–165.
[7]
O. Pikhurko, Perfect matchings and K 4 3-tilings in hypergraphs of large codegree, Graphs Comb. 24 (2008) 391–404.
[8]
V. Rödl, A. Ruciński, Dirac-type questions for hypergraphs–a survey (or more problems for endre to solve), in: An Irregular Mind, in: Bolyai Soc. Math. Studies, vol. 21, 2010, pp. 561–590.
[9]
V. Rödl, A. Ruciński, E. Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, Comb. Probab. Comput. 15 (2006) 229–251.
[10]
V. Rödl, A. Ruciński, E. Szemerédi, An approximate Dirac-type theorem for k-uniform hypergraphs, Combinatorica 28 (2008) 229–260.
[11]
A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Comb. Theory, Ser. A 119 (2012) 1500–1522.
[12]
A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II, J. Comb. Theory, Ser. A 120 (2013) 1463–1482.
[13]
Y. Zhao, Recent advances on Dirac-type problems for hypergraphs, in: Recent Trends in Combinatorics, 2016, pp. 145–165.
Index terms have been assigned to the content through auto-classification.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Mathematics
Discrete Mathematics  Volume 346, Issue 1
Jan 2023
955 pages

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 January 2023

Author Tags

  1. Dirac type result
  2. Minimum d-degree
  3. The probabilistic method
  4. Concentration inequalities

Qualifiers

  • Rapid-communication

Contributors

Other 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 05 Mar 2025

Other Metrics

Citations

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media