## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## 5.2 Preliminaries

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  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 AM. Then we have Proof. We prove Equation (5.8) by induction on |A|. For A ={x} we derive , since |M| = |G|/|Gx|. We next prove the induction step. We write A = A0 ∪{x} and compute 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 AM, 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required