Counting sets with small sumset, and the clique number of random Cayley graphs
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(...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
2003
|
| _version_ | 1797093020158394368 |
|---|---|
| author | Green, B |
| author_facet | Green, B |
| author_sort | Green, B |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T03:54:21Z |
| format | Journal article |
| id | oxford-uuid:c259037c-2e39-4176-8623-91dbe844737e |
| institution | University of Oxford |
| last_indexed | 2024-03-07T03:54:21Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | oxford-uuid:c259037c-2e39-4176-8623-91dbe844737e2022-03-27T06:08:19ZCounting sets with small sumset, and the clique number of random Cayley graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:c259037c-2e39-4176-8623-91dbe844737eSymplectic Elements at Oxford2003Green, BGiven 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. |
| spellingShingle | Green, B 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 |
| title_full | Counting sets with small sumset, and the clique number of random Cayley
graphs |
| title_fullStr | Counting sets with small sumset, and the clique number of random Cayley
graphs |
| title_full_unstemmed | Counting sets with small sumset, and the clique number of random Cayley
graphs |
| title_short | Counting sets with small sumset, and the clique number of random Cayley
graphs |
| title_sort | counting sets with small sumset and the clique number of random cayley graphs |
| work_keys_str_mv | AT greenb countingsetswithsmallsumsetandthecliquenumberofrandomcayleygraphs |