Spring 2017

The Number of B_h-sets of a Given Cardinality

Monday, March 6th, 2017 4:10 pm4:40 pm

Add to Calendar

Let A be a set of integers.  For any integer h\geq2, we say that A is a B_h-set if the h-wise sums  a_1 + ... + a_h (a_1,...,a_h\in A; a_1\leq...\leq a_h) are all distinct.  Let [n] = {1,...,n}.  A natural question is the determination or estimation of the extremal function
  F_h(n) = max{|A|: A\subset[n] is a B_h-set}.

The particular case of this problem in which h = 2 was raised by Simon Sidon in the 1930s and B_2-sets are known as Sidon sets.  An immediate argument shows that F_h(n) = o(n) and, therefore, this is a so called `degenerate' extremal problem.  As it is often the case with
degenerate problems, the structure of the extremal, that is, largest, B_h-sets A\subset[n] is not well understood.

We address the simpler problem of estimating the number of B_h-sets A\subset[n] of a given cardinality.  As a consequence of these bounds, we determine, asymptotically, for any integer m\leq n, the cardinality
of the largest B_h-sets contained in a typical m-element subset of [n].

This is joint work with D. Dellamonica Jr, S.J. Lee, V. Rödl and W. Samotij.