The Faber-Krahn problem for the Hamming cube

Combinatorics Seminar
Friday, April 16, 2010 - 15:05
1 hour (actually 50 minutes)
Skiles 255
Professor, Hebrew University (Jerusalem, Israel)
The Faber-Krahn problem for the cube deals with understanding the function, Lambda(t) = the maximal eigenvalue of an induced t-vertex subgraph of the cube  (maximum over all such subgraphs).  We will describe bounds on Lambda(t), discuss connections to isoperimetry and coding theory, and present some conjectures.