pith. sign in

arxiv: 0711.0081 · v3 · submitted 2007-11-01 · 🧮 math.NT · math.CO

Number of sets with small sumset and the clique number of random Cayley graphs

classification 🧮 math.NT math.CO
keywords cayleygraphfinitenumberomegaabelianabsolutecomplete
0
0 comments X
read the original abstract

Let $G$ be a finite abelian group of order $n$. For any subset $B$ of $G$ with $B=-B$, the Cayley graph $G_B$ is a graph on vertex set $G$ in which $ij$ is an edge if and only if $i-j\in B.$ It was shown by Ben Green that when $G$ is a vector space over a finite field $Z/pZ$, then there is a Cayley graph containing neither a complete subgraph nor an independent set of size more than $clog nloglog n,$ where $c$ is an absolute constant. In this article we observe that a modification of his arguments shows that for an arbitrary finite abelian group of order $n$, there is a Cayley graph containing neither a complete subgraph nor an independent set of size more than $c(omega^3(n)log omega(n) +log nloglog n)$, where $c$ is an absolute constant and $omega(n)$ denotes the number of distinct prime divisors of $n$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.