Dor Minzer

Member, School of Mathematics

October 23, 2018

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.

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.