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.