Computer Science/Discrete Mathematics Seminar II

Topic: Small-Set Expansion on the Grassmann Graph.

Speaker: Dor Minzer

Affiliation: Member, School of Mathematics

Date & Time: Tuesday October 23rd, 2018, 10:30am - 12:30pm

Location: Simonyi Hall 101

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.