Optimal Small Set Expanders and Their Codes.

A left-regular bipartite graph G of degree d is called a (t,α)-small-set-expander if every subset X of left vertices of size at most t has at least α|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≥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.