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

  1. A note on minimum degree condition for Hamilton (a,b)-cycles in hypergraphs
        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 13 Nov 2024

        Other Metrics

        Citations

        View Options

        View options

        Get Access

        Login options

        Media

        Figures

        Other

        Tables

        Share

        Share

        Share this Publication link

        Share on social media