ONE-POINT CONCENTRATION OF THE CLIQUE AND CHROMATIC NUMBERS OF THE RANDOM CAYLEY GRAPH ON F-2(n*)

摘要

Green [B. Green, Combinatorica, 25 (2005), pp. 307-326] showed that there exist constants C-1,C-2>0 such that the clique number omega(n) of the random Cayley graph on F-2(n) satisfies lim(n ->infinity) P(C(1)n log n < omega(n)< 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 F-2(n) analogue of the famous conjecture by Bollobas [B.Bollobas, Combin. Probab. Comput., 13 (2004), pp. 115-117] and giving almost the complete answer to the question by Green. [B. Green, On the Chromatic Number of Random Cayley Graphs, preprint, 2013]