Random Cayley graphs and random sumsets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911134693457920 |
|---|---|
| author | Alon, Noga Pham, Huy Tuan |
| author_facet | Alon, Noga Pham, Huy Tuan |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02561 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Random Cayley graphs and random sumsets Alon, Noga Pham, Huy Tuan Combinatorics Number Theory 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$. |
| title | Random Cayley graphs and random sumsets |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2509.02561 |