Combinatorics Seminar

When: Sunday, December 14, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, Tel Aviv University
Title: On the number of Bh-sets of a given size


Given an integer h > 1, we call a set A of integers a Bh-set if every number has at most one representation as a sum of h elements of A (even if we allow repetitions). In other words, A is a Bh set if there are no nontrivial solutions of the equation a1 + ... + ah = b1 + ... + bh with ai, bi from A. (If h = 2, such A are called Sidon sets.) A well-studied problem in additive number theory is that of determining fh(n), the maximum size of a Bh-set contained in [n] = {1, ..., n}. In particular, it is known that fh(n) is of order n1/h.

In this talk, we shall investigate the more general problem of estimating Fh(n,t), the number of Bh-sets contained in [n] that have precisely t elements, for all t = O(n1/h). Our results show the existence of a "threshold" function Th(n) in the following sense. If t << Th(n), then the ratio of Fh(n,t) to n choose t is fairly large, whereas if t >> Th(n), then this ratio becomes extremely small. As a corollary of our counting results, we determine the size of the largest Bh-set contained in a random m-element subset of [n] for every m.

If time permits, we shall discuss some ideas involved in the proof of the upper bounds for Fh(n,t). One key ingredient, an upper bound on the number of independent sets in "locally dense" graphs, which goes back to the work of Kleitman and Winston from the early 1980s, may be of independent interest.

This is joint work with Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Sang June Lee, and Vojtěch Rödl.