Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems

Existence of Small Families of t-wise Independent Permutations... - Shachar Lovett

Shachar Lovett
Institute for Advanced Study
September 20, 2011

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 is \( v^{O(t)} \).

The main technical ingredients in both cases are local limit theorems used to study random walks on lattices.

Joint work with Greg Kuperberg and Ron Peled