Sidon set systems (Q1998671)

A Sidon set is a set of numbers \(A\) (one usually considers \(A \subset \mathbb Z\)) such that there are no non-trivial solutions to the equation \[ a+b=c+d,\quad a,b,c,d \in A. \] A trivial solution is one for which \(\{a,b \}= \{c,d \}\). Sidon sets are classical and well-studied objects in the field of additive combinatorics. Much attention has been paid to the question of determined the largest Sidon set such that \(A \subset [n]\); it is known that the answer is \( \sqrt n + o(\sqrt n)\), with the precise value of the lower order term unknown. In this paper the authors consider a very nice new variant of this problem for set systems. Let \(\binom{[n]}{k}\) denote the set of all subsets of \([n]\) with cardinality \(k\). The authors pose the following question: what is the largest subset \(\mathcal A \subset \binom{[n]}{k}\) such that \[ A+B=C+D \implies \{A,B \}= \{C,D \}. \] Here \(A+B= \{a +b : a \in A, b \in B \}\) denotes the usual sum set of two sets. In the case when \(k=1\), this is simply the classical question of determining the size of the largest Sidon set. We call such a family \(\mathcal A\) a \textit{Sidon set system}, and let \(F_k(n)\) denote the size of the largest Sidon set system in \(\binom{[n]}{k}\). The authors, using a quite elementary argument, establish the bound \[ F_k(n) \leq \binom{n-1}{k-1}+n-k, \] for all \(2 \leq k < n\). This bound is optimal for all \(k\) in this range, up to a multiplicative constant. Moreover, the bound is completely sharp for \(k=2\), and asymptotically sharp for \(k=3\). Indeed, the authors give corresponding constructions which show that \[ F_2(n)=2n-3, \quad F_3(n) = \frac{n^2}{2}-O(n) \] and \[ F_k(n) \gg_k n^{k-1}, \quad \text{ for all } \, k \geq 4. \] It is particularly noteworthy that this problem can be solved completely for \(k=2\), in contrast to the case of \(k=1\), which remains a major open problem. The authors also consider a randomised version of this problem, whereby one considers a \(p\)-random set \(\mathcal A \subset \binom{[n]}{k}\) (each \(A \in \binom{[n]}{k}\) belongs to \(\mathcal A\) with probability \(p\), and these events are independent), and we seek information about the probability that \(\mathcal A\) is a Sidon set system. Again, the \(k=1\) case has been well-studied in the previous literature. The authors show that a threshold occurs when \(p\) is approximately \(n^{-\frac{2k+1}{4}}\), at which points this probability lurches from \(1-o(1)\) to \(o(1)\).