# Probabilistic existence of regular combinatorial objects Probabilistic existence of regular combinatorial objects Shachar Lovett (UCSD) Joint with Greg Kuperberg (UC Davis), Ron Peled (Tel-Aviv university) Overview Regular combinatorial objects Probabilistic model Main Theorem: random walks on lattices Proof: Fourier analysis and codes Summary and open problems Overview Regular combinatorial objects

Probabilistic model Main Theorem: random walks on lattices Proof: Fourier analysis and codes Summary and open problems Regular objects highly symmetric objects Regular graphs Regular hyper-graphs (aka designs) K-wise permutations Orthogonal arrays q-analogs Constructions known in some special cases

This work: First existence proofs for (nearly) all underlying parameters by a probabilistic argument Regular graphs (n,d) regular graph n vertices, all of degree d Easy to construct Regular hyper-graphs Also known as designs t-(n,k,) design: k-uniform hypergraph on n vertices; any t vertices belong to exactly edges 1-(n,2,d) design: regular graph Regular hyper-graphs

t-(n,k,) design: k-uniform hyper-graph on n vertices; any t vertices belong to exactly edges Constructions: Small values based on group symmetries [Teirlinck87] first asymptotic construction of t-(n,t+1,) designs for infinitely many n, Few other asymptotic constructions Regular hyper-graphs t-(n,k,) design: k-uniform hyper-graph on n vertices; any t vertices belong to exactly edges Existence unknown for most parameters: Steiner systems: t-(n,k,1) designs, open for t>5

Hadamard matrices: 2-(4m-1,2m-1,m-1) designs In general, constructions (and existence) unknown for almost all parameters K-wise permutations 125346 251643 361254 Family of permutations acting uniformly on k elements A set FSn is k-wise if for any k distinct elements i1,,ik and j1,,jk

(n k )! |{ F : (i1 ) j1 , , (ik ) jk }| |F| n! K-wise permutations 125346 251643 361254 Family of permutations acting uniformly on k elements Constructions: Subgroups of Sn: k=1,2,3 (e.g. for k=2 and n

prime, subgroup of affine maps {x->ax+b}) Fail for k>3 (only Sn or An are 4-wise for n>24) [Finucane-Peled-Yaari12] Combinatorial constructions for small k of exponential size Other examples Orthogonal arrays: subsets of [c]n where any k coordinates get all values equally often (aka k-wise independent functions [n]->[c]) q-analogs: Family of k-dimensional subspaces of Fqn which cover uniformly all the t-dimensional subspaces (eg designs for the Grassmanian) Spherical designs: family of points on Sn which allow to integrate low degree polynomials by

summing over the points Our approach Probabilistic construction General technique to prove existence of regular objects Prove existence of designs, k-wise permutations, orthogonal arrays, for (nearly) all underlying parameters; of optimal size up to polynomial overhead Overview Regular combinatorial objects Probabilistic model Main Theorem: random walks on lattices

Proof: Fourier analysis and codes Summary and open problems Probabilistic model Running example: t-(n,k,) designs k-uniform hyper-graph on n vertices; any t vertices belong to exactly edges Random construction: Sample N=N(n,k,t,) edges uniformly Analyze probability that any t vertices covered by exactly edges Very unlikely event Probabilistic model

Random constructions unlikely to work But is probability zero or tiny but positive? How can we analyze rare events ? Standard tools fail, e.g. Limited dependence (e.g. Lovasz Local lemma) doesnt hold Spencers method not relevant Probabilistic model Another viewpoint: sum of matrix rows Incidence matrix Edges:

ksubsets of [n] t-subsets of [n] 010010100 1 100101100 0 000010111 0 001011010 0

Sample few rows Analyze probability that sum is (,,) Pr[sum=expected sum] Probabilistic model Yet another viewpoint: short random 010010100 walk on a lattice Lattice spanned by rows Steps: rows 1

100101100 0 000010111 0 Probability that a short random walk will end in a specific point 001011010 0 Can we guarantee fast convergence? Overview

Regular combinatorial objects Probabilistic model Main Theorem: random walks on lattices Proof: Fourier analysis and codes Summary and open problems General setup Matrix 010010100 1 100101100 0 000010111 0

Sample N rows Pr[sum of rows= expected sum of rows] 001011010 0 When can we guarantee it is positive? General setup [Alon-Vu97] example of regular hyper-graphs on n vertices, ~nn/2 edges, with no regular

sub-hypergraphs 010010100 1 100101100 0 000010111 0 001011010 0 Pr[sum of rows= expected sum of rows]=0

Conclusion: need to assume some structure Main Theorem Main theorem: set of conditions that guarantee that Pr[sum of N rows= expected sum of rows]>0 N is polynomial in underlying parameters In our applications we get optimal N (up to polynomial factors) Can approximate probability up to 1+o(1) 010010100

1 100101100 0 000010111 0 001011010 0 010010100 A 1 100101100 0

000010111 0 Main Theorem Some notation B A set of columns B set of rows (|B| >> |A|) V linear space spanned by columns row(b) row in index bB We want SB of size |S|=N such that 1

1 row(b) row(b) | S | bS | B | bB 001011010 0 010010100 A

1 100101100 0 000010111 0 Main Theorem Pre-condition: divisibility We want |S|=N for which 1 1 row(b) row(b)

| S | bS | B | bB B 001011010 0 Let c1 be minimal integer such that c1 row(b) Lattice spanned by {row(b): b B}

| B | bB N must be a multiple of c1 010010100 A 1 100101100 0 000010111 0 Main Theorem Pre-condition: divisibility B

Example: t-(n,k,) designs [Wilson73, Graver-Jurkat73] analyze divisibility of incidence matrices n t c1 4 N multiple of t 001011010 0

010010100 A 1 100101100 0 000010111 0 Main Theorem Main condition: column span B V = space spanned by columns

Need: 001011010 0 (a) V has transitive symmetry group (b) V spanned by short integer vectors in l (c) V spanned by short integer vectors in l1 (in coding terms, V is an LDPC) (d) V contains the constant vectors Main Theorem B V = space spanned by columns

010010100 A 1 100101100 0 000010111 0 Example: t-(n,k,) designs 001011010 0 (a) V has transitive symmetry group

Sn acts as permutations on k-subsets (rows) and t-subsets (columns) Acts transitively on rows (e.g. B) Main Theorem V = space spanned by columnsB 010010100 A 1 100101100 0 000010111 0

Example: t-(n,k,) designs 001011010 0 (b) V spanned by short integer vectors in l Immediate since matrix has small elements, so columns are such a basis for V Main Theorem V = space spanned by columnsB 010010100 A 1

100101100 0 000010111 0 Example: t-(n,k,) designs 001011010 0 (c) V spanned by short integer vectors in l1 Usually the hardest condition to verify; designs, requires some combinatorial calculations

for Main Theorem B V = space spanned by columns 010010100 A 1 100101100 0 000010111 0

Example: t-(n,k,) designs 001011010 0 (d) V contains the constant vector Sum of columns is constant A Main Theorem 0100101001 1001011000 0000101110

B B x A matrix, V=span(columns) 0010110100 Assume c1 divisibility constant V spanned by integer vectors with l bound c2 V spanned by integer vectors with l1 bound c3 V has transitive symmetry group V contains the constant vectors Then for N=poly(|A|,c1,c2,c3),

Pr[sum of N rows= expected sum]>0 In fact, we approximate the probability up to 1+o(1) A Main Theorem 0100101001 1001011000 0000101110 B

B x A matrix, V=span(columns) 0010110100 Assume c1 divisibility constant Conditions V spanned by integer vectors with l bound c2 on cV3 as a V spanned by integer vectors with l1 bound code (over V has transitive symmetry group the V contains the constant vectors

rationals) Then for N=poly(|A|,c1,c2,c3), Pr[sum of N rows= expected sum]>0 In fact, we approximate the probability up to 1+o(1) Applications Optimal size up to polynomial overhead Can count the number of objects (up to 1+o(1)) Existence of t-(n,k,) designs with N=(n/t)O(t) Verification of conditions relatively simple Existence of k-wise permutations with N=nO(k) permutations Verification of conditions was harder; required nontrivial

representation theory of Sn Orthogonal arrays Overview Regular combinatorial objects Probabilistic model Main Theorem: random walks on lattices Proof: Fourier analysis and codes Summary and open problems Proof of main theorem A 0100101001

1001011000 0000101110 B N - Target #rows 0010110100 Choose each row with prob p=N/|B| X = sum of selected rows (random var) Pr[X=E[X]] = ?

Proof of main theorem B X = sum of selected rows Pr[X=E[X]] = ? Main tool: Fourier analysis Fourier coefficients of X: 2 i row ( b ), X ( ) (1 p(e 1)) bB A

0100101001 1001011000 0000101110 0010110100 Proof of main theorem A 0100101001 1001011000 0000101110 B

X = sum of selected rows Fourier coefficients of X: 0010110100 2 i row ( b ), X ( ) (1 p(e 1)) bB Maximal Fourier coefs form a lattice:

L { : X ( ) 1} { : row(b), } Proof of main theorem Fourier space Maximal Fourier coefs Proof of main theorem Fourier space Maximal Fourier coefs Step I: approximate F.C. near maximas Gaussian approximation Relatively straight-forward Proof of main theorem

Fourier space Maximal Fourier coefs Step II: bound F.C. far from maximas Most Fourier space Harder step, requires all the conditions on V Develop new connections between coding properties of V and the Fourier coefs Proof of main theorem End result: Gaussian approximation, restricted to the lattice in which X lives X = sum of N rows Y = Gaussian with same covariance as X Pr[X=E[X]] density of Y at E[X]

times some lattice related factors Overview Regular combinatorial objects Probabilistic model Main Theorem: random walks on lattices Proof: Fourier analysis and codes Summary and open problems Summary New probabilistic technique Theorem: can prove existence of regular structures by verification of a few conditions, which are verified explicitly

This is in contrast to the existence result which is non-explicit Summary Proof technique: Fourier analysis Make new connections between coding theory and Fourier analysis in order to bound Fourier coefficients Open problems Applications Work in progress (with Kuperberg and Peled): spherical designs Work in progress (with Vardy): qanalogs

Open problems Algorithms Current proof is purely existential Dont know how to find objects efficiently, even using randomness Other probabilistic techniques for rare events were made algorithmic, so there is hope Lovasz local lemma: Moser, Moser-Tardos Spencers theorem: Bansal, L-Meka