A note on the chromatic number of a dense random graph (Q1025972): Difference between revisions

This paper deals with the chromatic number of random graphs \(G(n,p)\) (\(n\) labelled vertices, each pair adjacent with probability \(p\) independent of all other pairs) where \(0<p<1\) is a constant. More precisely we shall be concerned with its typical value as \(n\rightarrow\infty\), and shall say that a certain property \(\wp\) holds \textbf{whp} (``with high probability'') if \(\lim_{n\rightarrow\infty}P(G(n,p)\text{~has~}\wp)=1\). It has been known for a long time -- see e.g. [\textit{B. Bollobás}, Random Graphs. 2nd ed. Cambridge Studies in Advanced Mathematics. 73. Cambridge: Cambridge University Press (2001; Zbl 0979.05003)] that the independence number \(\alpha(G)\) for \(G(n,p)\) \textbf{whp} satisfies, writing \(b=1/(1-p)\), and putting \(r_{p}(n)= 2\log_{b}(n)-2\log_{b}\log_{b}(n)+2\log_{b}(e/2)\) for convenience, that \[ \lfloor r_{p}(n)+1-2\frac{\log_{b}\log_{b}(n)}{\log_{b}(n)}\rfloor \leq \alpha (G(n,p))\leq \lfloor r_{p}(n)+1+2\frac{\log_{b}\log_{b}(n)}{\log_{b}(n)}\rfloor. \] In particular, \(\alpha\) is ``concentrated on two values''. Since it is elementary that for every graph on \(n\) vertices its chromatic number \(\chi(G)\) is \(\geq n/\alpha(G)\), a naïve hope might be that the implied lower bound on \(\chi(G(n,p))\) is either the true value of the chromatic number or at least very close to it. This possibility remained open when \textit{B. Bollobás} [``The chromatic number of random graphs'', Combinatorica 8, No. 1, 49--55 (1988; Zbl 0666.05033)] proved (much more than) that \(\chi(G(n,p))\) is \textbf{whp} \(n/2\log_{b}(n)(1+o(1))\), and also when \textit{C. McDiarmid} [On the method of bounded differences. Surveys in combinatorics, Inv. Pap. 12th Br. Comb. Conf., Norwich/UK 1989, Lond. Math. Soc. Lect. Note Ser. 141, 148--188 (1989; Zbl 0712.05012)] refined Bollobás's method to prove that \textbf{whp} \[ \frac{n}{r_{p}(n)+1+o(1)}\leq \chi(G(n,p))\leq \frac{n}{r_{p}(n)-1/2-1/(1-\sqrt{1-p})+o(1)}. \] In the paper under review, the authors note that this naïve hope is over-optimistic. More precisely, their main result, Theorem 1.2 is that \textbf{whp} \[ \chi(G(n,p))\geq \frac{n}{r_{p}(n)-\log_{b}(e)+o(1)}. \] It is easy to see, by manipulation, that this implies that \textbf{whp} \(\chi(G(n,p))-n/\alpha(G(n,p))\) is at least a constant times \(n/\log^{2}(n)\). It remains an open, and interesting question, whether the chromatic number can be estimated more precisely. The proof is in one sense simple. The authors estimate the random variable \(X\), counting the number of partitions of \(V(G(n,p))\) into \(\ell\) vertex classes which induce a proper colouring. Thus it is easy to see that the expectation of \(X\) is \[ \frac{1}{\ell !}\sum_{n_{1}+n_{2}+\dots +n_{\ell}=n,\,n_{i}>0\forall i}{n\choose n_{1},\dots n_{\ell}} (1-p)^{\sum_{i=1}^{\ell}{n_{i}\choose 2}}. \] Now we aim to estimate this expectation, so as be able to use the 1st moment method \(P(X>0)\leq {\mathbf E}(X)\) to show that for \(\ell\) well chosen, there are no such proper colourings and so \(\chi(G)\geq \ell\). The estimates involve re-writing the expectation as a sum of weighted multinomial coefficients over a different set and then using Stirling's formula repeatedly to estimate the coefficients repeatedly.