Random Latin squares and 2-dimensional expanders

DOI10.1016/J.AIM.2014.12.015MaRDI QIDQ488979zbMATH OpenOpenAlexFDO

Authors Alexander Lubotzky, Roy Meshulam

Publication date 27 January 2015

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

simplicial complexesexpansionrandom complexes

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Simplicial sets and complexes in algebraic topology (55U10) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: Let X be a 2-dimensional simplicial complex. The degree of an edge e is the number of 2-faces of X containing e. The complex X is an epsilon-expander if the coboundary d_1(phi) of every Z_2-valued 1-cochain phi in C^1(X;Z_2) satisfies |support(d_1(phi))| geq epsilon |supp(phi+d_0(psi))| for some 0-cochain psi. Using a new model of random 2-complexes we show the existence of an infinite family of 2-dimensional epsilon-expanders with maximum edge degree d, for some fixed epsilon>0 and d.

Recommendations

• On uniformly generating Latin squares
• Quasirandom Latin squares
• scientific article; zbMATH DE number 3887706
• Intercalates and discrepancy in random Latin squares
• Transversals in quasirandom latin squares
• Large deviations in random latin squares
• Random Latin square graphs
• Generating uniformly distributed random latin squares
• A Ramsey type result for Latin squares

Cites work

• scientific article; zbMATH DE number 3618783 (Why is no real title available?)
• A course in combinatorics.
• A proof of Alon’s second eigenvalue conjecture and related problems
• Coboundary expanders
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Global versus local asymptotic theories of finite-dimensional normed spaces
• Homological connectivity of random 2-complexes
• Homological connectivity of random k -dimensional complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Overlap properties of geometric expanders
• Ramanujan complexes and high dimensional expanders
• Ramanujan complexes of type \(\widetilde A_d\)
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups

Cited in

(12)

• Hypergraph expanders from Cayley graphs
• Quantitative aspects of acyclicity
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• The first Cheeger constant of a simplex
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• Hamilton transversals in random Latin squares
• Simplicial branching random walks
• Ramanujan complexes and high dimensional expanders
• Coboundary expansion for the union of determinantal hypertrees
• Expansion of building-like complexes
• Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes
• On the structure of random graphs with constant \(r\)-balls

This page was built for publication: Random Latin squares and 2-dimensional expanders

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