On Sidon sets in a random set of vectors

Abstract: For positive integers

d

and

n

, let

[n]^{d}

be the set of all vectors

(a_{1}, a_{2}, d o t s, a_{d})

, where

a_{i}

is an integer with

0 l e q a_{i} l e q 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

m a t h c a l Z_{n, d}

be the number of all Sidon sets in

[n]^{d}

. We show that

l o g (m a t h c a l Z_{n, d}) = T h e t a (n^{d / 2})

, where the constants of

T h e t a

depend only on

d

. Next, we estimate the maximum size of Sidon sets contained in a random set

[n]_{p}^{d}

, where

[n]_{p}^{d}

denotes a random set obtained from

[n]^{d}

by choosing each element independently with probability

p

.

Recommendations

Cited in

(7)

This page was built for publication: On Sidon sets in a random set of vectors