Id: arxiv/2606.23579 Url: https://arxiv.org/abs/2606.23579 Tags: math.CO, cs.CR, cs.IT Score: 0 Title: Optimal Small Set Expanders and Their Codes Domain: math.CO Source: arxiv Authors: Tristram Bogart, Marcelo Fiori, Pedro Raigorodsky, Mauricio Velasco Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-22 Page: https://delphi.science/r/arxiv/2606.23579 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\geq s$. Finally, as an application, we discuss the use of optimal small-set…