Naslov
One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on $\mathbb{;; ; F};; ; _2^n$

Autori
Mrazović, Rudi

Izvornik
SIAM journal on discrete mathematics (0895-4801) 31 (2017), 1; 143-154

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Cayley graphs ; chromatic number ; clique number

Sažetak
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 Cayley graph on $\mathbb{; ; ; F}; ; ; _2^n$ generated by a random subset satisfies $\lim_{; ; ; n\to\infty}; ; ; \mathbb{; ; ; P}; ; ; (C_1n\log n < \omega_n < 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, the clique number is actually concentrated on a single value. As a simple consequence of these results, we also prove a one-point concentration result for the chromatic number, thus proving an $\mathbb{; ; ; F}; ; ; _2^n$ analogue of the famous conjecture by Bollobás [B. Bollobás, 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].

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA