,UAH > Math > Colloquia > 1/19/2007
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.