Randomly twisted hypercubes

A twisted hypercube of dimension k is created from two twisted hypercubes of dimension k−1 by adding a matching joining their vertex sets, with the twisted hypercube of dimension 0 consisting of one vertex and no edges. We generate random twisted hypercube by generating the matchings randomly at each step. We show that, asymptotically almost surely, joining any two vertices in a random twisted hypercube of dimension k there are k internally disjoint paths of length at most klgk+Oklg2k. Since the graph is k-regular with 2k vertices, the number of paths is optimal and the length is asymptotically optimal.