Hamiltonicity in randomly perturbed hypergraphs. (English) Zbl 1443.05109
Summary: For integers \(k \geq 3\) and \(1 \leq \ell \leq k - 1\), we prove that for any \(\alpha > 0\), there exist \(\epsilon > 0\) and \(C > 0\) such that for sufficiently large \(n \in(k - \ell) \mathbb{N}\), the union of a \(k\)-uniform hypergraph with minimum vertex degree \(\alpha n^{k - 1}\) and a binomial random \(k\)-uniform hypergraph \(\mathbb{G}^{(k)}(n, p)\) with \(p \geq n^{-(k - \ell) - \epsilon}\) for \(\ell \geq 2\) and \(p \geq C n^{-(k - 1)}\) for \(\ell = 1\) on the same vertex set contains a Hamiltonian \(\ell\)-cycle with high probability. Our result is best possible up to the values of \(\epsilon\) and \(C\) and answers a question of M. Krivelevich et al. [SIAM J. Discrete Math. 31, No. 1, 155–171 (2017; Zbl 1354.05122)].
MSC:
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C65 | Hypergraphs |
Citations:
Zbl 1354.05122References:
| [1] | Balogh, J.; Treglown, A.; Wagner, A. Z., Tilings in randomly perturbed dense graphs, Comb. Probab. Comput., 28, 159-176 (2019) · Zbl 1434.05129 |
| [2] | Bastos, J. O.; Mota, G. O.; Schacht, M.; Schnitzer, J.; Schulenburg, F., Loose Hamiltonian cycles forced by large \((k - 2)\)-degree - approximation version, SIAM J. Discrete Math., 31, 2328-2347 (2017) · Zbl 1372.05152 |
| [3] | Bastos, J. O.; Mota, G. O.; Schacht, M.; Schnitzer, J.; Schulenburg, F., Loose Hamiltonian cycles forced by large \((k - 2)\)-degree - sharp version, Contrib. Discrete Math., 13, 2 (2018) · Zbl 1378.05151 |
| [4] | Bedenknecht, W.; Han, J.; Kohayakawa, Y.; Mota, G. O., Powers of tight Hamilton cycles in randomly perturbed hypergraphs, Random Struct. Algorithms, 55, 4, 795-807 (2019) · Zbl 1433.05178 |
| [5] | Bennett, P.; Dudek, A.; Frieze, A., Adding random edges to create the square of a Hamilton cycle, ArXiv e-prints (2017), available at |
| [6] | Bohman, Tom; Frieze, Alan; Martin, Ryan, How many random edges make a dense graph Hamiltonian?, Random Struct. Algorithms, 22, 1, 33-42 (2003) · Zbl 1013.05044 |
| [7] | Böttcher, J.; Han, J.; Kohayakawa, Y.; Montgomery, R.; Parczyk, O.; Person, Y., Universality of bounded degree spanning trees in randomly perturbed graphs, Random Struct. Algorithms, 55, 4, 854-864 (2019) · Zbl 1433.05275 |
| [8] | J. Böttcher, R. Montgomery, O. Parczyk, Y. Person, Embedding spanning bounded degree subgraphs in randomly perturbed graphs, preprint. · Zbl 1378.05111 |
| [9] | Buß, E.; Hàn, H.; Schacht, M., Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs, J. Comb. Theory, Ser. B, 103, 6, 658-678 (2013) |
| [10] | Czygrinow, A.; Molla, T., Tight codegree condition for the existence of loose Hamilton cycles in 3-graphs, SIAM J. Discrete Math., 28, 1, 67-76 (2014) · Zbl 1296.05113 |
| [11] | Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., s3-2, 1, 69-81 (1952) · Zbl 0047.17001 |
| [12] | Dudek, Andrzej; Frieze, Alan, Loose Hamilton cycles in random uniform hypergraphs, Electron. J. Comb., 18, 1, Article 48 pp. (2011) · Zbl 1218.05174 |
| [13] | Dudek, Andrzej; Frieze, Alan, Tight Hamilton cycles in random uniform hypergraphs, Random Struct. Algorithms, 42, 3, 374-385 (2013) · Zbl 1264.05078 |
| [14] | Glebov, R.; Person, Y.; Weps, W., On extremal hypergraphs for Hamiltonian cycles, Eur. J. Comb., 33, 4, 544-555 (2012) · Zbl 1237.05142 |
| [15] | Han, J.; Zhao, Y., Minimum codegree threshold for Hamilton ℓ-cycles in k-uniform hypergraphs, J. Comb. Theory, Ser. A, 132, 194-223 (2015) · Zbl 1307.05133 |
| [16] | Han, J.; Zhao, Y., Minimum degree thresholds for loose Hamilton cycle in 3-graphs, J. Comb. Theory, Ser. B, 114, 70-96 (2015) · Zbl 1315.05095 |
| [17] | Hàn, H.; Schacht, M., Dirac-type results for loose Hamilton cycles in uniform hypergraphs, J. Comb. Theory, Ser. B, 100, 332-346 (2010) · Zbl 1209.05161 |
| [18] | Janson, Svante; Łuczak, Tomasz; Rucinski, Andrzej, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (2000), Wiley-Interscience: Wiley-Interscience New York · Zbl 0968.05003 |
| [19] | Karp, Richard M., Reducibility among combinatorial problems, (Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) (1972), Plenum: Plenum New York), 85-103 · Zbl 1467.68065 |
| [20] | Keevash, P.; Kühn, D.; Mycroft, R.; Osthus, D., Loose Hamilton cycles in hypergraphs, Discrete Math., 311, 7, 544-559 (2011) · Zbl 1226.05187 |
| [21] | Koršunov, A. D., Solution of a problem of P. Erdős and A. Rényi on Hamiltonian cycles in nonoriented graphs, Diskretn. Anal., 31, 17-56 (1977), 90 · Zbl 0407.05060 |
| [22] | Krivelevich, Michael; Kwan, Matthew; Sudakov, Benny, Cycles and matchings in randomly perturbed digraphs and hypergraphs, Comb. Probab. Comput., 25, 6, 909-927 (2016) · Zbl 1372.05202 |
| [23] | Krivelevich, Michael; Kwan, Matthew; Sudakov, Benny, Bounded-degree spanning trees in randomly perturbed graphs, SIAM J. Discrete Math., 31, 1, 155-171 (2017) · Zbl 1354.05122 |
| [24] | Kühn, D.; Mycroft, R.; Osthus, D., Hamilton ℓ-cycles in uniform hypergraphs, J. Comb. Theory, Ser. A, 117, 7, 910-927 (2010) · Zbl 1219.05107 |
| [25] | Kühn, D.; Osthus, D., Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree, J. Comb. Theory, Ser. B, 96, 6, 767-821 (2006) · Zbl 1109.05065 |
| [26] | McDowell, A.; Mycroft, R., Hamilton ℓ-cycles in randomly perturbed hypergraphs, Electron. J. Comb., 25 (2018), P4.36 · Zbl 1402.05161 |
| [27] | Pósa, L., Hamiltonian circuits in random graphs, Discrete Math., 14, 4, 359-364 (1976) · Zbl 0322.05127 |
| [28] | Reiher, Christian; Rödl, Vojtěch; Ruciński, Andrzej; Schacht, Mathias; Szemerédi, Endre, Minimum vertex degree condition for tight Hamiltonian cycles in 3-uniform hypergraphs, Proc. Lond. Math. Soc., 119, 2, 409-439 (2019) · Zbl 1422.05077 |
| [29] | Rödl, V.; Ruciński, Andrzej, Dirac-type questions for hypergraphs—a survey (or more problems for Endre to solve), (An Irregular Mind. An Irregular Mind, Bolyai Soc. Math. Stud., vol. 21 (2010), János Bolyai Math. Soc.: János Bolyai Math. Soc. Budapest) · Zbl 1221.05255 |
| [30] | Rödl, V.; Ruciński, A., Families of triples with high minimum degree are Hamiltonian, Discuss. Math., Graph Theory, 34, 2, 361-381 (2014) · Zbl 1290.05114 |
| [31] | Rödl, V.; Ruciński, A.; Szemerédi, E., A Dirac-type theorem for 3-uniform hypergraphs, Comb. Probab. Comput., 15, 1-2, 229-251 (2006), MR2195584 · Zbl 1082.05057 |
| [32] | Rödl, V.; Ruciński, A.; Szemerédi, E., An approximate Dirac-type theorem for k-uniform hypergraphs, Combinatorica, 28, 2, 229-260 (2008) · Zbl 1164.05051 |
| [33] | Rödl, V.; Ruciński, A.; Szemerédi, E., Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs, Adv. Math., 227, 3, 1225-1299 (2011) · Zbl 1220.05083 |
| [34] | Spielman, Daniel A.; Teng, Shang-Hua, Smoothed analysis: motivation and discrete models, (Algorithms and Data Structures. Algorithms and Data Structures, Lecture Notes in Comput. Sci., vol. 2748 (2003), Springer: Springer Berlin), 256-270 · Zbl 1253.68378 |
| [35] | Zhao, Yi, Recent advances on Dirac-type problems for hypergraphs, (Recent Trends in Combinatorics. Recent Trends in Combinatorics, IMA Vol. Math. Appl., vol. 159 (2016), Springer: Springer Cham) · Zbl 1354.05100 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
