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)
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 t1, t2, 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 A1, A2, ..., At1 and B1, B2, ..., Bt2 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.
- Hits: 98