Generalizations of Sperner Systems

Dr. Grant Zhang

Department of Mathematical Sciences
University of Alabama in Huntsville

January 19, 2007
202 Madison Hall
3:00 PM (Coffee and Cookies at 2:30 in 201 Madison Hall)

Abstract

Given n and d what is the largest m for which we can find m subsets F of a set X of order n such that the difference of any two of these subsets has at least d elements? When d = 1 a classical result of Sperner in 1928 states that

,

which is attained if and only if F is either the collection of all subsets of order  or the collection of all subsets of order . Also, by replacing the word "difference" by "symmetric difference", the above problem is precisely one of the basic questions in coding theory: how many 0, 1 sequences of length n can we construct if any two of the sequences must differ in at least d places?

More generally, given t₁, t₂, n, and d what is the largest m for which we can find m subsets F of a set X of order n such that

for all distinct subsets A₁, A₂, ..., A_t1 and B₁, B₂, ..., B_t2 in F? These extremal set systems arise from electrical engineering and have equivalent formulations in combinatorial designs.

Our main aim in this talk is to present some optimal bounds. It turns out that many optimal solutions are closely related to t-designs.