Counting sets with small sumset, and the clique number of random Cayley graphs
Author:
Preprint
Abstract
Given a set A in Z/NZ we may form a Cayley sum graph G_A on vertex set Z/NZ by joining i to j if and only if i + j is in A. We investigate the extent to which performing this construction with a random set A simulates the generation of a random graph, proving that the clique number of G_A is a.s. O(log N). This shows that Cayley sum graphs can furnish good examples of Ramsey graphs. To prove this result we must study the specific structure of set addition on Z/NZ. Indeed, we also show that the clique number of a random Cayley sum graph on (Z/2Z)^n, 2^n = N, is almost surely not O(log N). Despite the graph-theoretical title, this is a paper in number theory. Our main results are essentially estimates for the number of sets A in {1,...,N} with |A| = k and |A + A| = m, for various values of k and m.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Random regular graphs of high degreeRandom Structures & Algorithms, 2001
- Combinatorics and linear algebra of Freiman's isomorphismMathematika, 2000
- Rectification Principles in Additive Number TheoryDiscrete & Computational Geometry, 1998
- Repeated communication and Ramsey graphsIEEE Transactions on Information Theory, 1995
- Can visibility graphs Be represented compactly?Discrete & Computational Geometry, 1994
- On irregularities of integer sequencesMathematika, 1974