Analysis of Complex Networks

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 Qⁿ₂-vertices where d(v, v′) = d. Then any Qⁿ₂-path from v to v′ has length 2l + d, and there are at most

Qⁿ₂-paths from v to v′ of length 2l + d.

Proof. W.l.o.g. we can assume v =(0,...,0) and v′ =(x_i)_i, where x_i=1 for 1 ≤ i ≤ d, and x_i = 0 otherwise. Each path of length m induces the family of steps (ε_s)_1≤s≤m, where ε_s∈{e_j| 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 {e₁,..., e_d}. Let (ε′_s)_1≤s≤m′ be the family obtained from (ε_s)_1≤s≤m by removing the steps e₁,..., e_d 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