Random regular graphs of non-constant degree: concentration of the chromatic number (Q1043588): Difference between revisions

This is a paper about random regular graphs \({\mathcal G}_{n,d}\) where, given \(n\) labelled vertices, each of the \(d\)-regular graphs on these vertices is equally likely to be selected. We allow \(d=d(n)\) to depend on \(n\), and are interested in behaviour for large \(n\): in particular, we say that a property \(\wp\) holds \textbf{whp} (``with high probability'') if \[ \lim_{n\rightarrow \infty}P({\mathcal G}_{n,d}\text{~has~}\wp)=1. \] The main focus is on `concentration results' for the chromatic number \(\chi\) of the resulting graph. It is well known that many invariants of random graphs (e.g. the clique number of an Erdős-Rényi graph) are concentrated on a small range of values, i.e. take one of these values \textbf{whp}. The main result in the paper under review is that, provided \(d(n)=o(n^{1/5})\), there is a concentration on two points of the chromatic number. Somewhat more precisely, given \(\epsilon>0\) there is \(n_{0}(\epsilon)\) such that for all \(n>n_{0}\) and \(d=o(n^{1/5})\) there is \(t=t(n,d,\epsilon)\) such that \[ P(\chi({\mathcal G}_{n,d})\in \{t,t+1\})\geq 1-\epsilon. \] Here is an outline of the proof. First, the authors note a previous result from [\textit{D. Achlioptas} and \textit{C. Moore}, The chromatic number of random regular graphs. Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 7th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2004 and 8th international workshop on randomization and computation, RANDOM 2004, Cambridge, MA, USA, August22-24, 2004. Proceedings. Berlin: Springer. Lecture Notes in Computer Science 3122, 219--228 (2004; Zbl 1105.05063] who showed two-point concentration when \(d\) is constant, and stated that their argument in fact extends to the case where \(d=o(n^{1/9-\delta})\) for any \(\delta>0\). (The statement in the paper of Achlioptas and Moore that it should extend to \(d=o(n^{1/7-\delta})\) may require more justification than was originally envisaged). Thus we may assume \(d>n^{1/10}\) and one then proves a number of results saying that \textbf{whp} the numbers of edges in the graphs induced by various subsets of the vertex set are not too far from what one might expect them to be. These results use other results on the so-called configuration model for actually generating the random regular graphs and the so-called switching technique of McKay. One then completes the proof by showing that if \(n\) is large enough, \(n^{1/10}<d=o(n^{1/5})\) and \(G\) is a \(d\)-regular graph on \(n\) vertices whose induced subgraphs have the good behaviour of the number of edges just described, then \(G\) can be coloured with \(t+1\) colours for the right \(t\). The authors observe that their techniques probably work for a much broader range of \(d(n)\), possibly up to \(n^{1/2-\epsilon}\) for any \(\epsilon>0\). They also observe it would be interesting to find more about the range of values on which \(\chi\) is concentrated this does not emerge from the proof.