Combinatorics Seminar

When: Sunday, May 24, 10am Where: Schreiber 309 Speaker: Andras Sebo, CNRS, Laboratoire G-SCOP, Grenoble Title: Generating all sets with bounded unions

Abstract:

We consider the problem of minimizing the size of a family of sets G such that every subset of {1, . . . , n} can be written as a disjoint union of at most k members of G, where k and n are given numbers. This problem originates in a real-world application aiming at the diversity of industrial production. At the same time, the question of finding the minimum of |G| so that every subset of {1, . . . , n} is the union of two sets in G was asked by Erdos and studied recently by Furedi and Katona without requiring the disjointness of the sets. A simple construction providing a feasible solution is conjectured to be optimal for this problem for all values of n and k and regardless of the disjointness requirement; We wish to promote this conjecture, and show some first, simple results about it. We prove it for all (n,k) for which n \leq 3k holds, and some individual values of n and k. We also discuss a recent development by David Ellis settling this conjecture asymptotically.

Joint work with Yannick Frein and Benjamin Leveque.