The diameter of random Schreier graphs

We give a combinatorial proof of the following theorem. Let G be any finite group acting transitively on a set of cardinality n . If S ⊆ G is a random set of size k , with k ≥ ( log n ) 1 + ɛ for some ɛ > 0 , then the diameter of the corresponding Schreier graph is O ( log k n ) with high probability. Except for the implicit constant, this result is the best possible.