Robust Hamiltonicity of Dirac graphs
HTML articles powered by AMS MathViewer
- by Michael Krivelevich, Choongbum Lee and Benny Sudakov PDF
- Trans. Amer. Math. Soc. 366 (2014), 3095-3130 Request permission
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
- 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, DOI 10.1002/9780470277331
- Noga Alon and Benny Sudakov, Increasing the chromatic number of a random graph, J. Comb. 1 (2010), no. 3-4, 345–356. MR 2799216, DOI 10.4310/JOC.2010.v1.n4.a1
- 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.
- 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, DOI 10.1002/rsa.20345
- J. Beck, Remarks on positional games. I, Acta Math. Acad. Sci. Hungar. 40 (1982), no. 1-2, 65–71. MR 685992, DOI 10.1007/BF01897304
- 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
- József Beck, Deterministic graph games and a probabilistic intuition, Combin. Probab. Comput. 3 (1994), no. 1, 13–26. MR 1285685, DOI 10.1017/S0963548300000936
- József Beck, Combinatorial games, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge University Press, Cambridge, 2008. Tic-tac-toe theory. MR 2402857, DOI 10.1017/CBO9780511735202
- 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, DOI 10.1137/110821299
- Béla Bollobás, The evolution of sparse graphs, Graph theory and combinatorics (Cambridge, 1983) Academic Press, London, 1984, pp. 35–57. MR 777163
- 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
- B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI 10.1007/BF02579198
- J. A. Bondy, Basic graph theory: paths and circuits, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 3–110. MR 1373656
- V. Chvátal and P. Erdős, Biased positional games, Ann. Discrete Math. 2 (1978), 221–229. MR 500701, DOI 10.1016/S0167-5060(08)70335-2
- Bill Cuckler and Jeff Kahn, Hamiltonian cycles in Dirac graphs, Combinatorica 29 (2009), no. 3, 299–326. MR 2520274, DOI 10.1007/s00493-009-2360-2
- 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
- Reinhard Diestel, Graph theory, 3rd ed., Graduate Texts in Mathematics, vol. 173, Springer-Verlag, Berlin, 2005. MR 2159259
- P. Erdős and J. L. Selfridge, On a combinatorial game, J. Combinatorial Theory Ser. A 14 (1973), 298–301. MR 327313, DOI 10.1016/0097-3165(73)90005-8
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- 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
- 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, DOI 10.1007/BF01626028
- 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, DOI 10.1016/0012-365X(83)90021-3
- 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.
- 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, DOI 10.1090/S0894-0347-2010-00678-9
- 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, DOI 10.1137/090761148
- 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
- Choongbum Lee and Benny Sudakov, Dirac’s theorem for random graphs, Random Structures Algorithms 41 (2012), no. 3, 293–305. MR 2967175, DOI 10.1002/rsa.20419
- László Lovász, Combinatorial problems and exercises, 2nd ed., AMS Chelsea Publishing, Providence, RI, 2007. MR 2321240, DOI 10.1090/chel/361
- L. Pósa, Hamiltonian circuits in random graphs, Discrete Math. 14 (1976), no. 4, 359–364. MR 389666, DOI 10.1016/0012-365X(76)90068-6
- 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, DOI 10.1016/j.disc.2007.10.042
- 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, DOI 10.1016/S0012-365X(02)00582-4
- Benny Sudakov and V. H. Vu, Local resilience of graphs, Random Structures Algorithms 33 (2008), no. 4, 409–433. MR 2462249, DOI 10.1002/rsa.20235
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_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
- MR Author ID: 602546
- Email: benjamin.sudakov@math.ethz.ch
- 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 - © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3180741