Counting sets with small sumset, and the clique number of random Cayley graphs (Q2387185): Difference between revisions

Suppose that \(\Gamma\) is a finite abelian group with cardinality \(N\) and that \(A\) is a subset of \(\Gamma\). Define \(G_A\) to be the graph with vertex set \(\Gamma\) and with \(i\) and \(j\) adjancent iff \(i+j\in A\). Such a graph is called a random Cayley sum graph, and the general question arises: to what extent, with \(A\) chosen at random, does \(G_A\) simulate a random graph on \(N\) vertices? This paper concentrates on the clique number \(\omega\) of \(G\). The main result is that if \(A\in Z_N\) is chosen at random then the probability that \(\omega(G)\leq 160\log N\) tends to 1 as \(N\to \infty\). This compares with the well known result for random graph \(G(N,1/2)\) that, if \(\varepsilon >0\), \[ \text{Prob}((2-\varepsilon)\log_2N\leq \omega\leq (2+\varepsilon)\log_2 N)\to 1\;\text{as}\;N\to \infty. \] It is also shown that the clique number of a random Cayley sum graph on \(\Gamma =Z^n_2\) is almost certainly of order \(\log N\log\log N\).