Optimal Small Set Expanders and Their Codes

Abstract

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 yields new "transfer" lower bounds on the number of neighbors of sets of size h greater than or equal to s. Finally, as an application, we discuss the use of optimal small-set expanders in building good codes for key exchange protocols in post-quantum cryptography.