Sidon set systems

Abstract

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 \left(\genfrac{}{}{0ex}{}{N-1}{k-1}\right)+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\ge 2$.

Incorporated referee comments. Published in Rev. Mat. Iberoam

References in corpus (2)

• Power monoids: A bridge between Factorization Theory and Arithmetic Combinatorics
• Is the Multiset of $n$ Integers Uniquely Determined by the Multiset of Its $s$-sums?