×

Random perturbation of sparse graphs. (English) Zbl 1465.05091

Summary: In the model of randomly perturbed graphs we consider the union of a deterministic graph \(\mathcal{G}_\alpha\) with minimum degree \(\alpha n\) and the binomial random graph \(\mathbb{G}(n,p)\). This model was introduced by T. Bohman et al. [Random Struct. Algorithms 22, No. 1, 33–42 (2003; Zbl 1013.05044)] and for Hamilton cycles their result bridges the gap between Dirac’s theorem and the results by L. Posa [Discrete Math. 14, 359–364 (1976; Zbl 0322.05127)] and A. D. Korsunov [Sov. Math., Dokl. 17, 760–764 (1976; Zbl 0353.05039); translation from Dokl. Akad. Nauk SSSR 228, 529–532 (1976)] on the threshold in \(\mathbb{G}(n,p)\). In this note we extend this result in \(\mathcal{G}_\alpha\cup\mathbb{G}(n,p)\) to sparser graphs with \(\alpha=o(1)\). More precisely, for any \(\varepsilon>0\) and \(\alpha \colon \mathbb{N} \mapsto (0,1)\) we show that a.a.s. \( \mathcal{G}_\alpha\cup \mathbb{G}(n,\beta /n)\) is Hamiltonian, where \(\beta = -(6 + \varepsilon) \log(\alpha)\). If \(\alpha>0\) is a fixed constant this gives the aforementioned result by Bohman et al. and if \(\alpha=O(1/n)\) the random part \(\mathbb{G}(n,p)\) is sufficient for a Hamilton cycle. We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into \(\mathbb{G}(n,p)\).

MSC:

05C42 Density (toughness, etc.)
05C35 Extremal problems in graph theory
05C80 Random graphs (graph-theoretic aspects)

References:

[1] Noga Alon and Zolt´an F¨uredi,Spanning subgraphs of random graphs, Graphs and Combinatorics8(1992), no. 1, 91-94. · Zbl 0767.05082
[2] Noga Alon, Michael Krivelevich, and Benny Sudakov,Embedding nearly-spanning bounded degree trees, Combinatorica27(2007), no. 6, 629-644. · Zbl 1164.05032
[3] J´ozsef Balogh, B´ela Csaba, Martin Pei, and Wojciech Samotij,Large bounded degree trees in expanding graphs, The Electronic Journal of Combinatorics17(2010), no. 1, #R6. · Zbl 1184.05022
[4] J´ozsef Balogh, Andrew Treglown, and Adam Zsolt Wagner,Tilings in randomly perturbed dense graphs, Combinatorics, Probability and Computing28(2019), no. 2, 159-176. · Zbl 1434.05129
[5] Wiebke Bedenknecht, Jie Han, Yoshiharu Kohayakawa, and Guilherme O Mota,Powers of tight Hamilton cycles in randomly perturbed hypergraphs, Random Structures & Algorithms55(2019), no. 4, 795-807. · Zbl 1433.05178
[6] Patrick Bennett, Andrzej Dudek, and Alan Frieze,Adding random edges to create the square of a Hamilton cycle,arXiv:1710.02716(2017).
[7] Tom Bohman, Alan Frieze, and Ryan Martin,How many random edges make a dense graph Hamiltonian?, Random Structures & Algorithms22(2003), no. 1, 33-42. · Zbl 1013.05044
[8] B´ela Bollob´as and Arthur G Thomason,Threshold functions, Combinatorica7 (1987), no. 1, 35-38. · Zbl 0648.05048
[9] Julia B¨ottcher,Large-scale structures in random graphs, Surveys in Combinatorics 440(2017), 87. · Zbl 1423.05148
[10] Julia B¨ottcher, Jie Han, Yoshiharu Kohayakawa, Richard Montgomery, Olaf Parczyk, and Yury Person,Universality for bounded degree spanning trees in randomly perturbed graphs, Random Structures & Algorithms55(2019), no. 4, 854-864. · Zbl 1433.05275
[11] Julia B¨ottcher, Richard Montgomery, Olaf Parczyk, and Yury Person,Embedding spanning bounded degree subgraphs in randomly perturbed graphs, Mathematika (2019), 1-25. · Zbl 1378.05111
[12] Julia B¨ottcher, Mathias Schacht, and Anusch Taraz,Proof of the bandwidth conjecture of Bollob´as and Koml´os, Mathematische Annalen343(2009), no. 1, 175-205. · Zbl 1229.05132
[13] Shagnik Das, Patrick Morris, and Andrew Treglown,Vertex Ramsey properties of randomly perturbed graphs, Random Structures & Algorithms57(2020), no. 4, 983- 1006. · Zbl 1454.05075
[14] Shagnik Das and Andrew Treglown,Ramsey properties of randomly perturbed graphs: cliques and cycles, Combinatorics, Probability and Computing29(2020), no. 6, 830- 867. · Zbl 1466.05128
[15] Gabriel Andrew Dirac,Some theorems on abstract graphs, Proceedings of the London Mathematical Society3(1952), no. 1, 69-81. · Zbl 0047.17001
[16] Andrzej Dudek, Christian Reiher, Andrzej Ruci´nski, and Mathias Schacht,Powers of Hamiltonian cycles in randomly augmented graphs, Random Structures & Algorithms 56(2020), no. 1, 122-141. · Zbl 1444.05080
[17] P Erd˝os and Alfr´ed R´enyi,On the existence of a factor of degree one of a connected random graph, Acta Mathematica Hungarica17(1966), no. 3-4, 359-368. · Zbl 0203.56902
[18] Asaf Ferber, Kyle Luh, and Oanh Nguyen,Embedding large graphs into a random graph, Bulletin of the London Mathematical Society49(2017), no. 5, 784-797. · Zbl 1372.05199
[19] Asaf Ferber and Rajko Nenadov,Spanning universality in random graphs, Random Structures & Algorithms53(2018), no. 4, 604-637. · Zbl 1405.05160
[20] Alan Frieze and Micha l Karo´nski,Introduction to random graphs, Cambridge University Press, 2016. · Zbl 1328.05002
[21] Alan M Frieze,On large matchings and cycles in sparse random graphs, Discrete Mathematics59(1986), no. 3, 243-256. · Zbl 0628.05051
[22] Andr´as Hajnal and Endre Szemer´edi,Proof of a conjecture of P. Erd˝os, Combinatorial theory and its applications2(1970), 601-623. · Zbl 0217.02601
[23] Jie Han, Patrick Morris, and Andrew Treglown,Tilings in randomly perturbed graphs: Bridging the gap between Hajnal-Szemer´edi and Johansson-Kahn-Vu, Random Structures & Algorithms58(2021), no. 3, 480-516. · Zbl 1522.05428
[24] Anders Johansson, Jeff Kahn, and Van Vu,Factors in random graphs, Random Structures & Algorithms33(2008), no. 1, 1-28. · Zbl 1146.05040
[25] Felix Joos and Jaehoon Kim,Spanning trees in randomly perturbed graphs, Random Structures & Algorithms56(2020), no. 1, 169-219. · Zbl 1444.05132
[26] J´anos Koml´os, G´abor N S´ark¨ozy, and Endre Szemer´edi,Proof of a packing conjecture of Bollob´as, Combinatorics, Probability and Computing4(1995), no. 3, 241-255. · Zbl 0842.05072
[27] J´anos Koml´os, G´abor N S´ark¨ozy, and Endre Szemer´edi,On the P´osa-Seymour conjecture, Journal of Graph Theory29(1998), no. 3, 167-176. · Zbl 0919.05042
[28] J´anos Koml´os, G´abor N S´ark¨ozy, and Endre Szemer´edi,Proof of the Seymour conjecture for large graphs, Annals of Combinatorics2(1998), no. 1, 43-60. · Zbl 0917.05043
[29] J´anos Koml´os, G´abor N S´ark¨ozy, and Endre Szemer´edi,Spanning trees in dense graphs, Combinatorics, Probability and Computing10(2001), no. 5, 397-416. · Zbl 0998.05012
[30] J´anos Koml´os and Endre Szemer´edi,Limit distribution for the existence of Hamiltonian cycles in a random graph, Discrete Mathematics43(1983), no. 1, 55-63. · Zbl 0521.05055
[31] Aleksei Dmitrievich Korshunov,Solution of a problem of Erd˝os and Renyi on Hamiltonian cycles in nonoriented graphs, Doklady Akademii Nauk, vol. 228, Russian Academy of Sciences, 1976, pp. 529-532.
[32] Michael Krivelevich,Embedding spanning trees in random graphs, SIAM Journal on Discrete Mathematics24(2010), no. 4, 1495-1500. · Zbl 1221.05283
[33] Michael Krivelevich,Long paths and Hamiltonicity in random graphs, Random Graphs, Geometry and Asymptotic Structure84(2016), 1. · Zbl 1408.05075
[34] Michael Krivelevich, Matthew Kwan, and Benny Sudakov,Bounded-degree spanning trees in randomly perturbed graphs, SIAM Journal on Discrete Mathematics31 (2017), no. 1, 155-171. · Zbl 1354.05122
[35] Daniela K¨uhn and Deryk Osthus,On P´osa’s conjecture for random graphs, SIAM Journal on Discrete Mathematics26(2012), no. 3, 1440-1457. · Zbl 1256.05224
[36] Richard Montgomery,Spanning trees in random graphs, Advances in Mathematics 356(2019), 106793. · Zbl 1421.05080
[37] Rajko Nenadov and Nemanja ˇSkori´c,Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs, Random Structures & Algorithms 54(2019), no. 1, 187-208. · Zbl 1405.05167
[38] Rajko Nenadov and Miloˇs Truji´c,Sprinkling a few random edges doubles the power, SIAM Journal on Discrete Mathematics (2020).
[39] Lajos P´osa,Hamiltonian circuits in random graphs, Discrete Mathematics14(1976), no. 4, 359-364. · Zbl 0322.05127
[40] Oliver Riordan,Spanning subgraphs of random graphs, Combinatorics, Probability and Computing9(2000), no. 2, 125-148. · Zbl 0964.05058
[41] Daniel A Spielman and Shang-Hua Teng,Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM51(2004), no. 3, 385-463 · Zbl 1192.90120
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.