로그인
ACTIVITIES
Published Papers
Home > Activities > Outputs > Published Papers
    Title   l  The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers
    Journal   l  Random Structures and Algorithms
    Year   l  2013
    Vol   l  DOI 10.1002/rsa.20496
    No   l  
    Pages   l  
    Author   l  Yoshiharu Kohayakawa, Sang June Lee, Vojtech Rodl, Wojciech Samotij
    DownLoad    l 1365646147_0.930967.pdf  
Abstract:
A set~$A$ of non-negative integers is called a \textit{Sidon set} if
all the sums~$a_1+a_2$, with~$a_1\leq a_2$ and~$a_1$,~$a_2\in A$,
are distinct. A well-known problem on Sidon sets is the
determination of the maximum possible size~$F(n)$ of a Sidon subset
of $[n]=\{0,1,\dots,n-1\}$. Results of Chowla, Erd\H{o}s, Singer and
Tur\'an from the 1940s give that $F(n)=(1+o(1))\sqrt{n}$. We study
Sidon subsets of sparse random sets of integers, replacing the
`dense environment'~$[n]$ by a sparse, random subset~$R$ of~$[n]$,
and ask how large a subset~$S\subset R$ can be, if we require
that~$S$ should be a Sidon set.

Let~$R=[n]_m$ be a random subset of~$[n]$ of cardinality~$m=m(n)$,
with all the~${n\choose m}$ subsets of~$[n]$ equiprobable. We
investigate the random variable~$F([n]_m)=\max|S|$, where the
maximum is taken over all Sidon subsets~$S\subset[n]_m$, and obtain
quite precise information on~$F([n]_m)$ for the whole range of~$m$,
as illustrated by the following abridged version of our results.
Let~$0\leq a\leq1$ be a fixed constant and
suppose~$m=m(n)=(1+o(1))n^a$. We show that there is a constant
$b=b(a)$ such that, almost surely, we have~$F([n]_m)=n^{b+o(1)}$.
As it turns out, the function~$b=b(a)$ is a continuous, piecewise
linear function of~$a$ that is non-differentiable at two `critical'
points:~$a=1/3$ and~$a=2/3$. Somewhat surprisingly, between those
two points, the function~$b=b(a)$ is constant.

Our approach is based on estimating the number of Sidon sets of a
given cardinality contained in~$[n]$. Our estimates also directly
address a problem raised by Cameron and Erd\H os [\emph{On the
number of sets of integers with various properties}, Number theory
({B}anff, {AB}, 1988), de Gruyter, Berlin, 1990, pp.~61--79].

Keyword

년도별 리스트보기 2017 | 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008
파일 년도 논문
2016 Anandam Banerjee, Jinhyun Park. On numerical equivalence for algebraic cobordism, J. Pure Appl. Algebra, 220(1):435-464
2015 Amalendu Krishna, Jinhyun Park. Semitopologization in motivic homotopy theory and applications, Algebraic & Geometric Topology, 15(2):823-861
2015 Amalendu Krishna, Jinhyun Park. DGA-structure on additive higher Chow groups, Int. Math. Res. Not., 2015(1):1-54
2015 Junehyuk Jung. Number of nodal domains and singular points of eigenfunctions of negatively curved surfaces with an isometric involution, J. Differential Geom., Vol. accepted
2015 Junehyuk. On the sparsity of positive-definite automorphic forms within a family, J. Anal. Math., Vol. accepted
2014 Sijong Kwak, Kangjin Han. Sharp bounds for higher linear syzygies and classifications of projective varieties, Math. Ann., Vol. DOI 10.1007/s00208-014-1084-9
2014 Sijong Kwak, Jaeman Ahn. On Syzygies, degree, and geometric properties of projective schemes with property N_{3,p}., J Pure and Applied Algebra(JPAA),
2014 Cheol-Hyun Cho. Orbifold Morse–Smale–Witten complexes, International Journal of Mathematics, 25(5):Doi:10.1142
2014 Cheol-Hyun Cho, Kwokwai Chan, Siu-Cheong Lau, Hsian-Hua Tseng. Lagrangian Floer Superpotentials and Crepant Resolutions for Toric Orbifolds, Communications in mathematical physics, DOI 10.1007/s00220-014-1
2013 Krishna, Amalendu; Park, Jinhyun. Algebraic cobordism theory attached to algebraic equivalence, Journal of K-theory, 11(1):73-112
2012 Krishna, Amalendu, Park, Jinhyun. Mixed motives over k[t]/(t^{m+1}), Journal of the Institute of Mathematics of Jussieu, 11(3):611-657
2012 rishna, Amalendu; Park, Jinhyun. Moving lemma for additive higher Chow groups, Algebra & Number Theory, Algebra & Number Theory, 6(2):293-326
2014 Sang June Lee. On constant-multiple-free sets contained in random sets of integers, Ars Combinatoria,
2013 Yoshiharu Kohayakawa, Sang June Lee, Vojtech Rodl, Wojciech Samotij. The number of Sidon sets and the maximum size of Sidon sets contained in a sparse random set of integers, Random Structures and Algorithms, Vol. DOI 10.1002/rsa.20496
2013 Cho, Cheol-Hyun1. On the counting of holomorphic discs in toric Fano manifolds, Advances in Geometry, Vol. DOI: 10.1515/advgeom-2012-0041
2012 Antei M.. Extension of finite solvable torsors over a curve, Manuscripta Mathematica, Vol. doi: 10.1007/s00229-012-0535-4
2012 Antei M., Mehta V. B.. On the Grothendieck-Lefschetz theorem for a family of varieties, Bulletin des Sciences Mathématiques, 136(4):423 - 431
2011 Marco Antei and Vikram B. Mehta. Vector bundles over normal varieties trivialized by finite morphisms DOI: 10.1007/s00013-011-0327-1, Archiv der Mathematik, 97(6):523-527
2011 Antei M. The fundamental group scheme of a non reduced scheme, Bulletin des Sciences Mathématiques, 135(5):531-539
2011 Jung Hee Cheon · Jin Hong · Minkyu Kim. Accelerating Pollard’s Rho Algorithm on Finite Fields, Journal of Cryptology,
1234