Seminar

Consider the following combinatorial problem. A t-(n,k,lambda) block design is a family of k-sets of [n], such that any t-set of [n] is contained in exactly lambda of the k-sets in the family. An (l; n,k,t) large set is a partition of all k-sets to t-(n,k,lambda) block designs (where necessarily lambda={n-t choose k-t}/l).

For which values of n,k,t,l to these objects exist? The known explicit constructions cover very few settings. So, it makes sense to study probabilistic constructions. A uniform partition of all the k-sets of [n] to l parts is very unlikely to produce an (l; n,k,t) large set. But is the probability of success zero, or merely tiny and positive (which suffices for proving existence)?

I will describe a general technique to analyze such problems, based on harmonic analysis and local central limit theorems. Surprisingly, the techniques to control the Fourier tail rely on concepts arising in coding theory.

https://arxiv.org/abs/1302.4295

https://eccc.weizmann.ac.il/report/2017/070/



Based on joint works with Greg Kuperberg, Ron Peled, Sankeerth Rao and Alex Vardy.