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.