On Sidon sets in a random set of vectors

摘要

For positive integers $d$ and $n$, let $[n]^d$ be the set of all vectors $(a_1,a_2,dots, a_d)$, where $a_i$ is an integer with $0leq a_ileq n-1$. A subset $S$ of $[n]^d$ is called a emph{Sidon set} if all sums of two (not necessarily distinct) vectors in $S$ are distinct. In this paper, we estimate two numbers related to the maximum size of Sidon sets in $[n]^d$. First, let $cZ_{n,d}$ be the number of all Sidon sets in $[n]^d$. We show that $log (cZ_{n,d})=Theta(n^{d/2})$, where the constants of $Theta$ depend only on $d$. Next, we estimate the maximum size of Sidon sets contained in a random set $[n]^d_p$, where $[n]^d_p$ denotes a random set obtained from $[n]^d$ by choosing each element independently with probability $p$.