Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Robust Hamiltonicity of Dirac graphs


Authors: Michael Krivelevich, Choongbum Lee and Benny Sudakov
Journal: Trans. Amer. Math. Soc. 366 (2014), 3095-3130
MSC (2010): Primary 05C38, 05C35, 05C57, 05C80
DOI: https://doi.org/10.1090/S0002-9947-2014-05963-1
Published electronically: February 10, 2014
MathSciNet review: 3180741
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A graph is Hamiltonian if it contains a cycle which passes through every vertex of the graph exactly once. A classical theorem of Dirac from 1952 asserts that every graph on $ n$ vertices with minimum degree at least $ n/2$ is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we extend Dirac's theorem in two directions and show that Dirac graphs are robustly Hamiltonian in a very strong sense. First, we consider a random subgraph of a Dirac graph obtained by taking each edge independently with probability $ p$, and prove that there exists a constant $ C$ such that if $ p \ge C \log n / n$, then a.a.s. the resulting random subgraph is still Hamiltonian. Second, we prove that if a $ (1:b)$ Maker-Breaker game is played on a Dirac graph, then Maker can construct a Hamiltonian subgraph as long as the bias $ b$ is at most $ cn /\log n$ for some absolute constant $ c > 0$. Both of these results are tight up to a constant factor, and are proved under one general framework.


References [Enhancements On Off] (What's this?)

  • [1] Noga Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons Inc., Hoboken, NJ, 2008. With an appendix on the life and work of Paul Erdős. MR 2437651 (2009j:60004)
  • [2] Noga Alon and Benny Sudakov, Increasing the chromatic number of a random graph, J. Comb. 1 (2010), no. 3-4, 345-356. MR 2799216 (2012e:05337)
  • [3] N. Alon, M. Capalbo, Y. Kohayakawa, V. Rödl, A. Rucinski, and E. Szemerédi, Universality and tolerance, Proc. 41 IEEE FOCS. IEEE (2000), 14-21.
  • [4] József Balogh, Béla Csaba, and Wojciech Samotij, Local resilience of almost spanning trees in random graphs, Random Structures Algorithms 38 (2011), no. 1-2, 121-139. MR 2768886 (2012d:05340), https://doi.org/10.1002/rsa.20345
  • [5] J. Beck, Remarks on positional games. I, Acta Math. Acad. Sci. Hungar. 40 (1982), no. 1-2, 65-71. MR 685992 (85c:90121), https://doi.org/10.1007/BF01897304
  • [6] József Beck, Random graphs and positional games on the complete graph, Random graphs '83 (Poznań, 1983) North-Holland Math. Stud., vol. 118, North-Holland, Amsterdam, 1985, pp. 7-13. MR 860583 (87j:05130)
  • [7] József Beck, Deterministic graph games and a probabilistic intuition, Combin. Probab. Comput. 3 (1994), no. 1, 13-26. MR 1285685 (95h:90191), https://doi.org/10.1017/S0963548300000936
  • [8] József Beck, Combinatorial games, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge University Press, Cambridge, 2008. Tic-tac-toe theory. MR 2402857 (2009g:91038)
  • [9] Sonny Ben-Shimon, Michael Krivelevich, and Benny Sudakov, On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs, SIAM J. Discrete Math. 25 (2011), no. 3, 1176-1193. MR 2825331 (2012i:05254), https://doi.org/10.1137/110821299
  • [10] Béla Bollobás, The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 35-57. MR 777163 (86i:05119)
  • [11] B. Bollobás and A. Papaioannou, A biased Hamiltonian game, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), 1982, pp. 105-115. MR 725872 (85e:90081)
  • [12] B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35-38. MR 905149 (88g:05122), https://doi.org/10.1007/BF02579198
  • [13] J. A. Bondy, Basic graph theory: paths and circuits, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 3-110. MR 1373656 (97a:05129)
  • [14] V. Chvátal and P. Erdős, Biased positional games, Ann. Discrete Math. 2 (1978), 221-229. Algorithmic aspects of combinatorics (Conf., Vancouver Island, B.C., 1976). MR 500701 (81a:05107)
  • [15] Bill Cuckler and Jeff Kahn, Hamiltonian cycles in Dirac graphs, Combinatorica 29 (2009), no. 3, 299-326. MR 2520274 (2011a:05184), https://doi.org/10.1007/s00493-009-2360-2
  • [16] Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Martin Marciniszyn, and Angelika Steger, On the resilience of long cycles in random graphs, Electron. J. Combin. 15 (2008), no. 1, Research Paper 32, 26. MR 2383452 (2009h:05188)
  • [17] Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259 (2006e:05001)
  • [18] P. Erdős and J. L. Selfridge, On a combinatorial game, J. Combinatorial Theory Ser. A 14 (1973), 298-301. MR 0327313 (48 #5655)
  • [19] Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847 (2001k:05180)
  • [20] Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 85-103. MR 0378476 (51 #14644)
  • [21] János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb. 2 (1998), no. 1, 43-60. MR 1682919 (2000h:05144), https://doi.org/10.1007/BF01626028
  • [22] János Komlós and Endre Szemerédi, Limit distribution for the existence of Hamiltonian cycles in a random graph, Discrete Math. 43 (1983), no. 1, 55-63. MR 680304 (85g:05124), https://doi.org/10.1016/0012-365X(83)90021-3
  • [23] A. Korshunov,
    Solution of a problem of Erdős and Rényi on Hamiltonian cycles in non-oriented graphs,
    Soviet Math. Dokl. 17 (1976), 760-764.
  • [24] Michael Krivelevich, The critical bias for the Hamiltonicity game is $ (1+o(1))n/\ln n$, J. Amer. Math. Soc. 24 (2011), no. 1, 125-131. MR 2726601 (2011k:05158), https://doi.org/10.1090/S0894-0347-2010-00678-9
  • [25] Michael Krivelevich, Choongbum Lee, and Benny Sudakov, Resilient pancyclicity of random and pseudorandom graphs, SIAM J. Discrete Math. 24 (2010), no. 1, 1-16. MR 2600649 (2011h:05232), https://doi.org/10.1137/090761148
  • [26] Michael Krivelevich and Tibor Szabó, Biased positional games and small hypergraphs with large covers, Electron. J. Combin. 15 (2008), no. 1, Research Paper 70, 13. MR 2411447 (2009h:91047)
  • [27] Choongbum Lee and Benny Sudakov, Dirac's theorem for random graphs, Random Structures Algorithms 41 (2012), no. 3, 293-305. MR 2967175, https://doi.org/10.1002/rsa.20419
  • [28] László Lovász, Combinatorial problems and exercises, 2nd ed., AMS Chelsea Publishing, Providence, RI, 2007. MR 2321240
  • [29] L. Pósa, Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), no. 4, 359-364. MR 0389666 (52 #10497)
  • [30] Gábor N. Sárközy and Stanley Selkow, Distributing vertices along a Hamiltonian cycle in Dirac graphs, Discrete Math. 308 (2008), no. 23, 5757-5770. MR 2459395 (2009j:05136), https://doi.org/10.1016/j.disc.2007.10.042
  • [31] Gábor N. Sárközy, Stanley M. Selkow, and Endre Szemerédi, On the number of Hamiltonian cycles in Dirac graphs, Discrete Math. 265 (2003), no. 1-3, 237-250. MR 1969376 (2004a:05002), https://doi.org/10.1016/S0012-365X(02)00582-4
  • [32] Benny Sudakov and V. H. Vu, Local resilience of graphs, Random Structures Algorithms 33 (2008), no. 4, 409-433. MR 2462249 (2009h:05191), https://doi.org/10.1002/rsa.20235

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C38, 05C35, 05C57, 05C80

Retrieve articles in all journals with MSC (2010): 05C38, 05C35, 05C57, 05C80


Additional Information

Michael Krivelevich
Affiliation: School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Email: krivelev@post.tau.ac.il

Choongbum Lee
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: cb{\textunderscore}lee@math.mit.edu

Benny Sudakov
Affiliation: Department of Mathematics, ETH, 8092 Zurich, Switzerland – and – Department of Mathematics, University of California, Los Angeles, Los Angeles, California 90095
Email: benjamin.sudakov@math.ethz.ch

DOI: https://doi.org/10.1090/S0002-9947-2014-05963-1
Received by editor(s): January 10, 2012
Received by editor(s) in revised form: September 21, 2012
Published electronically: February 10, 2014
Additional Notes: The first author’s research was supported in part by USA-Israel BSF Grant 2010115 and by grants 1063/08, 912/12 from the Israel Science Foundation
The second author’s research was supported in part by a Samsung Scholarship
The third author’s research was supported in part by SNSF grant 200021-149111 and by a USA-Israel BSF grant
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society