Computer Science/Discrete Mathematics Seminar II
Small-Set Expansion on the Grassmann Graph.
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.