• Counting Sets With Small Sumse...

Result: Counting Sets With Small Sumset, And The Clique Number Of Random Cayley Graphs: Counting sets with small sumset, and the clique number of random Cayley graphs

Title:
Counting Sets With Small Sumset, And The Clique Number Of Random Cayley Graphs: Counting sets with small sumset, and the clique number of random Cayley graphs
Authors:
Green, BJ
Source:
Combinatorica. 25:307-326
Publication Status:
Preprint
Publisher Information:
Springer Science and Business Media LLC, 2005.
Publication Year:
2005
Subject Terms:
Mathematics - Number Theory, Random graphs (graph-theoretic aspects), sumsets, 0102 computer and information sciences, 01 natural sciences, clique number, Cayley sum graph, Other combinatorial number theory, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Number Theory (math.NT), 0101 mathematics
Document Type:
Academic journal Article
File Description:
application/xml
Language:
English
ISSN:
1439-6912
0209-9683
DOI:
10.1007/s00493-005-0018-2
DOI:
10.48550/arxiv.math/0304183
Access URL:
http://arxiv.org/pdf/math/0304183
http://arxiv.org/abs/math/0304183
https://zbmath.org/2201519
https://doi.org/10.1007/s00493-005-0018-2
https://dblp.uni-trier.de/db/journals/combinatorica/combinatorica25.html#Green05
https://link.springer.com/article/10.1007/s00493-005-0018-2
https://ora.ox.ac.uk/objects/uuid:c259037c-2e39-4176-8623-91dbe844737e
Rights:
Springer TDM
arXiv Non-Exclusive Distribution
Accession Number:
edsair.doi.dedup.....3f725c8c3dde1644a15d1bcf10470852
Database:
OpenAIRE

Further Information

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.
18 pages; to appear in Combinatorica, exposition has been improved thanks to comments from Imre Ruzsa and Seva Lev