Computer Science/Discrete Mathematics Seminar I

In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as the connection between vertex and spectral expansion is limited. We discuss successful attempts to create unique neighbor expanders (a weak version of vertex expansion), as well as limitations in using common combinatorial methods to create stronger expanders.