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
Abstract:
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.