Discrete Geometry and Combinatorics Seminar

Greg KuperbergUniversity of California at Davis
Probabilistic existence of t-designs and other regular combinatorial structures

Monday, September 23, 2013 - 2:30pm
Malott 206

A t-(v,k,λ) design, also called a t-design, is a set of k-subsets (blocks) in a universal set of size v, such that every t-tuple is in exactly λ blocks. Teirlinck's theorem is a celebrated result that says that there is a non-trivial t-design for every t. I will discuss a new method developed in joint work with Shachar Lovett and Ron Peled that gives a new proof of Teirlinck's theorem with a much wider range of choices for the other parameters. The argument is a novel variant of the probabilistic method: If you pick a collection of blocks at random, there is a very small but positive probability that they will form a t-design; the probability can be estimated precisely using a finitary version of the local central limit theorem. The same method can be used to show existence of t-wise permutations for every t, and also q-analogues of t-designs and other regular combinatorial structures.