Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-06T23:07:22.106Z Has data issue: false hasContentIssue false
  • English
  • Français

The Threshold Probability for Long Cycles

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  08 September 2016

ROMAN GLEBOV ,
HUMBERTO NAVES  and
BENNY SUDAKOV
ROMAN GLEBOV
Affiliation:
School of Computer Science and Engineering, Hebrew University, Jerusalem 9190401, Israel (e-mail: roman.l.glebov@gmail.com)
HUMBERTO NAVES
Affiliation:
Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55455, USA (e-mail: hnaves@ima.umn.edu)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland (e-mail: benjamin.sudakov@math.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

For a given graph G of minimum degree at least k, let Gp denote the random spanning subgraph of G obtained by retaining each edge independently with probability p = p(k). We prove that if p ⩾ (logk + loglogk + ωk(1))/k, where ωk(1) is any function tending to infinity with k, then Gp 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 classification

Primary: 05C80: Random graphs
Secondary: 05C38: Paths and cycles 05C85: Graph algorithms 05D40: Probabilistic methods 05C05: Trees
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 208 - 247
Copyright
Copyright © Cambridge University Press 2016 

References

[1] Alon, N. and Spencer, J. (2008) The Probabilistic Method, Wiley.Google Scholar
[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. 25 1176–1193.Google Scholar
[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.Google Scholar
[4] Bollobás, B. (2001) Random Graphs, second edition, Cambridge University Press.CrossRefGoogle Scholar
[5] Diestel, R. (2010) Graph Theory, fourth edition, Vol. 173 of Graduate Texts in Mathematics, Springer.Google Scholar
[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 Sciences 5 17–61.Google Scholar
[7] Gilbert, E. (1959) Random graphs. Ann. Math. Statist. 30 1141–1144.CrossRefGoogle Scholar
[8] Glebov, R. and Krivelevich, M. (2013) On the number of Hamilton cycles in sparse random graphs. SIAM J. Discrete Math. 27 27–42.Google Scholar
[9] Hopcroft, J. and Tarjan, R. (1973) Algorithm 447: Efficient algorithms for graph manipulation. Comm. Assoc. Comput. Mach. 16 372–378.Google Scholar
[10] Komlós, J. and Szemerédi, E. (1983) Limit distributions for the existence of Hamilton circuits in a random graph. Discrete Math. 43 55–63.CrossRefGoogle Scholar
[11] Korshunov, A. (1976) Solution of a problem of Erdős and Rényi on Hamiltonian cycles in non-oriented graphs. Soviet Math. Dokl. 17 760–764.Google Scholar
[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. 46 320–345.CrossRefGoogle Scholar
[13] Krivelevich, M. and Sudakov, B. (2013) The phase transition in random graphs: A simple proof. Random Struct. Alg. 43 131–138.CrossRefGoogle Scholar
[14] Menger, K. (1927) Zur allgemeinen Kurventheorie. Fund. Math. 10 96–115.CrossRefGoogle Scholar
[15] Pósa, L. (1976) Hamiltonian circuits in random graphs. Discrete Math. 14 359–364.Google Scholar
[16] Riordan, O. (2014) Long cycles in random subgraphs of graphs with large minimum degree. Random Struct. Alg. 45 764–767.Google Scholar
[17] West, D. (2007) Introduction to Graph Theory, Prentice Hall.Google Scholar