Probabilistic existence of regular combinatorial structures
From MaRDI portal
Publication:2400828
Abstract: 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.
Recommendations
Cites work
- A constructive proof of the general Lovász local lemma
- A constructive proof of the Lovász local lemma
- A diagonal form for the incidence matrices of t-subsets vs. k- subsets
- A Fourier-analytic approach to counting partial Hadamard matrices
- A recursive construction of t-wise uniform permutations
- Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions
- An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
- An Identity Involving the Least Common Multiple of Binomial Coefficients and Its Application
- Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration of correlation-immune Boolean functions
- Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
- Asymptotic Enumeration of Hypergraphs by Degree Sequence
- Averaging sets: A generalization of mean values and spherical designs
- Chebyshev-type quadratures for doubling weights
- Combinatorics and complexity of partition functions
- Constructing Small Sample Spaces Satisfying Given Constraints
- Constructive discrepancy minimization by walking on the edges
- scientific article; zbMATH DE number 5771375 (Why is no real title available?)
- scientific article; zbMATH DE number 51906 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- scientific article; zbMATH DE number 3448595 (Why is no real title available?)
- scientific article; zbMATH DE number 863481 (Why is no real title available?)
- scientific article; zbMATH DE number 3430682 (Why is no real title available?)
- Large sets of t-designs from groups
- Locally Decodable Codes
- Longest Increasing and Decreasing Subsequences
- Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
- Moore-Penrose inverse of set inclusion matrices
- Non-trivial \(t\)-designs without repeated blocks exist for all \(t\)
- On a bound of Hoeffding in the complex case
- On Linear Characterizations of Combinatorial Optimization Problems
- On t-designs
- On the Representations of the Symmetric Group
- Optimal asymptotic bounds for spherical designs
- Orthogonal arrays. Theory and applications
- Probabilistic existence of rigid combinatorial structures
- Six Standard Deviations Suffice
- Small designs for path-connected spaces and path-connected homogeneous spaces
- The CRC handbook of combinatorial designs
- The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
- The module structure of integral designs
- The number of graphs and a random graph with a given degree sequence
- The representation theory of the symmetric groups
Cited in
(27)- Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges
- Random combinatorial structures: the convergent case
- Large sets with multiplicity
- Large sets of \(t\)-designs over finite fields exist for all \(t\)
- The Stein-Lovász theorem and its applications to some combinatorial arrays
- Coloured and directed designs
- Possibilities determine the combinatorial structure of probability polytopes
- scientific article; zbMATH DE number 1245629 (Why is no real title available?)
- Asymptotic enumeration of difference matrices over cyclic groups
- A survey on tight Euclidean \(t\)-designs and tight relative \(t\)-designs in certain association schemes
- Asymptotic enumeration of sparse uniform hypergraphs with given degrees
- Combinatorics of NC-probability spaces with independent constants
- scientific article; zbMATH DE number 7124291 (Why is no real title available?)
- Chebyshev-type cubature formulas for doubling weighted spheres, balls, and simplexes
- Probabilistic existence of rigid combinatorial structures
- Asymptotic Enumeration of Hypergraphs by Degree Sequence
- Degree sequences of sufficiently dense random uniform hypergraphs
- The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- Existence of small ordered orthogonal arrays
- On perfect sequence covering arrays
- A polynomial construction of perfect sequence covering arrays
- Graph and hypergraph packing
- Transitivity in finite general linear groups
- Almost Steiner systems in finite classical polar spaces
- Nontrivial t-designs in polar spaces exist for all t
This page was built for publication: Probabilistic existence of regular combinatorial structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400828)
