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
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 d∈ ,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
Qn2-paths from v to v′ of length 2l + d.
Proof. W.l.o.g. we can assume v =(0,...,0) and v′ =(xi)i, where xi=1 for 1 ≤ i ≤ d, and xi = 0 otherwise. Each path of length m induces the family of steps (εs)1≤s≤m, where εs∈{ej| 1 ≤ j ≤ n}. Since the path ends at v′, we have for fixed 1 ≤ j ≤ n
Hence the families induced by our paths contain necessarily the set {e1,..., ed}. Let (ε′s)1≤s≤m′ be the family obtained from (εs)1≤s≤m by removing the steps e1,..., ed at the smallest index at which they occur. Then (ε′s)1≤s≤m′ represents a cycle starting and ending at v. Furthermore, we have for all
Get Analysis of Complex Networks now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.