Counting sets with small sumset, and the clique number of random Cayley graphs (Q2387185): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:58, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting sets with small sumset, and the clique number of random Cayley graphs |
scientific article |
Statements
Counting sets with small sumset, and the clique number of random Cayley graphs (English)
0 references
5 October 2006
0 references
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\).
0 references
Cayley sum graph
0 references
sumsets
0 references
clique number
0 references