## 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.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 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

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.

No credit card required