Combinatorics Seminar

When: Sunday, January 15, 10am Where: Schreiber 309 Speaker: Ron Peled, Tel Aviv University Title: Probabilistic existence of rigid combinatorial structures

Abstract:

We develop a new probabilistic method for proving the existence of rare objects under certain conditions. The method applies to show the existence of rigid combinatorial structures which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations. This improves existing results in the theory of t-designs and gives the first proof of existence of non-trivial t-wise permutations for t>3. In all cases, the sizes of the objects obtained are optimal up to polynomial overhead. Our main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.

Joint work with Greg Kuperberg and Shachar Lovett.