One-point concentration of the clique and chromatic numbers of the random Cayley graph on F₂ⁿ

2015/10/20 by Rudi Mrazović, Mrazović, Rudi · 1 citation
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

Abstract

Green showed that there exist constants C₁,C₂>0 such that the clique number ω of the random Cayley graph on \mathbbF₂ⁿ satisfies lim_n→∞ℙ(C₁nlog n < ω< C₂nlog n)=1. In this paper we find the best possible C₁ and C₂. 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 \mathbbF₂ⁿ analogue of the famous conjecture by Bollobás and giving almost the complete answer to the question by Green.

Cited by

• Limiting spectral laws for sparse random circulant matrices

Related

• Tight asymptotics of clique-chromatic numbers of dense random graphs
• On the clique number of random Cayley graphs and related topics
• Cliques and Chromatic Number in Inhomogenous Random Graphs
• On the concentration of the chromatic number of random graphs
• Clique coloring of dense random graphs