Counting sets with small sumset, and the clique number of random Cayley graphs (Q2387185): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1994148577 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0304183 / rank | |||
Normal rank |
Latest revision as of 06:19, 19 April 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