DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kohayakawa, Yoshiharu | ko |
dc.contributor.author | Lee, Sang June | ko |
dc.contributor.author | Roedl, Vojtech | ko |
dc.contributor.author | Samotij, Wojciech | ko |
dc.date.accessioned | 2015-03-16T08:04:04Z | - |
dc.date.available | 2015-03-16T08:04:04Z | - |
dc.date.created | 2014-12-29 | - |
dc.date.created | 2014-12-29 | - |
dc.date.created | 2014-12-29 | - |
dc.date.issued | 2015-01 | - |
dc.identifier.citation | RANDOM STRUCTURES & ALGORITHMS, v.46, no.1, pp.1 - 25 | - |
dc.identifier.issn | 1042-9832 | - |
dc.identifier.uri | http://hdl.handle.net/10203/194145 | - |
dc.description.abstract | A set A of non-negative integers is called a Sidon set if all the sums a1+a(2), with a(1)<= a(2) and a(1), a(2), 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,...,n-1}. Results of Chowla, Erdos, Singer and Turan from the 1940s give that F(n)=(1+o(1))root 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 of>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 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 of>[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 0a1 be a fixed constant and suppose m=m(n)=(1+o(1))na. We show that there is a constant b=b(a) such that, almost surely, we have F([n]m)=nb+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 Erds (On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61-79). | - |
dc.language | English | - |
dc.publisher | WILEY-BLACKWELL | - |
dc.subject | ARITHMETIC PROGRESSIONS | - |
dc.subject | UNCROWDED HYPERGRAPHS | - |
dc.subject | GRAPHS | - |
dc.subject | SUBSETS | - |
dc.title | The Number of Sidon Sets and the Maximum Size of Sidon Sets Contained in a Sparse Random Set of Integers | - |
dc.type | Article | - |
dc.identifier.wosid | 000345595000001 | - |
dc.identifier.scopusid | 2-s2.0-84921661741 | - |
dc.type.rims | ART | - |
dc.citation.volume | 46 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 1 | - |
dc.citation.endingpage | 25 | - |
dc.citation.publicationname | RANDOM STRUCTURES & ALGORITHMS | - |
dc.identifier.doi | 10.1002/rsa.20496 | - |
dc.contributor.localauthor | Lee, Sang June | - |
dc.contributor.nonIdAuthor | Kohayakawa, Yoshiharu | - |
dc.contributor.nonIdAuthor | Roedl, Vojtech | - |
dc.contributor.nonIdAuthor | Samotij, Wojciech | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Sidon sets | - |
dc.subject.keywordAuthor | random sets of integers | - |
dc.subject.keywordAuthor | probabilistic extremal problems | - |
dc.subject.keywordAuthor | additive combinatorics | - |
dc.subject.keywordPlus | ARITHMETIC PROGRESSIONS | - |
dc.subject.keywordPlus | UNCROWDED HYPERGRAPHS | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordPlus | SUBSETS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.