Random Latin squares and 2-dimensional expanders

DOI10.1016/J.AIM.2014.12.015zbMATH Open1306.05020arXiv1307.3582OpenAlexW2140304656MaRDI QIDQ488979FDOQ488979

Alexander Lubotzky, Roy Meshulam

Publication date: 27 January 2015

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

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.

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

Recommendations

• On uniformly generating Latin squares
• Quasirandom Latin squares
• scientific article
• 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

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)

Cites Work

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

Cited In (13)

• Expansion of building-like complexes
• Isoperimetric inequalities for Ramanujan complexes and topological expanders
• Random Steiner systems and bounded degree coboundary expanders of every dimension
• Hamilton transversals in random Latin squares
• Ramanujan complexes and high dimensional expanders
• Quantitative aspects of acyclicity
• Bounded degree cosystolic expanders of every dimension
• Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes
• Coboundary expansion for the union of determinantal hypertrees
• Simplicial branching random walks
• Hypergraph expanders from Cayley graphs
• The first Cheeger constant of a simplex
• 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)