Intro Research Area Contact
 Basic Research Outputs Masters&PhDs
 Professor Post Doc Graduate Student Visiting Scholar Staff
 Organizations People
 Notice Photo Gallery
 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 Title of paper Title of journal

 년도별 리스트보기 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&eacute;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&eacute;matiques, 135(5):531-539
2011 Jung Hee Cheon · Jin Hong · Minkyu Kim. Accelerating Pollard’s Rho Algorithm on Finite Fields, Journal of Cryptology,
 1 2 3 4