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]|\ge \lceil \frac{|U{|}^2}{r(|H\cup U^2|-1)+|U|}\rceil .$
2. $|N[A]|\ge |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.