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

BJ Green

Research output: Contribution to journalArticle (Academic Journal)peer-review

32 Citations (Scopus)

Abstract

Given a set A ⊆ 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 ∈ 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 almost surely 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 &UGamma; =(Z/2Z)(n) is almost surely not O( log |&UGamma;|).
Translated title of the contributionCounting sets with small sumset, and the clique number of random Cayley graphs
Original languageEnglish
Pages (from-to)307 - 326
JournalCombinatorica
Volume25 (3)
Publication statusPublished - May 2005

Bibliographical note

Publisher: Springer
Other identifier: IDS Number: 932TT

Fingerprint

Dive into the research topics of 'Counting sets with small sumset, and the clique number of random Cayley graphs'. Together they form a unique fingerprint.

Cite this