An isoperimetric problem in Cayley graphs (Q1818087)

A graph \(\Gamma\) is said to be \(k\)-separable if there is a subset \(X\) of \(V\) such that \(|X|\geq k\) and \(|\delta X|\geq k\). If \(\Gamma\) is \(k\)-separable, the \(k\)-isoperimetric number of \(\Gamma\) is \(\kappa_k(\Gamma)= \min\{|\delta X|:|X|\geq k\) and \(|\delta X|\geq k\}\). The authors develop a method to study \(k\)-isoperimetric numbers of Cayley graphs. The main result is the following theorem: Let \(T\) be a minimal generating set of a group \(G\) and \(\Gamma= \text{Cay}(G, T\cup T^{-1})\). If \(\Gamma\) is 2-separable, then one of the following conditions holds: (i) \(\kappa_2(\Gamma)= d_2(\Gamma)\), where \(d_2\) is the minimal cardinality of the boundary of two points. (ii) \(\Gamma\) is regular of degree 4 and \(T= \{s,t\}\) with \(s^3= t^3= 1\) and \((st^{-1})^2= 1\). Thus, if \(|S|> 4\), every cutset of cardinality less than \(d_2\) must isolate a single vertex.