Counting Sets With Small Sumset, And The Clique Number Of Random Cayley Graphs

Given a set A⊂ ℤ/Nℤ we may form a Cayley sum graph GA on vertex set ℤ/Nℤ 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 GA is almost surely O(logN). 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 ℤ/Nℤ. Indeed, we also show that the clique number of a random Cayley sum graph on Γ =(ℤ/2ℤ)n is almost surely notO(log |Γ|).

• Publication year

  2003

• Venue

  Comb.

• Publication date

  2003-04-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00493-005-0018-2arXiv math/0304183
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An analog of Freiman's theorem in groups

  2018influential reference
• Foundations of a Structural Theory of Set Addition

  2007cited by this paper
• Modern Graph Theory

  2002cited by this paper
• Random regular graphs of high degree

  2001cited by this paper
• Combinatorics and linear algebra of Freiman's isomorphism

  2000cited by this paper
• Rectification Principles in Additive Number Theory

  1998cited by this paper
• Sums of Finite Sets

  1996influential reference
• Repeated communication and Ramsey graphs

  1994cited by this paper
• Can visibility graphs Be represented compactly?

  1993cited by this paper
• Uniform distrubution, positive trigonometric polynomials and difference sets

  1982cited by this paper
• On irregularities of integer sequences

  1974cited by this paper

• On the cop number and the weak Meyniel conjecture for algebraic graphs

  2025cites this paper
• The VC-dimension of random subsets of finite groups

  2025cites this paper
• The Lovász number of random circulant graphs

  2025cites this paper
• A remark on the independence number of sparse random Cayley sum graphs

  2025influential citation
• Limiting spectral laws for sparse random circulant matrices

  2025cites this paper
• Random Cayley graphs and random sumsets

  2025cites this paper
• On the clique number of random Cayley graphs and related topics

  2024influential citation
• On the independence number of sparser random Cayley graphs

  2024cites this paper
• On Cayley sum signed graphs-I

  2024cites this paper
• Low-Degree Polynomials Are Good Extractors

  2024cites this paper
• Sumsets in the Hypercube

  2024cites this paper
• On the cop number and the weak Meyniel conjecture for algebraic graphs

  2023cites this paper
• Vertex isoperimetry on signed graphs and spectra of non-bipartite Cayley and Cayley sum graphs

  2023cites this paper
• On the subgraphs of Cayley sum graphs

  2023cites this paper
• Restricted sumsets in multiplicative subgroups

  2023cites this paper
• Maximality of subfields as cliques in Cayley graphs over finite fields

  2022influential citation
• Gauss sums and the maximum cliquesin generalized Paley graphs of square order

  2021cites this paper
• On maximal cliques of Cayley graphs over fields

  2021cites this paper
• C O ] 1 7 Ju n 20 20 Sidon set systems

  2020cites this paper
• The Typical Structure of Sets With Small Sumset

  2019cites this paper
• A Cheeger type inequality in finite Cayley sum graphs

  2019cites this paper
• The Erdős–Moser Sum-free Set Problem

  2018cites this paper
• Set systems with distinct sumsets

  2018cites this paper
• Sidon set systems

  2018cites this paper
• On subgraphs of random Cayley sum graphs

  2017cites this paper
• On Cayley Sum Graphs of Non-Abelian Groups

  2016cites this paper
• On integral Cayley sum graphs

  2016cites this paper
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles

  2016cites this paper
• On integral Cayley sum graphs

  2016cites this paper
• The number of subsets of integers with no $k$-term arithmetic progression

  2016cites this paper
• A random model for the Paley graph

  2016cites this paper
• Integral Cayley Sum Graphs and Groups

  2016cites this paper
• On Cayley Sum Graphs of Non-Abelian Groups

  2015cites this paper
• Extractors in Paley graphs: A random model

  2015cites this paper
• One-Point Concentration of the Clique and Chromatic Numbers of the Random Cayley Graph on 픽2

  2015cites this paper
• On Reducible and Primitive Subsets of Fp, I

  2015cites this paper
• Cayley sum color and anti-circulant graphs

  2015cites this paper
• Unitary Addition Cayley Ring Signed Graphs *

  2015cites this paper
• Counting sets with small sumset and applications

  2015cites this paper
• On the independence ratio of distance graphs

  2014cites this paper
• On the domination and total domination numbers of Cayley sum graphs over Zn

  2014cites this paper
• On the Chromatic Number of Random Cayley Graphs

  2013influential citation
• Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions

  2013cites this paper
• The chromatic number of random Cayley graphs

  2013cites this paper
• Application of some combinatorial arrays in coloring of total graph of a commutative ring

  2013cites this paper
• Unitary Addition Cayley Signed Graphs

  2013cites this paper
• Counting sets with small sumset and applications

  2013cites this paper
• Difference Sets and Positive Exponential Sums I. General Properties

  2012cites this paper
• A refinement of the Cameron–Erdős conjecture

  2012cites this paper
• Uniquely Kr-Saturated Graphs

  2012cites this paper
• Some properties of unitary addition Cayley graphs

  2012cites this paper
• Combinatorics Using Computational Methods

  2012cites this paper
• Random Latin square graphs

  2011cites this paper
• Spectra of Graphs

  2011cites this paper
• Freiman Homomorphisms of Random Subsets of $\mathbb{Z}_{N}$

  2010cites this paper
• Gonzalo Fiz Pontiveros-AFR Proposal

  2010cites this paper
• N T ] 1 N ov 2 00 7 Clique number of random Cayley graph

  2009cites this paper
• Connectivity of addition Cayley graphs

  2007cites this paper
• The Connectivity of addition Cayley graphs

  2007cites this paper
• Large sets in finite fields are sumsets

  2007cites this paper
• Number of sets with small sumset and the clique number of random Cayley graphs

  2007influential citation
• Sum-free subsets of finite abelian groups of type III

  2007influential citation
• Sums and differences along Hamiltonian cycles

  2006cites this paper
• Testing triangle-freeness in general graphs

  2006cites this paper
• A Cheeger type inequality in finite Cayley sum graphs

  year unknowncites this paper