Expansion and isoperimetric constants for product graphs (Q858145)

The authors study isoperimetric constants of graphs with analytic methods. They give lower bounds on the so-called expansion (introduced by Alon) of a Cartesian product. As a special case they prove that for every graph \(G\) the order of magnitude of the expansion of the \(n\)th power is \(\frac{1}{\sqrt{n}}\). They also prove similar theorems for other concepts of expansion defined in terms of inner or symmetric vertex boundary (instead of the most usual outer vertex boundary).