Tutte Colloquium - Hao Huang

Friday, May 14, 2021 3:30 pm - 3:30 pm EDT (GMT -04:00)

Title: Interlacing methods in Extremal Combinatorics

Speaker: Hao Huang
Affliliation: Emory University
Zoom: Contact Emma Watson

Abstract:

Extremal Combinatorics studies how large or how small a collection of finite objects could be, if it must satisfy certain restrictions. In this talk, we will discuss applications of spectral graph theory, more specifically eigenvalue interlacing, to prove various interesting results in Extremal Combinatorics. We will discuss the Erdos-Ko-Rado Theorem and its degree version, an isodiametric inequality for discrete cubes, and the resolution of a thirty-year-old open problem in Theoretical Computer Science, the Sensitivity Conjecture of Nisan and Szegedy. Several open problems will also be mentioned during this talk.