On the Number of Elements Dominated by a Subgroup

Abstract

We obtain lower bounds for the number of elements dominated by a subgroup in a Cayley graph. Let \(G\) be a finite group and let \(U\) be a generating set for \(G\) such that \(U = U^{-1}\) and \(1 \in U\). Let \(A\) be an independent subgroup of \(G\). Let \(r\) be a positive integer, and suppose that, in the Cayley graph \((G,U)\), any two non-adjacent vertices have at most \(r\) common neighbours. Let \(N[H]\) denote the set of elements of \(G\) which are dominated by the elements of \(H\). We prove that

1. \(|N[A]| \geq \lceil\frac{|U|^2}{r(|H \cup U^2|-1)+|U|}\rceil.\)
2. \(|N[A]| \geq |U||H| -\frac{|H|r}{2}(|H \cup U^2|-1).\)

An interesting example illustrating these results is the graph on the symmetric group \(S_n\), in which two permutations are adjacent if one can be obtained from the other by moving one element. For this graph we show that \(r = 4\) and illustrate the inequalities.