On the clique number of random Cayley graphs and related topics

David Conlon, Jacob Fox, Huy Tuan Pham +1

We prove that a random Cayley graph on a group of order $N$ has clique number $O(\log N\log \log N)$ with high probability. This bound is best possible up to the constant factor f…