Probabilistic Existence of Regular Combinatorial Objects
Shachar Lovett from UCSD, along with Greg Kuperberg from UC Davis, and Ron Peled from Tel-Aviv University, explore the probabilistic existence of regular combinatorial objects like regular graphs, hyper-graphs, and k-wise permutations. They introduce novel probabilistic approaches to prove the existence of these objects with various underlying parameters, paving the way for new insights and advancements in combinatorial theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
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 hyper-graph 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 [Teirlinck 87] 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
125346 251643 361254 K-wise permutations Family of permutations acting uniformly on k elements A set F Snis k-wise if for any k distinct elements i1, ,ikand j1, ,jk ( )! n k n : ( ) = , ( ) = = |{ , }| | | F i j i j F 1 1 k k !
125346 251643 361254 K-wise permutations 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-Yaari 12] 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) doesn t hold Spencer s method not relevant
Probabilistic model Another viewpoint: sum of matrix rows t-subsets of [n] Incidence matrix 0100101001 1001011000 0000101110 Sample few rows Edges: k-subsets of [n] Analyze probability that sum is ( , , ) Pr[sum=expected sum] 0010110100
Probabilistic model Yet another viewpoint: short random walk on a lattice 0100101001 1001011000 0000101110 Lattice spanned by rows Steps: rows Probability that a short random walk will end in a specific point Can we guarantee fast convergence? 0010110100
Overview Regular combinatorial objects Probabilistic model Main Theorem: random walks on lattices Proof: Fourier analysis and codes Summary and open problems
General setup 0100101001 1001011000 0000101110 Matrix Sample N rows 0010110100 Pr[sum of rows= expected sum of rows] When can we guarantee it is positive?
General setup 0100101001 1001011000 0000101110 [Alon-Vu 97] example of regular hyper-graphs on n vertices, ~nn/2 edges, with no regular sub-hypergraphs 0010110100 Pr[sum of rows= expected sum of rows]=0 Conclusion: need to assume some structure
Main Theorem 0100101001 1001011000 0000101110 Main theorem: set of conditions that guarantee that Pr[sum of N rows= expected sum of rows]>0 0010110100 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)
A Main Theorem 0100101001 1001011000 0000101110 Some notation B A set of columns B set of rows (|B| >> |A|) V linear space spanned by columns 0010110100 row(b) row in index b B We want S B of size |S|=N such that 1 | | b S S 1 B = ( ) ( ) row b row b | | b B
A Main Theorem 0100101001 1001011000 0000101110 Pre-condition: divisibility B We want |S|=N for which 1 | | b S S 1 B 0010110100 = ( ) ( ) row b row b | | b B Let c1 be minimal integer such that c row B ( ) Lattice spanned by {row(b): b } b B 1 | |b B N must be a multiple of c1
A Main Theorem 0100101001 1001011000 0000101110 Pre-condition: divisibility B Example: t-(n,k, ) designs 0010110100 [Wilson 73, Graver-Jurkat 73] analyze divisibility of incidence matrices n t N multiple of 4t c 1
A Main Theorem 0100101001 1001011000 0000101110 Main condition: column span B V = space spanned by columns 0010110100 Need: (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
A Main Theorem 0100101001 1001011000 0000101110 V = space spanned by columns B Example: t-(n,k, ) designs 0010110100 (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)
A Main Theorem 0100101001 1001011000 0000101110 V = space spanned by columns B Example: t-(n,k, ) designs 0010110100 (b) V spanned by short integer vectors in l Immediate since matrix has small elements, so columns are such a basis for V
A Main Theorem 0100101001 1001011000 0000101110 V = space spanned by columns B Example: t-(n,k, ) designs 0010110100 (c) V spanned by short integer vectors in l1 Usually the hardest condition to verify; for designs, requires some combinatorial calculations
A Main Theorem 0100101001 1001011000 0000101110 V = space spanned by columns B Example: t-(n,k, ) designs 0010110100 (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 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 Conditions on V as a code (over the 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
A Proof of main theorem 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]] = ?
A Proof of main theorem 0100101001 1001011000 0000101110 B X = sum of selected rows Pr[X=E[X]] = ? 0010110100 Main tool: Fourier analysis Fourier coefficients of X: ( ) b B i row b = + 2 ( ), (1 ( 1)) X p e
A Proof of main theorem 0100101001 1001011000 0000101110 B X = sum of selected rows Fourier coefficients of X: ( ) b B 0010110100 i row b = + 2 ( ), (1 ( 1)) X p e Maximal Fourier coefs form a lattice: { : ( ) 1} { : X = = L = ( ), } 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): q-analogs
Open problems Algorithms Current proof is purely existential Don t 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 Spencer s theorem: Bansal, L-Meka
