Random Cayley graphs and random sumsets

We prove that any finite abelian group $G$ contains a collection of not too many subsets with a special structure, so that for every subset $A$ of $G$ with a small doubling, there is a member $F$ of the collection that is fully contained in the sumset $A+A$ and is not much smaller than it. Using this result we obtain improved bounds for the problem of estimating the typical independence number of sparse random Cayley or Cayley-sum graphs, and for the problem of estimating the smallest size of a subset of $G$ which is not a sumset. We also obtain tight bounds for the typical maximum length of an arithmetic progression in the sumset of a sparse random subset of $G$.

• Publication year

  2025

• Venue

  Unknown venue

• Publication date

  2025-09-02

• Fields of study

  Mathematics

• Identifiers
  arXiv 2509.02561
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A remark on the independence number of sparse random Cayley sum graphs

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

  2024cited by this paper
• On the independence number of sparser random Cayley graphs

  2024cited by this paper
• Arithmetic progressions in sumsets of random sets

  2023influential reference
• A Proof of the Kahn-Kalai Conjecture

  2022cited by this paper
• An analog of Freiman's theorem in groups

  2018cited by this paper
• Counting sets with small sumset and applications

  2013cited by this paper
• The chromatic number of random Cayley graphs

  2013influential reference
• Arithmetic Progressions in Sumsets and Lp-Almost-Periodicity

  2011cited by this paper
• Large sets in finite fields are sumsets

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

  2007cited by this paper
• Thresholds and Expectation Thresholds

  2006cited by this paper
• Freiman's theorem in an arbitrary abelian group

  2005cited by this paper
• Counting Sets With Small Sumset, And The Clique Number Of Random Cayley Graphs

  2003cited by this paper
• The Probabilistic Method

  1998influential reference
• Repeated communication and Ramsey graphs

  1994cited by this paper
• Arithmetic progressions in sumsets

  1991cited by this paper
• A personal communication

  1989cited by this paper
• What is the structure of K if K+K is small?

  1987cited by this paper

• No citing papers are available for this paper.