***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 13th October, 2.15 in Fine Hall 224
 
Speaker: Shachar Lovett, IAS, Princeton

Title: Existence of small families of t-wise independent permutations and
t-designs via local limit theorems.

We show existence of rigid combinatorial objects that previously were not known
to exist. Specifically, we consider two families of objects:

1. A family of permutations on n elements is t-wise independent if it acts
uniformly on tuples of t elements. Constructions of small families of t-wise
independent permutations are known only for t=1,2,3. We show that there exist
small families of t-wise independent permutations for all t, whose size is
n^{O(t)}.

2. A t-(v,k,lambda) design is a family of sets of size k in a universe of size v
such that each t elements belong to exactly lambda sets. Constructions of
t-designs are known only for some specific settings of parameters. We show that
there exist small t-designs for any t,v,k whose size (and lambda) are v^{O(t)}.

Both results follow the same methodology. We formulate the problem as a random
walk on a lattice with a prescribed set of allowed steps, and then study the
random walk using local limit theorems.

Joint work with Greg Kuperberg and Ron Peled

                       -----------

Next week: Laci Lovasz

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)