Monotone expansion

DOI10.1145/2213977.2214073MaRDI QIDQ5415535zbMATH OpenOpenAlexFDO

Authors Amir Yehudayoff, Jean Bourgain

Publication date 13 May 2014

Published in Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

expander graphsexplicit constructions

Mathematics Subject Classification ID

Connectivity (05C40) Graph theory (including graph drawing) in computer science (68R10)

Abstract: This work, following the outline set in [B2], presents an explicit construction of a family of monotone expanders. The family is essentially defined by the Mobius action of SL_2(R) on the real line. For the proof, we show a product-growth theorem for SL_2(R).

Recommendations

• Expansion in SL₂( R) and monotone expanders
• Monotone expanders: constructions and applications
• Expanders and dimensional expansion
• Limitations on Explicit Constructions of Expanding Graphs
• Strong uniform expansion in \(\text{SL}(2,p)\).

Cited in

(7)

• Monotonicity of auto-expansions
• Essentially every unimodular matrix defines an expander
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Monotone Case for an Extended Process
• Monotone expanders: constructions and applications
• Expansion in SL₂( R) and monotone expanders
• A spectral gap theorem in SU(d)

This page was built for publication: Monotone expansion

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