UC San Diego
Probabilistic existence of regular combinatorial structures
- Author(s): Kuperberg, G
- Lovett, S
- Peled, R
- et al.
Published Web Locationhttps://arxiv.org/pdf/1302.4295
© 2017, Springer International Publishing AG. We show the existence of regular combinatorial objects 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. In all cases, the sizes of the objects are optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen structure has the required properties with positive yet tiny probability. Our method allows also to give rather precise estimates on the number of objects of a given size and this is applied to count the number of orthogonal arrays, t-designs and regular hypergraphs. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.