On Sidon sets in a random set of vectors
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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 $0\leq a_i\leq 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$.
Abstract
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 $0\leq a_i\leq 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$.
참고문헌 (12)
- S. Chowla, "Solution of a problem of Erd˝os and Tur´an in additive-number theory", Proc. Nat. Acad. Sci. India. Sect. A, 14, pp.1~2 (1944)
- J. Cilleruelo, "Sidon sets in N d", J. Combin. Theory Ser. A, 117(7), pp.857~871 (2010)
- P. Erd˝os, "On a problem of Sidon in additive number theory and on some related problems. Addendum", J. Lond. Math. Soc, 19, pp.208~ (1944)
- P. Erd˝os, "On a problem of Sidon in additive number theory, and on some related problems", J. Lond. Math. Soc, 16, pp.212~215 (1941)
- H. Halberstam, "Sequences" (1983), Springer-Verlag
- Y. Kohayakawa, "The maximum size of a Sidon set contained in a sparse random set of integers", Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp.159~171 (2011)
- Y. Kohayakawa, "The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers", Random Structures Algorithms, 46(1), pp.1~25 (2015)
- B. Lindstr¨om, "An inequality for B2-sequences", J. Combin. Theory, 6, pp.211~212 (1969)
- B. Lindstr¨om, "On B2-sequences of vectors", J. Number Theory, 4, pp.261~265 (1972)
- M. Mitzenmacher, "Probability and Computing" (2005), Cambridge University Press
- K. O’Bryant, "A complete annotated bibliography of work related to Sidon sequences", Electron. J. Combin, 11, pp.39~ (2004)
- J. Singer, "A theorem in finite projective geometry and some applications to number theory", Trans. Amer. Math. Soc, 43(3), pp.377~385 (1938)