Skip to main content
eScholarship
Open Access Publications from the University of California

Probabilistic existence of regular combinatorial structures

  • Author(s): Kuperberg, G
  • Lovett, S
  • Peled, R
  • et al.

Published Web Location

https://arxiv.org/pdf/1302.4295
No data is associated with this publication.
Abstract

© 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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item