Revista Matemática Iberoamericana

Full-Text PDF (345 KB) | List online-first RMI articles | RMI summary
Published online first: 2020-02-11
DOI: 10.4171/rmi/1174

Sidon set systems

Javier Cilleruelo, Oriol Serra[1] and Maximilian Wötzel[2]

(1) Universitat Politècnica de Catalunya, Barcelona, Spain
(2) Universitat Politècnica de Catalunya, Barcelona, Spain and Barcelona Graduate School of Mathematics, Spain

A family $\mathcal{A}$ of $k$-subsets of $\{1,2,\dots, N\}$ is a Sidon system if the sumsets $A+B$, $A,B\in \mathcal{A}$ are pairwise distinct. We show that the largest cardinality $F_k(N)$ of a Sidon system of $k$-subsets of $[N]$ satisfies $F_k(N)\le {N-1\choose k-1}+N-k$ and the asymptotic lower bound $F_k(N)=\Omega_k(N^{k-1})$. More precise bounds on $F_k(N)$ are obtained for $k\le 3$. We also obtain the threshold probability for a random system to be Sidon for $k \geq 2$.

Keywords: Sidon sets, distinct sumsets, additive combinatorics

Cilleruelo Javier, Serra Oriol, Wötzel Maximilian: Sidon set systems. Rev. Mat. Iberoam. Electronically published on February 11, 2020. doi: 10.4171/rmi/1174 (to appear in print)