Combinatorics Seminar

When: Sunday, March 25, 10am Where: Schreiber 309 Speaker: Alex Samorodnitsky, Hebrew University Title: An asymptotic Faber-Krahn inequality for the Hamming cube

Abstract:

Given a subset A of the Hamming cube H = {0,1}^n, let l(A) be the maximal eigenvalue of the subgraph of H induced by the vertices of A. Let l(a) be the maximum of l(A) over all subsets A with |A| = a.

The function l(a) was studied by Friedman and Tillich in connection with bounds for error-correcting codes. Following their terminology, we call the values of l(a) the Faber-Krahn (FK) minima and the optimal subsets attaining these values the FK minimizers for the cube.

We will explain the connection with error-correcting codes and give asymptotically tight bounds on l(a). In particular, the (asymptotic) FK minimizers for the cube are the Hamming balls.

The main step in our approach is a modification of the logarithmic Sobolev inequality for the Hamming cube. Time permitting, we will show this inequality also implies a modified hypercontractive inequality for the cube, which is stronger than the 'classical version' for functions with small support.