2015/10/20 by Rudi Mrazović, Mrazović, Rudi
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1510.05991
12 pages
arxiv created 2015/10/20 · arxiv updated 2015/10/21
Green showed that there exist constants C1,C2>0 such that the clique number ω of the random Cayley graph on \mathbbF2n satisfies limn→∞ℙ(C1nlog n < ω< C2nlog n)=1. In this paper we find the best possible C1 and C2. 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 \mathbbF2n analogue of the famous conjecture by Bollobás and giving almost the complete answer to the question by Green.