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 is not concentrated on fewer than
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
Retrieve articles in Journal of the American Mathematical Society with MSC (2020): 05C15, 05C80
Retrieve articles in all journals with MSC (2020): 05C15, 05C80
Additional Information
Annika Heckel
Affiliation:
Mathematisches Institut der Universität München, Theresienstr. 39, 80333 München, Germany
Email:
heckel@math.lmu.de
DOI:
https://doi.org/10.1090/jams/957
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.
Article copyright:
© Copyright 2020
American Mathematical Society