One-point concentration of the clique and chromatic numbers of the random Cayley graph on F_2^n

Abstract

Green showed that there exist constants $C_1,C_2>0$ such that the clique number $\omega$ of the random Cayley graph on ${\mathbb{F}}_2^n$ satisfies ${\lim }_{n\to \infty }\mathbb{P}(C_{1}n\log n<\omega <C_{2}n\log n)=1$. In this paper we find the best possible $C_1$ and $C_2$. Moreover, we prove that for $n$ in a set of density $1$, clique number is actually concentrated on a single value. As a simple consequence of these results, we also prove the one-point concentration result for the chromatic number, thus proving the ${\mathbb{F}}_2^n$ analogue of the famous conjecture by Bollobás and giving almost the complete answer to the question by Green.

12 pages

References in corpus (1)

• On the chromatic number of random Cayley graphs