In this section we present three theorems, instrumental for our analysis of connectivity, large components, and distances in *n*-cubes. The first result is due to [4] used for Sidon sets in groups in the context of Cayley graphs. In what follows *G* denotes a finite group and *M* a finite set acted upon by *G*.

**Proposition 5.1** *Suppose G acts transitively on M and let A* ⊂ *M. Then we have*

*Proof*. We prove Equation (5.8) by induction on |*A*|. For *A* ={*x*} we derive, since |*M*| = |*G*|/|*G _{x}*|. We next prove the induction step. We write

Aldous [2, 3] observed how to use Proposition 5.1 for deriving a very general lower bound for vertex boundaries in Cayley graphs:

**Theorem 5.1** *Suppose G acts transitively on M and let A* ⊂ *M, and let S be a generating set of the Cayley graph* Cay(*G*, *S*), *where* |*S*| = *n. Then we have*

*Proof*. We compute

and hence . From this we can immediately ...

Start Free Trial

No credit card required