O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 [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 AM. Then we have

images

Proof. We prove Equation (5.8) by induction on |A|. For A ={x} we deriveimages, since |M| = |G|/|Gx|. We next prove the induction step. We write A = A0 ∪{x} and compute

images

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

images

Proof. We compute

images

and hence images. 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.

Start Free Trial

No credit card required