Non-concentration of the chromatic number of a random graph
HTML articles powered by AMS MathViewer
- by Annika Heckel
- J. Amer. Math. Soc. 34 (2021), 245-260
- DOI: https://doi.org/10.1090/jams/957
- Published electronically: December 3, 2020
- HTML | PDF | Request permission
Abstract:
We show that the chromatic number of $G_{n, \frac {1}{2}}$ is not concentrated on fewer than $n^{\frac {1}{4}-\varepsilon }$ consecutive values. This addresses a longstanding question raised by Erdős and several other authors.References
- Dimitris Achlioptas and Assaf Naor, The two possible values of the chromatic number of a random graph, Ann. of Math. (2) 162 (2005), no. 3, 1335–1351. MR 2179732, DOI 10.4007/annals.2005.162.1335
- Noga Alon and Michael Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997), no. 3, 303–313. MR 1606020, DOI 10.1007/BF01215914
- Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703
- Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
- B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), no. 1, 49–55. MR 951992, DOI 10.1007/BF02122551
- Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
- B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), no. 1, 49–55. MR 951992, DOI 10.1007/BF02122551
- B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), no. 3, 419–427. MR 498256, DOI 10.1017/S0305004100053056
- Fan Chung and Ron Graham, Erdős on graphs, A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems. MR 1601954, DOI 10.1201/9781439863879
- Amin Coja-Oghlan, Konstantinos Panagiotou, and Angelika Steger, On the chromatic number of random graphs, J. Combin. Theory Ser. B 98 (2008), no. 5, 980–993. MR 2442592, DOI 10.1016/j.jctb.2007.11.009
- P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297. MR 120167, DOI 10.5486/pmd.1959.6.3-4.12
- P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
- Nikolaos Fountoulakis, Ross J. Kang, and Colin McDiarmid, The $t$-stability number of a random graph, Electron. J. Combin. 17 (2010), no. 1, Research Paper 59, 29. MR 2644845, DOI 10.37236/331
- Roman Glebov, Anita Liebenau, and Tibor Szabó, On the concentration of the domination number of the random graph, SIAM J. Discrete Math. 29 (2015), no. 3, 1186–1206. MR 3369991, DOI 10.1137/12090054X
- G. R. Grimmett and C. J. H. McDiarmid, On colouring random graphs, Math. Proc. Cambridge Philos. Soc. 77 (1975), 313–324. MR 369129, DOI 10.1017/S0305004100051124
- Annika Heckel, The chromatic number of dense random graphs, Random Structures Algorithms 53 (2018), no. 1, 140–182. MR 3829438, DOI 10.1002/rsa.20757
- 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
- Ross J. Kang and Colin McDiarmid, Colouring random graphs, Topics in chromatic graph theory, Encyclopedia Math. Appl., vol. 156, Cambridge Univ. Press, Cambridge, 2015, pp. 199–229. MR 3380173
- Tomasz Łuczak, A note on the sharp concentration of the chromatic number of random graphs, Combinatorica 11 (1991), no. 3, 295–297. MR 1122014, DOI 10.1007/BF01205080
- David W. Matula, On the complete subgraphs of a random graph, Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 356–369. MR 0266796
- D. Matula, The employee party problem, Notices of the American Mathematical Society, 19\penalty0 (2):\penalty0 A–382, 1972.
- Colin McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989) London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 1036755
- Konstantinos Panagiotou and Angelika Steger, A note on the chromatic number of a dense random graph, Discrete Math. 309 (2009), no. 10, 3420–3423. MR 2528203, DOI 10.1016/j.disc.2008.09.019
- Nathan Ross, Fundamentals of Stein’s method, Probab. Surv. 8 (2011), 210–293. MR 2861132, DOI 10.1214/11-PS182
- A. Scott, On the concentration of the chromatic number of random graphs. Available at arxiv.org/abs/0806.0178, 2008.
- E. Shamir and J. Spencer, Sharp concentration of the chromatic number on random graphs $G_{n,p}$, Combinatorica 7 (1987), no. 1, 121–129. MR 905159, DOI 10.1007/BF02579208
Bibliographic Information
- Annika Heckel
- Affiliation: Mathematisches Institut der Universität München, Theresienstr. 39, 80333 München, Germany
- MR Author ID: 1005704
- Email: heckel@math.lmu.de
- Received by editor(s): June 27, 2019
- Received by editor(s) in revised form: January 17, 2020, and April 1, 2020
- Published electronically: December 3, 2020
- Additional Notes: This research was funded by ERC Grants 676632-RanDM and 772606-PTRCSP.
- © Copyright 2020 American Mathematical Society
- Journal: J. Amer. Math. Soc. 34 (2021), 245-260
- MSC (2020): Primary 05C15, 05C80
- DOI: https://doi.org/10.1090/jams/957
- MathSciNet review: 4188818