## Combinatorics Seminar

When: Sunday, December 14, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, Tel Aviv University
Title: On the number of B_{h}-sets of a given size
## Abstract:

Given an integer h > 1, we call a set A of integers a B_{h}-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 B_{h} set
if
there are no nontrivial solutions of the equation a_{1} + ... + a_{h}
=
b_{1} + ... + b_{h} with a_{i}, b_{i} from A. (If h = 2, such A are called
Sidon sets.) A well-studied problem in additive number theory is
that
of determining f_{h}(n), the maximum size of a B_{h}-set contained in
[n]
= {1, ..., n}. In particular, it is known that f_{h}(n) is of order
n^{1/h}.
In this talk, we shall investigate the more general problem of
estimating F_{h}(n,t), the number of B_{h}-sets contained in [n] that
have precisely t elements, for all t = O(n^{1/h}). Our results
show
the existence of a "threshold" function T_{h}(n) in the following
sense. If t << T_{h}(n), then the ratio of F_{h}(n,t) to n choose t is
fairly large, whereas if t >> T_{h}(n), then this ratio becomes
extremely small. As a corollary of our counting results, we
determine
the size of the largest B_{h}-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 F_{h}(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.