One-point concentration of the clique and chromatic numbers of the random Cayley graph on F₂^n
classification
🧮 math.CO
keywords
cliquemathbbnumbercayleychromaticconcentrationgraphgreen
read the original 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_1n\log n < \omega < C_2n\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\'{a}s and giving almost the complete answer to the question by Green.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.