Sidon set systems

  • Javier Cilleruelo

    Universidad Autónoma de Madrid, Spain
  • Oriol Serra

    Universitat Politècnica de Catalunya, Barcelona, Spain
  • Maximilian Wötzel

    Universitat Politècnica de Catalunya, Barcelona, Spain and Barcelona Graduate School of Mathematics, Spain
Sidon set systems cover
Download PDF

A subscription is required to access this article.

Abstract

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

Cite this article

Javier Cilleruelo, Oriol Serra, Maximilian Wötzel, Sidon set systems. Rev. Mat. Iberoam. 36 (2020), no. 5, pp. 1527–1548

DOI 10.4171/RMI/1174