Two values of the chromatic number of a sparse random graph
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 849-854
Stepan Kargaltsev; Dmitry Shabanov; Talia Shaikheeva; Stepan Kargaltsev; Dmitry Shabanov; Talia Shaikheeva. Two values of the chromatic number of a sparse random graph. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 849-854. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a75/
@article{AMUC_2019_88_3_a75,
     author = {Stepan Kargaltsev and Dmitry Shabanov and Talia Shaikheeva and Stepan Kargaltsev and Dmitry Shabanov and Talia Shaikheeva},
     title = { Two values of the chromatic number of a sparse random graph},
     journal = {Acta mathematica Universitatis Comenianae},
     pages = {849--854},
     year = {2019},
     volume = {88},
     number = {3},
     url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a75/}
}
TY  - JOUR
AU  - Stepan Kargaltsev
AU  - Dmitry Shabanov
AU  - Talia Shaikheeva
AU  - Stepan Kargaltsev
AU  - Dmitry Shabanov
AU  - Talia Shaikheeva
TI  - Two values of the chromatic number of a sparse random graph
JO  - Acta mathematica Universitatis Comenianae
PY  - 2019
SP  - 849
EP  - 854
VL  - 88
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a75/
ID  - AMUC_2019_88_3_a75
ER  - 
%0 Journal Article
%A Stepan Kargaltsev
%A Dmitry Shabanov
%A Talia Shaikheeva
%A Stepan Kargaltsev
%A Dmitry Shabanov
%A Talia Shaikheeva
%T Two values of the chromatic number of a sparse random graph
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 849-854
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a75/
%F AMUC_2019_88_3_a75

Voir la notice de l'article provenant de la source Comenius University

The famous results of \L uczak (1991) and Alon -- Krivelevich (1997) state that the chromatic number $\chi(G(n,p))$ of the binomial random graph $G(n,p)$ is concentrated in two consecutive values with probability tending to 1 provided $p=p(n)\le n^{-1/2-\varepsilon}$. Unfortunately, their proofs do not give the explicit values of $\chi(G(n,p))$ as functions of $n$ and $p$. Achlioptas and Naor (2005) found these values in the sparse case when $np$ is fixed. Coja--Oghlan, Panagiotou and Steger (2008) showed that the chromatic number of $G(n,p)$ is concentrated in three explicit consecutive values provided $p=p(n)\le n^{-3/4-\delta}$, they also established a 2-point concentration for the ``half'' of the values of the parameter $p$ under these conditions. In the current paper we improve the discussed result and show that the concentration of the chromatic number in two explicit consecutive values holds ``almost everywhere'' provided $p=p(n)\le n^{-3/4-\delta}$ and $np\to+\infty$. Namely, if $r_p=\min\{r:(n-1)p<2r\ln r\}$ then we prove that for$$ (n-1)p\in\left(2(r_p-1)\ln (r_p-1),2r_p\ln r_p-\ln r_p-2-r_{p}^{-1/6}\right),$$it holds that$$ {\sf Pr}\left(\chi(G(n,p))\in\{r_p,r_p+1\}\right)\to 1\mbox{ as }n\to+\infty.$$