×

The threshold probability for long cycles. (English) Zbl 1371.05269

Summary: For a given graph \(G\) of minimum degree at least \(k\), let \(G_p\) denote the random spanning subgraph of \(G\) obtained by retaining each edge independently with probability \(p=p(k)\). We prove that if \(p\geq(\log k+\log\log k+\omega_k(1))/k\), where \(\omega_k(1)\) is any function tending to infinity with \(k\), then \(G_p\) asymptotically almost surely contains a cycle of length at least \(k+1\). When we take \(G\) to be the complete graph on \(k+1\) vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C38 Paths and cycles
05C12 Distance in graphs
05C85 Graph algorithms (graph-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C05 Trees
05C07 Vertex degrees
05C45 Eulerian and Hamiltonian graphs

Software:

Algorithm 447
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alon, N. and Spencer, J. (2008) The Probabilistic Method, Wiley. · Zbl 1148.05001
[2] Ben-Shimon, S., Krivelevich, M. and Sudakov, B. (2011) On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs. SIAM J. Discrete Math.251176-1193. doi:10.1137/110821299 · Zbl 1237.05187
[3] Bollobás, B. (1984) The evolution of sparse graphs. In Graph Theory and Combinatorics: Proc. Cambridge Combinatorial Conference in honor of Paul Erdős, Academic Press, pp. 35-57. · Zbl 0552.05047
[4] Bollobás, B., Random Graphs, (2001), Cambridge University Press · Zbl 0997.05049
[5] Diestel, R. (2010) Graph Theory, fourth edition, Vol. 173 of Graduate Texts in Mathematics, Springer. · Zbl 1204.05001
[6] Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences517-61. · Zbl 0103.16301
[7] Gilbert, E., Random graphs, Ann. Math. Statist., 30, 1141-1144, (1959) · Zbl 0168.40801 · doi:10.1214/aoms/1177706098
[8] Glebov, R. and Krivelevich, M. (2013) On the number of Hamilton cycles in sparse random graphs. SIAM J. Discrete Math.2727-42. doi:10.1137/120884316 · Zbl 1268.05179
[9] Hopcroft, J. and Tarjan, R. (1973) Algorithm 447: Efficient algorithms for graph manipulation. Comm. Assoc. Comput. Mach.16372-378.
[10] Komlós, J. and Szemerédi, E. (1983) Limit distributions for the existence of Hamilton circuits in a random graph. Discrete Math.4355-63. doi:10.1016/0012-365X(83)90021-3 · Zbl 0521.05055
[11] Korshunov, A., Solution of a problem of Erdős and Rényi on Hamiltonian cycles in non-oriented graphs, Soviet Math. Dokl., 17, 760-764, (1976) · Zbl 0353.05039
[12] Krivelevich, M., Lee, C. and Sudakov, B. (2015) Long paths and cycles in random subgraphs of graphs with large minimum degree. Random Struct. Alg.46320-345. doi:10.1002/rsa.20508 · Zbl 1314.05190
[13] Krivelevich, M. and Sudakov, B. (2013) The phase transition in random graphs: A simple proof. Random Struct. Alg.43131-138. doi:10.1002/rsa.20470 · Zbl 1272.05181
[14] Menger, K., Zur allgemeinen Kurventheorie, Fund. Math., 10, 96-115, (1927) · JFM 53.0561.01
[15] Pósa, L., Hamiltonian circuits in random graphs, Discrete Math., 14, 359-364, (1976) · Zbl 0322.05127 · doi:10.1016/0012-365X(76)90068-6
[16] Riordan, O., Long cycles in random subgraphs of graphs with large minimum degree, Random Struct. Alg., 45, 764-767, (2014) · Zbl 1320.05116 · doi:10.1002/rsa.20571
[17] West, D., Introduction to Graph Theory, (2007), Prentice Hall
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.