Non-concentration of the chromatic number of a random graph

Heckel, Annika

doi:10.1090/jams/957

Non-concentration of the chromatic number of a random graph

Author: Annika Heckel
Journal: J. Amer. Math. Soc. 34 (2021), 245-260
MSC (2020): Primary 05C15, 05C80
DOI: https://doi.org/10.1090/jams/957
Published electronically: December 3, 2020
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show that the chromatic number of $G_{n, \frac {1}{2}}$ is not concentrated on fewer than $n^{\frac {1}{4}-\epsilon }$ consecutive values. This addresses a longstanding question raised by Erdős and several other authors.

[1] 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, https://doi.org/10.4007/annals.2005.162.1335
[2] Noga Alon and Michael Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997), no. 3, 303–313. MR 1606020, https://doi.org/10.1007/BF01215914
[3] 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
[4] 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
[5] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), no. 1, 49–55. MR 951992, https://doi.org/10.1007/BF02122551
[6] Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966
[7] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), no. 1, 49–55. MR 951992, https://doi.org/10.1007/BF02122551
[8] B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), no. 3, 419–427. MR 498256, https://doi.org/10.1017/S0305004100053056
[9] Fan Chung and Ron Graham, Erdős on graphs, A K Peters, Ltd., Wellesley, MA, 1998. His legacy of unsolved problems. MR 1601954
[10] 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, https://doi.org/10.1016/j.jctb.2007.11.009
[11] P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297. MR 120167
[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
[13] Nikolaos Fountoulakis, Ross J. Kang, and Colin McDiarmid, The 𝑡-stability number of a random graph, Electron. J. Combin. 17 (2010), no. 1, Research Paper 59, 29. MR 2644845
[14] 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, https://doi.org/10.1137/12090054X
[15] G. R. Grimmett and C. J. H. McDiarmid, On colouring random graphs, Math. Proc. Cambridge Philos. Soc. 77 (1975), 313–324. MR 369129, https://doi.org/10.1017/S0305004100051124
[16] Annika Heckel, The chromatic number of dense random graphs, Random Structures Algorithms 53 (2018), no. 1, 140–182. MR 3829438, https://doi.org/10.1002/rsa.20757
[17] Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847
[18] 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
[19] Tomasz Łuczak, A note on the sharp concentration of the chromatic number of random graphs, Combinatorica 11 (1991), no. 3, 295–297. MR 1122014, https://doi.org/10.1007/BF01205080
[20] 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
[21] D. Matula,
The employee party problem,
Notices of the American Mathematical Society, 19(2):A-382, 1972.
[22] 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
[23] 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, https://doi.org/10.1016/j.disc.2008.09.019
[24] Nathan Ross, Fundamentals of Stein’s method, Probab. Surv. 8 (2011), 210–293. MR 2861132, https://doi.org/10.1214/11-PS182
[25] A. Scott,
On the concentration of the chromatic number of random graphs.
Available at arxiv.org/abs/0806.0178, 2008.
[26] E. Shamir and J. Spencer, Sharp concentration of the chromatic number on random graphs 𝐺_{𝑛,𝑝}, Combinatorica 7 (1987), no. 1, 121–129. MR 905159, https://doi.org/10.1007/BF02579208