Probabilistic existence of rigid combinatorial structures

DOI10.1145/2213977.2214075MaRDI QIDQ5415537zbMATH OpenOpenAlexFDO

Authors Greg Kuperberg, Shachar Lovett, Ron Peled

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.0492

zbMATH Keywords

designslocal central limit theoremorthogonal arrayspermutationsprobabilistic method

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Central limit and other weak theorems (60F05)

Abstract: We show the existence of rigid 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 such object has the required properties with positive yet tiny probability. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.

Recommendations

• Probabilistic existence of regular combinatorial structures
• The Stein-Lovász theorem and its applications to some combinatorial arrays
• scientific article; zbMATH DE number 863502

Cited in

(12)

• Counting Steiner triple systems
• Random combinatorial structures: the convergent case
• Counting \(r\)-graphs without forbidden configurations
• Probabilistic existence of regular combinatorial structures
• Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
• Double roots of random Littlewood polynomials
• Possibilities determine the combinatorial structure of probability polytopes
• Nontrivial t-designs over finite fields exist for all t
• On the discrepancy of random matrices with many columns
• Combinatorial models of rigidity and renormalization
• A spectral bound on hypergraph discrepancy
• Explicit and near-optimal construction of t-rankwise independent permutations

This page was built for publication: Probabilistic existence of rigid combinatorial structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415537)