Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number (Q3146985)

Let \(n\) and \(r\) be positive integers with \(nr\) even. The properties of a graph chosen uniformly and at random from all \(r\)-regular (simple) graphs on \(n\) labelled vertices have been much studied: see for example \textit{N. C. Wormald} [Models of random regular graphs, Lond. Math. Soc. Lect. Notes Ser. 267, 239-298 (1999; Zbl 0935.05080)] for a recent survey of this area. We say that (for given \(r=r(n)\)) the random graph \(G\) thus generated has some graph property \(\wp\) whp if \(\lim_{n\rightarrow\infty}P(G\text{ has }\wp)=1\). At the time of Wormald's article it was known that, provided \(r(n)\) is `small' the resulting random graph is whp \(r\)-connected and has a Hamilton cycle. Proofs had been written down, in the case of \(r\)-connectedness, in \textit{T. Łuczak} [Sparse random graphs with a given degree sequence; in: Frieze, Alan (ed.) et al., Random graphs. Volume 2, 165-182 (1992; Zbl 0817.05057)] for \(r(n)\leq n^{0.002}\) and, in the case of Hamiltonicity, for \(r=o(n^{1/5})\) in an unpublished result of Frieze, but it was `folklore' that these results could be extended to all \(r=o(n^{1/2})\) using the so-called edge switching technique of B. D. McKay and Wormald (see e.g. \textit{B. D. McKay} and \textit{N. C. Wormald} [Combinatorica 11, 369-382 (1991; Zbl 0742.05047)]). Let \(\alpha\) be the independence number and \(\chi\) the chromatic number. \textit{A. M. Frieze} and \textit{T. Łuczak} [J. Comb. Theory, Ser. B 54, 123-132 (1992; Zbl 0771.05088)] had shown that if \(\varepsilon\) and \(\eta\) are fixed \(>0\) then there is an \(r_{\varepsilon}\) such that, if \(r_{\varepsilon}\leq r\leq n^{1/3-\eta}\) then whp \[ \left|\alpha-\frac{2n}{r}(\log(r)-\log\log(r)+1-\log(2))\right|\leq \frac{\varepsilon n}{r} \] and, provided \(r\) is sufficiently large, whp \[ \left|\chi-\frac{r}{2\log(r)}\right|\leq \frac{16r\log\log(r)}{\log(r)^{2}}. \] The main obstacle to understanding behaviour for larger values of \(r(n)\) is the absence of a tractable model for the random graphs. The so-called configuration model used to prove the results for `small' \(r(n)\) runs into technical difficulties for larger \(r(n)\). The first progress beyond `small' \(r(n)\) was made in \textit{M. Krivelevich, B. Sudakov, V. H. Vu} and \textit{N. C. Wormald} [Random Struct. Algorithms 18, 346-363 (2001; Zbl 0996.05106)] where it was shown, using edge switching and the results from \textit{B. D. McKay} and \textit{N. C. Wormald} [Eur. J. Comb. 11, 565-580 (1990; Zbl 0739.05043)], that for \(n^{1/2}\log(n)\leq r(n)\leq n-4\) the graph is whp connected and has a Hamilton cycle, and that for \(n^{6/7+\varepsilon}\leq r(n)\leq 0.9n\) we have whp \(\alpha\sim 2\log_{n/(n-r)}(r)\). In \textit{C. Cooper, A. Frieze, B. Reed} [Random regular graphs of non-constant degree: Connectivity and Hamiltonicity, Comb. Probab. Comput. 11, 249-261 (2002)] the results for \(r\)-connectedness are extended to cover all \(3\leq r(n)\leq c_{0}n\). Together with the result of Krivelevich et al. noted above, this implies the graph whp is \(r\)-connected and has a Hamilton cycle for all \(3\leq r(n)\leq n-4\) (the largest range of \(r(n)\) for which it is possible to expect these two results to be true). In the present paper, estimates are given for the chromatic number and independence number of random regular graphs, when \(n^{1/4}\leq r(n)\leq n^{1-\eta}\) for any \(\eta>0\). More precisely, for \(\varepsilon>0\) it is shown that whp \[ \left|\alpha-\frac{2n}{r}(\log(r)-\log\log(r)+1-\log(2))\right|\leq \frac{\varepsilon n}{r} \] and that, denoting the chromatic number by \(\chi\), \[ \chi=\frac{r}{2\log(r)}\left(1+O\left(\frac{\log\log(r)}{\log(r)}\right)\right). \] Since the paper by Krivelevich et al. gives asymptotically tight estimates of \(\alpha\) and \(\chi\) for \(n^{6/7+\eta}\leq r(n)\leq 0.9n\), we see the gap in the middle is closed. However for \(\alpha\) and \(\chi\) a small gap \(0.9n< r(n)\) is not covered, and the behaviour of \(\alpha\) and \(\chi\) for small constant \(r\) is still not fully understood. The edge switching technique is crucial both in the paper under review and the paper of Cooper, Frieze and Reed. A further trick required here is a decomposition technique. Basically one takes a random partition of the \(n\) vertices into classes \(V_{1},\ldots, V_{s}\) where \(s=r^{1-\eta/10}\) and let \(d_{i,j}(v)\) be the degree of \(v\in V_{i}\) in the random bipartite graph \(\Gamma_{i,j}\) with vertex classes \(V_{i}\) and \(V_{j}\). (If \(i=j\), we take \(\Gamma_{i,i}\) to be the induced subgraph on \(V_{i}\).) Then \(d_{i,j}(v)\) is sharply concentrated around its mean. Summarising very crudely, we need only generate (for a typical degree sequence of \(\Gamma_{i,j})\), independent random graphs \(\Gamma_{i,j}\) with that degree sequence, and can then analyse the \(r\)-regular graph as a union of independent graphs of small degree about \(r^{\eta/10}\leq n/s\). The detailed proof is complex: in particular, it depends on careful analysis of an algorithm SIMPLIFY for passing from certain multigraphs with the right degree sequence to random simple graphs with these degree sequences. Readers interested in other recent work on random regular graphs should consult also \textit{J. H. Kim, B. Sudakov} and \textit{V. H. Vu} [Random Struct. Algorithms 21, 216-224 (2002)] which shows that the automorphism group is trivial whp for \(3\leq r(n)\leq n-4\) and various preprints on the homepages of Wormald, Kim and others.