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.5 Distances in n-Cubes

In this section we analyze for which probabilities, λn, random induced subgraphs of n-cube exhibit “short” distances. To be precise, we ask for which λn does there exist some constant Δ such that

images

Before we give the main result of this section we prove a combinatorial lemma [21]. A weaker version of this lemma is proved in [6].

Lemma 5.8 Let dimages,d ≥ 2, and let v, v′ be two Qn2-vertices where d(v, v′) = d. Then any Qn2-path from v to v′ has length 2l + d, and there are at most

images

Qn2-paths from v to vof length 2l + d.

Proof. W.l.o.g. we can assume v =(0,...,0) and v′ =(xi)i, where xi=1 for 1 ≤ id, and xi = 0 otherwise. Each path of length m induces the family of steps (εs)1≤sm, where εs∈{ej| 1 ≤ jn}. Since the path ends at v′, we have for fixed 1 ≤ jn

images

Hence the families induced by our paths contain necessarily the set {e1,..., ed}. Let (ε′s)1≤sm be the family obtained from (εs)1≤sm by removing the steps e1,..., ed at the smallest index at which they occur. Then (ε′s)1≤sm represents a cycle starting and ending at v. Furthermore, we have for all

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