Computer Science/Discrete Mathematics Seminar I

Graph Vertex Expansion

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.

Date & Time

May 08, 2023 | 11:15am – 12:15pm

Location

Simonyi 101 and Remote Access

Speakers

Theo McKenzie

Affiliation

Harvard University