{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-22","reactions":{}}