Spring 2017

Hypergraph Expanders from Cayley Graphs

Wednesday, Jun. 20, 2018 9:30 am10:15 am

Add to Calendar

Given a $k$-uniform hypergraph $H$, consider the associated graph whose vertex set consists of the $(k-1)$-tuples of vertices in $V(H)$ which are contained in some edge and where two vertices are joined if there is an edge of $H$ containing both. We say that $H$ is an expander if this associated graph is an expander. Using Cayley graphs over elementary abelian 2-groups, we give a randomisable construction of such expanders whose degree is polylogarithmic in the number of vertices. Partly based on joint work with Jonathan Tidor and Yufei Zhao.