MATH Seminar

Title: On the Number of B_h Sets of a Given Size
Seminar: Combinatorics
Speaker: Domingos Dellamonica of Sao Paulo
Contact: Vojtech Rodl, rodl@mathcs.emory.edu
Date: 2014-10-27 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: For an integer h bigger or equal to 2, a $B_h$ set is a set of integers with the property that every collection containing h of its elements yield a unique sum (and repetitions are allowed). For $h = 2$, such sets are also called Sidon sets. In this talk we will describe our recent results on estimating $F(n, s, h)$, which we define as the number of $B_h$ sets of cardinality s containing integers from $[n] = {1, 2, ..., n}$. It is not hard to see that for $s > n^(1/h)$, we have $F(n, s, h) = 0$. Indeed, in this case there are more h-sums than possible outcomes for the sums. On the other hand, there are constructions of B-h sets having cardinality $c.n^(1/h)$, (with c depending on h only) hence we shall estimate the behavior of $F(n, s, h)$ for s up to $O( n^(1/h))$. Our counting shows the existence of a surprising threshold function $T(n)$: for values of $s << T(n)$, the B-h sets are abundant while for $s >> T(n)$ the B-h sets become very rare. More precisely, we show that $T(n) ~ n^{(1 + o(1))/(2h - 1)}$ and establish fairly precise estimates of $F(n, s, h)$ for the entire range of s.