Monotone Expanders and Applications
Monash University, Australia

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 Sidiropoulos.