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
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