pith. sign in

arxiv: 1510.05991 · v1 · pith:GPRKH4GKnew · submitted 2015-10-20 · 🧮 math.CO

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

classification 🧮 math.CO
keywords cliquemathbbnumbercayleychromaticconcentrationgraphgreen
0
0 comments X
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.