School Seminars and Colloquia

Monotone expanders and applications

Discrete Structures and Algorithms Seminar

by David Wood

Institution: Monash University
Date: Tue 21st February 2017
Time: 11:00 AM
Location: Russell Love Theatre, Peter Hall Building

Abstract: Expanders are classes of highly connected graphs that are of fundamental importance in graph theory, with numerous applications in
computer science, group theory and number theory. In a breakthrough
result that resolved an old open problem in complexity theory, Jean Bourgain recently constructed so-called d-monotone bipartite expanders, for some constant d. We consider the question of how small can d be. We answer this question by constructing 3-monotone expanders, which is best possible since 2-monotone graphs are planar. Similarly, we construct bipartite expanders that have 3-page book embeddings, 2-queue layouts, and 4-track layouts. All these results are best possible. The talk will only assume an elementary background in graph theory. Joint work with Vida Dujmovińá and Anastasios

For More Information: Contact: Sanming Zhou. email: