One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on $\mathbb{;; ; F};; ; _2^n$ (CROSBI ID 235606)
Prilog u časopisu | izvorni znanstveni rad | međunarodna recenzija
Podaci o odgovornosti
Mrazović, Rudi
engleski
One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on $\mathbb{;; ; F};; ; _2^n$
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].
Cayley graphs ; chromatic number ; clique number
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
nije evidentirano
Podaci o izdanju
31 (1)
2017.
143-154
objavljeno
0895-4801
1095-7146
10.1137/16M1062107