Rutgers Discrete Mathematics Seminar

Title: Using rectangular convolutions to construct biregular expanders

Speaker: Adam Marcus, Princeton

Date: Monday, February 12, 2018 2:00 pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


I will discuss recent advances in the technique we call "the method of interlacing polynomials'' --- a technique that uses polynomials as a way to prove existence theorems in linear algebra. Previous results used this method to show the existence of bipartite Ramanujan graphs of any size and degree, and subsequent progress was made in the work of Cohen in the form of a polynomial time construction. This talk will discuss some recent progress in extending these results to the case of biregular, bipartite expanders. Unlike classical Ramanujan graphs, these new constructions can have partitions of different sizes, making them more suitable for many applications.

This is joint work with Aurelien Gribinski.