Combinatorics Seminar

When: Sunday, March 22, 10am
Where: Schreiber 209 (NOTE THE UNUSUAL ROOM !)
Speaker: Or Ordentlich, Tel Aviv University
Title: An Upper Bound on the Sizes of Multiset-Union-Free Families

Abstract:

Two families of subsets of [n] are called multiset-union-free if all their pairwise multiset unions are distinct. In this work we derive a new upper bound on the sizes of families that possess this property, improving a result by Urbanke and Li. To that end, we introduce a soft variation of the Saur-Perles-Shelah Lemma, that is then used in conjunction with an information-theoretic bound for a more general setup.

No prior knowledge in information theory will be assumed.

Joint work with Ofer Shayevitz.