Distributed Computing FS 2013
Prof R. Wattenhofer, Michael König · 2013
Generally, observe that N = |V (Pn) | = n! ∈ O(n n) ⇒ n ∈ O( log N log log N). a) See Figure 1. For drawing Pn, first draw n copies of Pn−1, each of which will have some j ∈ {1,..., n} fixed as the last vertex. The edges corresponding to reversing prefixes of length n − 1 or less are the links within such a copy of Pn−1. The other links connect Pn−1|v1 with Pn−1|vn. Fixing v1 and vn, there are (n − 2)! links between Pn−1|v1 and Pn−1|vn, as in each copy of Pn we have |Sn−2 | = (n − 2)! many nodes whose first and last component are v1 and vn, respectively, and each of the links in question connects two of them.