On Small Separations in Cayley Graphs
arXiv:1112.1970
Abstract
We present two results on expansion of Cayley graphs. The first result settles a conjecture made by DeVos and Mohar. Specifically, we prove that for any positive constant there exists a finite connected subset of the Cayley graph of such that . This yields that there can be no universal bound for for subsets of either infinite or finite vertex transitive graphs. Let be the Cayley graph of a finitely generated infinite group and finite such that is connected. Our second result is that if then has a ring-like structure.
arXiv comment9 pages, 2 figures