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 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: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)}$.
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.