On the Number of Bh-Sets. (16th September 2015)

• Record Type: Journal Article
• Authors: DELLAMONICA, DOMINGOS; KOHAYAKAWA, YOSHIHARU; LEE, SANG JUNE; RÖDL, VOJTĚCH; SAMOTIJ, WOJCIECH
• Is Part Of: Combinatorics, probability and computing. Volume 25:Number 1(2016:Jan.)
• Page Start: 108
• Page End: 129
• Publication Date: 2015-09-16
• Subjects: Primary 11B75, -- 05A16, -- Secondary 05D40, -- 11B83; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548315000206
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : A set A of positive integers is a Bh -set if all the sums of the form a 1 + . . . + ah, with a 1, . . ., ah ∈ A and a 1 ⩽ . . . ⩽ ah, are distinct. We provide asymptotic bounds for the number of Bh -sets of a given cardinality contained in the interval [ n ] = {1, . . ., n }. As a consequence of our results, we address a problem of Cameron and Erdős (1990) in the context of Bh -sets. We also use these results to estimate the maximum size of a Bh -sets contained in a typical (random) subset of [ n ] with a given cardinality.