Random Steiner systems and bounded degree coboundary expanders of every dimension

DOI10.1007/S00454-018-9991-2zbMATH Open1426.05183arXiv1512.08331OpenAlexW2963586772WikidataQ129974749 ScholiaQ129974749MaRDI QIDQ2334503FDOQ2334503

Authors: Zur Luria, Ron Rosenthal, Alexander Lubotzky 

Publication date: 7 November 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We introduce a new model of random $d$-dimensional simplicial complexes, for $dgeq2$, whose $(d-1)$-cells have bounded degrees. We show that with high probability, complexes sampled according to this model are coboundary expanders. The construction relies on Keevash's recent result on designs [Ke14], and the proof of the expansion uses techniques developed by Evra and Kaufman in [EK15]. This gives a full solution to a question raised in [DK12], which was solved in the two-dimensional case by Lubotzky and Meshulam [LM13].

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

Recommendations

• Coboundary expanders
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Random Latin squares and 2-dimensional expanders

zbMATH Keywords

simplicial complexesSteiner systemsdesignscoboundary expansion

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) Orthogonal arrays, Latin squares, Room squares (05B15) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Title not available (Why is that?)
• Expansion of building-like complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Expander graphs and their applications
• Homological connectivity of random k -dimensional complexes
• Ramanujan complexes and high dimensional expanders
• Random Latin squares and 2-dimensional expanders
• Coboundary expanders
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On Gromov's method of selecting heavily covered points
• Homological connectivity of random 2-complexes
• Counting designs
• Isoperimetric inequalities in simplicial complexes
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Inverse expander mixing for hypergraphs
• A Cheeger-type inequality on simplicial complexes
• Mixing in high-dimensional expanders
• On expansion and topological overlap
• Overlap properties of geometric expanders
• Mixing properties and the chromatic number of Ramanujan complexes
• A proof of Alon’s second eigenvalue conjecture and related problems
• Expansion of random graphs: new proofs, new results
• Ramanujan complexes of type \(\widetilde A_d\)
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Harmonic functions and boundary value problems on a chain complex
• Ramanujan hypergraphs
• Finite quotients of Bruhat-Tits buildings as geometric expanders
• Simplicial complexes: spectrum, homology and random walks
• Higher Dimensional Cheeger Inequalities
• Minors in random and expanding hypergraphs
• Spectra of combinatorial Laplace operators on simplicial complexes
• On the chromatic number of a simplicial complex
• Random walks on simplicial complexes and harmonics
• Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
• Eigenvalue confinement and spectral gap for random simplicial complexes

Cited In (9)

• Expansion of building-like complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Coloured and directed designs
• Random Simplicial Complexes: Models and Phenomena
• Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes
• Coboundary expanders
• Coboundary expansion for the union of determinantal hypertrees
• Simplicial branching random walks
• Hypergraph expanders from Cayley graphs

This page was built for publication: Random Steiner systems and bounded degree coboundary expanders of every dimension

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