Multi-way expanders and imprimitive group actions on graphs

Abstract

For n at least 2, the concept of n-way expanders was defined by various researchers. Bigger n gives a weaker notion in general, and 2-way expanders coincide with expanders in usual sense. Koji Fujiwara asked whether these concepts are equivalent to that of ordinary expanders for all n for a sequence of Cayley graphs. In this paper, we answer his question in the affirmative. Furthermore, we obtain universal inequalities on multi-way isoperimetric constants on any finite connected vertex-transitive graph, and show that gaps between these constants imply the imprimitivity of the group action on the graph.

Accepted in Int. Math. Res. Notices. 18 pages, rearrange all of the arguments in the proof of Main Theorem (Theorem A) in a much accessible way (v4); 14 pages, appendix splitted into a forthcoming preprint (v3); 17 pages, appendix on noncommutative L_p spaces added (v2); 12 pages, no figures