Small-Set Expansion on the Grassmann Graph.

Computer Science/Discrete Mathematics Seminar II
Topic:Small-Set Expansion on the Grassmann Graph.
Speaker:Dor Minzer
Affiliation:Member, School of Mathematics
Date:Tuesday, October 23
Time/Room:10:30am - 12:30pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2018/1023-DorMinzer

A graph G is called a small set expander if any small set of vertices contains only a small fraction of the edges adjacent to it. This talk is mainly concerned with the investigation of small set expansion on the Grassmann Graphs, a study that was motivated by recent applications to Probabilistically Checkable Proofs and hardness of approximation. 

For a vector space $V$ over a finite field and an integer parameter $\ell$, the vertices of the Grassmann Graph are all $\ell$-dimensional subspaces of $V$, and two subspaces are connected by an edge if they intersect in dimension $\ell-1$. In this talk, we will see that this graph is not a small set expander, formulate a qualitative characterization of all of the small-sets that prevent it from being a small-set expander, and prove a special case of it. 

The talk does not assume any special knowledge from the audience.