Optimal Small Set Expanders and Their Codes (opens in new tab)

A left-regular bipartite graph $G$ of degree $d$ is called a $(t,\alpha)$-small-set-expander if every subset $X$ of left vertices of size at most $t$ has at least $\alpha |X|$ neighbors. Such a graph is an optimal small-set expander if small subsets have as many neighbors as possible. We characterize optimal expanders combinatorially via girth and prove the existence of $s$-optimal expanders for every $s$. We also prove that $s$-optimality yie...