Near-independence of permutations and an almost sure polynomial bound on the

diameter of the symmetric group

László Babai^{∗} and Thomas P. Hayes^{†}

Abstract We address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group S_{n}. This is equivalent to polynomial-time (O(n^{c})) mixing of the (lazy) random walk on S_{n} where one step is multiplication by a generator or its inverse.

We prove that the conjecture is true for almost all pairs of generators. Specifically, our bound is Õ(n^{7}). For almost all pairs of generators, words of this length representing any given permutation can be constructed in Las Vegas polynomial time. The best previous bound on the word length for a random pair of generators was n^{ln n(1/2+o(1))} (Babai–Hetyei, 1992).

We build on recent major progress by Babai–Beals– Seress (SODA, 2004), confirming the conjecture under the assumption that at least one of the generators has degree < 0.33n.

The main technical contribution of the present paper is the following near-independence result for permutations. The first cycle of a permutation is the trajectory of the first element of the permutation domain. For a random permutation, the distribution of the length of the first cycle is uniform. We show that if τ ∈ S_{n} is a given permutation of degree ≥ n^{3/4} and σ ∈ S_{n} is chosen at random, then the distributions of the length of the first cycle of σ and the length of the first cycle in στ are nearly independent. The ability of an essentially arbitrarily fixed permutation (τ) to “scramble” another permutation in this technical sense may be of independent interest and suggests new directions in the statistical theory of permutations pioneered by Goncharov and Erdős–Turán.

∗Department of Computer Science, University of Chicago.

Email: laci@cs.uchicago.edu.

†Division of Computer Science, University of California Berkeley. Email: hayest@cs.uchicago.edu. Much of this work was done while the second author was visiting Toyota Technological Institute at Chicago.

1 Pairwise near-independence of permutations By a random element of a nonempty finite set S we mean an element chosen uniformly from S.

Given two independent random residue classes mod p, X and Y, one can easily generate p + 1 pairwise independent random residue classes: Y and X_{i} := X + iY (i = 0, 1, …, p − 1). This fact gives rise to a small universal family of hash functions and has been used in myriad ways in computer science in contexts where full independence would be too costly to achieve.

Given two independent random permutations τ, σ ∈ S_{n} (where S_{n} denotes the symmetric group of degree n, i. e., the set of n! permutations of an n-set), can we construct a large family of pairwise independent random permutations from them, using only multiplications and inversions? Clearly, σ, τ, and στ are pairwise independent, but it is easy to show that no four words in τ and σ can be pairwise independent.

Yet one would expect that τ and στ^{i} (i = 1, …, r) should be pairwise “nearly independent” for rather large values of r (like r = Ω(n); but r might even grow at a slightly superpolynomial rate). The question is, how to measure “near-independence” of permutations.

Definition 1.1. We say that a sequence of pairs of (real-valued) random variables X_{n} and Y_{n} is nearly independent if for all x, y ∈ ℝ,

Pr(X_{n} ≤ x and Y_{n} ≤ y)=Pr(X_{n} ≤ x)Pr(Y_{n} ≤ y)+o(1),

where the o(1) term approaches zero (uniformly in x and y) as n → ∞.

One of the most important parameters of a permutation π is the length of its first cycle, i. e., the length of the trajectory of the first point of the permutation domain: 1, 1^{π}, 1^{π^{2}}, . . .. For a random permutation π ∈ S_{n}, the length of the first cycle of π is uniformly distributed over {1, 2, …, n} (cf. [20, Ex.3.3]).

In this paper we show:

Theorem 1.2. Given a pair of independent random permutations τ, σ ∈ S_{n}, the lengths of the first cycles of the s + 1 permutations τ and στ^{i} (i = 1, …, s) are pairwise nearly independent up to s = n^{(7/32−o(1)) ln n}.

In fact, to generate this degree of pairwise nearindependence, we do not need the amount of randomness afforded by a pair of random permutations; one random permutation suffices. This is formalized in the next result which is the main technical contribution of this paper. The degree deg(τ) of a permutation τ is the number of elements moved by τ.

Theorem 1.3. Let us fix τ ∈ S_{n} and choose σ ∈ S_{n} at random. Assume deg(τ) ≥ n^{3/4}. Let Y denote the length of the first cycle of σ and X the length of the first cycle of στ. Then for all k, ℓ (1 ≤ k, ℓ ≤ n),

|Pr (X ≤ k and Y ≤ ℓ) − \frac{kℓ}{n^{2}} | ≤ n^{−1/8+o(1)}.

Here, the o(1) term approaches zero as n → ∞ uniformly in k and ℓ. The proof of Theorem 1.3 is presented in Sections 7 to 10.

The immediate motivation for these results is described in Sections 2, 3, and 6. We believe, however, that Theorem 1.3 is of wider interest and suggests a new direction in the statistical theory of permutations pioneered by Goncharov [15] and, in a series of papers, by Erdős and Turán [11, 12, 13] (see the Open Problems section).

2 Diameter of Cayley graphs Let G be a finite group and S a set of generators of G. We consider the undirected Cayley graph Γ(G, S) which has G as its vertex set; the pairs {{g, gs} : g ∈ G, s ∈ S} are the edges. Let diam(G, S) denote the diameter of Γ(G, S).

In this paper we consider the cases G = S_{n} and G = A_{n} (the symmetric group consisting of the n! permutations of a set of n elements, and the alternating group consisting of the n!/2 even permutations). We address the following long-standing conjecture.

Conjecture 2.1. ([7]) For G = S_{n} and G = A_{n}, the diameter diam(G, S) is polynomially bounded in terms of n for all sets S of generators.

The best upper bound known to hold for the diameter of all Cayley graphs of A_{n} and S_{n} is exp(\sqrt{n ln n}(1 + o(1))) [7].

Regarding random pairs of generators, Dixon’s classical result states that almost all pairs of permutations in S_{n} generate either S_{n} or A_{n} [9] (cf. [8, 2]).

The main result of the present paper shows that the generation a.a. leads to polynomial diameter:

Theorem 2.2. For almost all pairs of permutations S = {σ, τ} of G = S_{n} or A_{n}, the diameter of the Cayley graph Γ(G, S) is bounded by O(n^{C}) where C is a constant. (Our current estimate of C is 7 + o(1).)

The best previously known bound for almost all pairs of generators was n^{ln n(1/2+o(1))} [4].

3 Previous work The diameter of Cayley graphs has been studied in a number of contexts, including interconnection networks, expanders, puzzles such as Rubik’s cube and Rubik’s rings, card shuffling and rapid mixing, random generation of group elements, and combinatorial group theory.

Even and Goldreich [14] proved that finding the diameter of a Cayley graph of a permutation group is NP-hard even for the basic case when the group is an elementary abelian 2-group (every element has order 2). Jerrum [18] proved that for directed Cayley graphs of permutation groups, to find the directed distance between two permutations is PSPACE-hard. No approximation algorithm is known for distance in and the diameter of Cayley graphs of permutation groups. Strikingly, the question of the diameter of the Rubik’s cube Cayley graph appears to be wide open (cf. [19]). We refer to [5] for more information on the history of the diameter problem and related results and to the survey [16] for applications of Cayley graphs to interconnection networks.

Prior to [3], Conjecture 2.1 had only been verified for very special classes of generating sets. Driscoll and Furst [10] proved an O(n^{2}) bound for the case when all generators are cycles of bounded lengths and McKenzie [21] gave a polynomial bound for the case when the generators have bounded degree. Major progress on Conjecture 2.1 was made by Babai-Beals-Seress in [3].

Theorem 3.1. ([3]) Let S be a set of generators for G = S_{n} or G = A_{n}. Assume that S contains a permutation of degree ≤ 0.33n. Then diam(G, S) = O(n^{C}) where C is a constant.

The bound on C stated in [3] was 7 + o(1); and 6 + o(1) for bounded |S|.

For random pairs of generators, it was pointed out in [3] that Theorem 3.1 implies a polynomial bound on the diameter of the Cayley graphs of S_{n} and A_{n} with probability 1 − ε; but the exponent depended on ε > 0. The move from probability (1 − ε) to “almost all” (Theorem 2.2) was remarkably difficult and required new insights into the “near-independence” of deterministically related permutations. We believe that these insights bring us closer to settling Conjecture 2.1; and the new type of questions in the statistical theory of permutations initiated by Theorem 1.3 may have further applications.

4 Some statistical group theory Henceforth, we will assume n is sufficiently large. By an “almost certain” event we shall mean a sequence of events depending on the parameter n such that the probability of the events approaches 1 as n → ∞. The abbreviation “a.a.” (“almost always”) or equivalently, “almost surely,” etc., refers to such a sequence of events.

In this section we study the typical behavior of permutations. We shall use the following terminology.

Definition 4.1. Let σ ∈ S_{n} be a permutation acting on the set [n] = {1, …, n}. The “first cycle” of σ is the trajectory of 1; the second cycle is the trajectory of the smallest i that does not belong to the first cycle, etc. Let ℓ_{i} denote the length of the i-th cycle; set ℓ_{i} = 0 if the number of cycles is less than i. Let T_{i} denote the set of elements in [n] not covered by the first i − 1 cycles.

Observation 4.2. Let σ ∈ S_{n} be a random permutation. Given T_{k}, the restriction σ_{k} := (σ | T_{k}) is a random permutation of T_{k}. Consequently, ℓ_{k} is uniformly distributed in {1, …, |T_{k}|}.

First we give an explicit upper bound on the probability that a random permutation has very low order. This is required for the proof of Theorem 2.2 (Section 6).

Proposition 4.3. The probability that the order of a random permutation σ ∈ S_{n} is ≤ n is O(n^{−1/4}).

Proof. (Sketch.) We prove that the probability that l.c.m.[ℓ_{1}, ℓ_{2}] ≤ n is 1 − O(n^{−1/4}). It is easy to prove that with this probability, both ℓ_{1} and ℓ_{2} are greater than n^{3/4}, so it suffices to prove that the probability that g.c.d.(ℓ_{1}, ℓ_{2}) ≥ n^{1/4} is O(n^{−1/4}). To this end, we observe that for any d and i the probability that d | ℓ_{i}, conditioned under any sequence ℓ_{1}, …, ℓ_{i−1} such that ∑_{j=1}^{i−1} ℓ_{j} < n, is ≤ 1/d since ℓ_{i} is uniformly distributed in a prefix of the positive integers. Therefore, assuming ℓ_{1} < n, the probability that d | ℓ_{1} and d | ℓ_{2} is at most 1/d^{2}. Hence the probability that g.c.d.(ℓ_{1}, ℓ_{2}) ≥ r is less than 1/n plus ∑_{d=r}^{∞} 1/d^{2} < ∑_{d=r}^{∞} 1/d(d−1) = 1/(r−1). Apply this bound with r = n^{1/4}. □

The following result, the main result of this section, is is an ingredient in the proof of Theorem 1.2 (Section 11).

Theorem 4.4. For a permutation σ and a number K, let e(σ, K) denote the smallest j ≥ 1 such that deg(σ^{j}) ≤ K. Let us fix p, 0 < p < 1. Then, for a.a. σ ∈ S_{n}, we have e(σ, n^{p}) ≥ exp (((1 − p^{2})/2 − o(1)) ln^{2} n).

We shall use the following classical result of Erdős and Turán on the typical order of a permutation.

Theorem 4.5. (Erdős – Turán [11]) A.a., the order of a random permutation σ ∈ S_{n} is

ord(σ) = exp ((1/2 + o(1)) ln^{2} n) .

We shall also make use of the following result concerning the typical distribution of cycle lengths in a random permutation. For the notation see Def. 4.1.

Lemma 4.6. (Babai – Hetyei [4], Lemma 3.1) Let us fix r, 0 < r < 1, and let k = ⌊(1 − r) ln n⌋. Let σ ∈ S_{n} be a random permutation. Then a.a., |T_{k}| = n^{r(1+o(1))}.

Corollary 4.7. Using the notation of Lemma 4.6, a.a., the length of each of the first k cycles is at least n^{r(1+o(1))}.

Proof. Let us fix ε > 0. Recall Def. 4.1 and Obs. 4.2. Let us consider the following events.

• A : |T_{k}| ≤ n^{r−ε}. We have Pr (A) = o(1) by Lemma 4.6.

• A_{i} : |T_{i}| ≤ n^{r−ε}. Note that ⋃_{i=1}^{k} A_{i} = A_{k} = A.

• B_{i} : ℓ_{i} ≤ n^{r−2ε}.

Observe that Pr (B_{i} | ¬A_{i}) ≤ n^{−ε} because ℓ_{i} is uniform in {1, ..., |T_{i}|}.

• B : (∃i ≤ k)(ℓ_{i} ≤ n^{r−2ε}).

Now Pr (B) ≤ Pr (A) + Pr (B ∧ ¬A) ≤ Pr (A) + ∑_{i=1}^{k} Pr (B_{i} ∧ ¬A) ≤ Pr (A) + ∑_{i=1}^{k} Pr (B_{i} ∧ ¬A_{i}) ≤ Pr (A) + ∑_{i=1}^{k} Pr (B_{i} | ¬A_{i}) ≤ Pr (A) + kn^{−ε} = o(1), proving the claim. □

Proof of Theorem 4.4. Let us fix r such that 1 > r > p and let k = ⌊(1−r) ln n⌋. For convenience we shall omit rounding. Let us also fix ε > 0. As before, ℓ_{i} denotes the length of the i-th cycle in σ.

Let us consider the following events, all of which will be shown to have probability o(1). Fix ε > 0.

• B : (∃i < k)(ℓ_{i} ≤ n^{r−ε}).

We have Pr (B) = o(1) by Corollary 4.7.

• C: |T_{k}| > n^{r+ε}. We have Pr (D) = o(1) by Lemma 4.6.

• D : the order of σ_{k} := (σ | T_{k}) (the restriction of σ to T_{k}) is ord(σ) ≤ exp((ln^{2} |T_{k}|/2)(1 + ε)). We have Pr (D) ≤ Pr (C) + Pr (D | ¬C) = o(1). This follows from Theorem 4.5, noting that under condition ¬C, the restriction σ_{k} is a uniform random permutation of T_{k}.

• E : ord(σ_{k}) ≥ exp((r^{2}/2) ln^{2} n(1 + 2ε)).

E ⊆ D ∪ C so Pr (E) = o(1).

• F_{j} : deg(σ^{j}) ≤ n^{r−2ε}.

• F (s) : (∃j)(1 ≤ j ≤ s)(deg(σ^{j}) ≤ n^{r−2ε}).

Note that F (s) := ⋃_{j=1}^{s} F_{j}. Our goal is to prove that for appropriate choice of s, F (s) has vanishing probability.

• G_{j} : ord(σ) divides j ord(σ_{k}).

Note that F_{j} ⊆ B ∪ G_{j} since if ℓ_{i} > n^{r−2ε} for all i < k then the only way for σ^{j} to have degree ≤ |T_{k}| is to fix all points outside T_{k}.

• G(s) : ord(σ) ≤ s ord(σ_{k}).

So ⋃_{j=1}^{s} G_{j} ⊆ G(s), hence F (s) ⊆ B ∪ G(s).

• H(s) : ord(σ) ≤ s exp((r^{2}/2)(ln^{2} n)(1 + 2ε)).

• K : ord(σ) ≤ exp((ln^{2} n/2)(1 − ε)).

Note that Pr (K) = o(1) by Theorem 4.5.

Let now s = exp((1−r^{2} −ε)/2) ln^{2} n. Note that s < exp((ln^{2} n/2)(1 − ε)) − (r^{2}/2) ln^{2} n(1 + 2ε)). Therefore H(s) ⊆ K ∪ E; consequently, Pr (H(s)) = o(1). Note further that G(s) ⊆ H(s) ∪ E; therefore Pr (G(s)) = o(1). The relation F (s) ⊆ B ∪ G(s) then implies that Pr (F (s)) = o(1).

So for s = exp(((1 − r^{2} − ε)/2) ln^{2} n, the statement F (s) a.a. fails to hold. Noting that this is true for all r > p and all ε > 0, Theorem 4.4 follows. □

Finally we include an observation on cycle lengths, to be used in the proof of Theorem 1.3 (Section 10).

Proposition 4.8. For a random σ ∈ S_{n}, let X_{k} denote the total length of cycles of lengths ≤ k. Then, for every ℓ > 0, Pr (X_{k} ≥ ℓ) ≤ k/ℓ.

Proof. It is easy to see that E (X_{k}) = k; therefore the stated bound follows by Markov’s inequality. □

5 Tail Estimates In this section, we will present several general tail estimates which will be needed later. In particular, Theorem 5.6 will be one of the key ingredients in the proof of Theorem 1.3 (Section 10).

The following version of Chernoff’s bound is especially useful for variables with a “biased” distribution. This version is an immediate consequence of [22, Theorem 4.1, p. 68].

Theorem 5.1. (Chernoff) Let X_{1}, …, X_{N} be independent random variables, bounded by 0 ≤ X_{i} ≤ 1. Let X = ∑_{i=1}^{N} X_{i} have expectation μ. Then for every r > μ,

(5.1)  Pr (X ≥ r) ≤ (\frac{eμ}{r})^{r} .

For every r < μ,

(5.2)  Pr (X ≤ r) ≤ exp (\frac{−(μ − r)^{2}}{2μ} ) .

The following corollary will be used in the proof of Lemma 8.2.

Corollary 5.2. Let b, μ_{1}, …, μ_{N} be positive reals. Let μ = ∑_{i=1}^{N} μ_{i}. Suppose Y_{1}, …, Y_{N} is a sequence of random variables such that 0 ≤ Y_{i} ≤ b. Assume that, for every i ≥ 0, for every history Y_{1}, …, Y_{i−1}, the conditional expectation of the indicator of the event {Y_{i} ≠ 0} satisfies

Pr (Y_{i} ≠ 0 | Y_{1}, …, Y_{i−1}) ≤ μ_{i}.

Then, letting Y = ∑_{i=1}^{N} Y_{i}, for every s > 0,

Pr (Y ≥ s) ≤ (\frac{ebμ}{s})^{s/b} .

Proof. It is easy to construct independent random variables X_{1}, …, X_{N} with values in {0, 1}, satisfying the conditions of Theorem 5.1 such that E (X_{i}) = μ_{i} and bX_{i} ≥ Y_{i} holds with probability one. Substituting r = s/b in (5.1) completes the proof. □

Our next bound, on the size of the intersection of a given set with a random set, will be used in the proof of Lemma 8.1.

Lemma 5.3. Let T ⊆ V and α := |T |/n. Sample Π uniformly at random from among subsets of V of size t. Then

Pr (|Π ∩ T | ≤ αt/2) ≤ exp(−αt/8).

Proof. Generate Π by sampling t elements of V sequentially, without replacement. Note that, if this sampling were performed with replacement, the probability of the event |Π ∩ T | ≤ αt/2 would only increase, since

Pr (|Π ∩ T | ≤ αt/2 | |Π| = s)

would then clearly be a decreasing function of s. That the desired upper bound holds even when Π is sampled “with replacement” follows from (5.2). □

We will need the following extension of the (unbiased) Chernoff’s bound to real-valued martingales with bounded differences, due to W. Hoeffding [17], and often referred to as the Hoeffding-Azuma inequality (cf. [1, Thm.7.2.1]).

Theorem 5.4. (Hoeffding-Azuma) Let X_{0}, …, X_{n} be a real martingale, i. e., a random process such that E (X_{i} | X_{0}, …, X_{i−1}) = X_{i−1} for every i. Suppose further that |X_{i} − X_{i−1}| ≤ 1. Then, for every a ≥ 0,

Pr (X_{n} < X_{0} − a) ≤ exp (−a^{2}/2n) .

Finally, we will prove two concentration inequalities on the distributions of random subset sums. In the first case, we condition on the size of the subset.

Lemma 5.5. Let a_{1}, …, a_{m} ∈ [0, 1], let b = ∑_{i=1}^{m} a_{i}, and let k ∈ {1, …, m}. Let S be a random subset of {1, …, m} of size k, and let Y_{k} = ∑_{i∈S} a_{i}. Then, for every s > 0,

(5.3)  Pr (Y_{k} ≤ kb/m − s) < exp(−s^{2}/2k).

Proof. Define random variables Y_{0}, …, Y_{k} by first selecting ψ ∈ S_{m} uniformly at random, then setting Y_{i} = ∑_{j=1}^{i} a_{i^{ψ}}, for i ∈ {0, …, k}. Note that Y_{k} has the same distribution as in the lemma.

For 0 ≤ i ≤ k, set Z_{i} = E (Y_{k} | Y_{0}, …, Y_{i}), so that Z_{0}, …, Z_{k} is a (Doob) martingale. Note that Z_{0} = E (Y_{k}) = kb/m, and Z_{k} = Y_{k}. It is clear that, for all i, |Z_{i} − Z_{i−1}| ≤ 1. (In fact, an easy shuffling argument shows that |Z_{i} −Z_{i−1}| ≤ (m−k)/(m+1−i).)

Inequality (5.3) now follows from Theorem 5.4 applied to the deviation Z_{k} − Z_{0} = Y_{k} − kb/m. □

Next, we consider the case when k is chosen uniformly at random from {1, …, m}, and the random subset has size k. Theorem 5.6, which will be applied in the proof of Theorem 1.3 (Section 10), says that, as long as the set of values is not too skewed, the distribution of the sum is nearly uniform.

Theorem 5.6. Let m > 1, let a_{1}, …, a_{m} ∈ [0, 1], and let b = ∑_{i=1}^{m} a_{i}. Let k ∈ {1, …, m} be uniformly random, and let S be a randomly chosen subset of {1, …, m} of size k. Let Y = ∑_{i∈S} a_{i}. Then, for every x ∈ [0, b],

(5.4)  |Pr (Y ≤ x) − \frac{x}{b}| ≤ \frac{2\sqrt{m ln m}}{b}.

Proof. Assume b > 2\sqrt{m ln m}; otherwise the conclusion holds vacuously.

First, we estimate the probability that Y ≤ x. Define Y_{1}, …, Y_{m} as in the proof of Lemma 5.5. Then we can think of Y as Y_{k}, where k is uniformly random in {1, …, m}.

For every ℓ, we have

Pr (Y ≤ x) = \frac{1}{m} ∑_{k=1}^{m} Pr (Y_{k} ≤ x)

≤ \frac{ℓ}{m} + \frac{1}{m} ∑_{k=⌈ℓ⌉}^{m} Pr (Y_{k} ≤ x).

Let ℓ = (x + s)m/b, where s > 0 will be specified later. Then, by Lemma 5.5, for each k ≥ ℓ,

Pr (Y_{k} ≤ x) ≤ Pr (Y_{k} ≤ kb/m − s) ≤ exp(−s^{2}/2m),

and therefore,

(5.5)  Pr (Y ≤ x) ≤ \frac{x + s}{b} + exp(−s^{2}/2m).

Setting s = \sqrt{2m ln(b/\sqrt{m ln m})} ∈ [0, \sqrt{m ln m}], equation (5.5) implies

(5.6)  Pr (Y ≤ x) ≤ \frac{x}{b} + \frac{2\sqrt{m ln m}}{b}

Observing that the distribution of b − Y is identical to the distribution of Y, we infer that

(5.7)  Pr (b − Y ≤ b − x) ≤ \frac{b − x}{b} + \frac{2\sqrt{m ln m}}{b}.

Combining (5.6) and (5.7) yields (5.4). □

6 Almost sure diameter bound via pairwise near-independence: a Chebyshev argument In this section we deduce our main result, Theorem 2.2, from Theorem 3.1 combined with our “main technical contribution,” Theorem 1.3.

First we state a corollary to Theorem 1.3. For π ∈ S_{n}, we use c(π, i) to denote the π-cycle containing point i, so |c(π, 1)| is the length of the first cycle of π.

Corollary 6.1. Suppose τ ∈ S_{n} has degree at least n/4. Sample σ uniformly at random from S_{n}. Then the events A = {|c(σ, 1)| > 3n/4} and B = {|c(στ, 1)| > 3n/4} are nearly independent. More precisely, Pr (A) = 1/4 + o(1), Pr (B) = 1/4 + o(1), and Pr (A and B) = 1/16 + o(1).

The Chebyshev argument follows.

Lemma 6.2. Suppose τ ∈ S_{n} is such that for 1 ≤ i ≤ 10 log n, τ^{i} has degree at least n/4. Sample σ uniformly at random from S_{n}. Then, a.a., for at least one of the permutations στ^{i}, for 1 ≤ i ≤ 10 log n, the length of the first cycle is greater than 3n/4.

Proof. Let τ ∈ S_{n}, and suppose that each of τ, τ^{2}, …, τ^{10 log n} has degree at least n/4. Sample σ ∈ S_{n} uniformly at random.

For 1 ≤ i ≤ 10 log n, let A_{i} denote the event that |c(στ^{i}, 1)| > 3n/4. Since στ^{i} is distributed uniformly over S_{n}, |c(στ^{i}, 1)| is uniformly distributed over 1, …, n, and so Pr (A_{i}) = 1/4 + o(1).

By Corollary 6.1 applied to τ and σ, it follows that A_{0} and A_{1} are nearly independent. More generally, for 0 ≤ i < j ≤ 10 log n, applying Corollary 6.1 to τ^{j−i} (in place of τ) and στ^{i} (in place of σ), it follows that A_{i} and A_{j} are nearly independent.

Let X denote the number of events A_{i} which occur. Then X = ∑_{i=1}^{10 log n} X_{i}, where X_{i} denotes the indicator variable for event A_{i}. It follows that E (X) = Θ(log n) and Var (X) = o(log^{2} n). Hence, by Chebyshev’s inequality, Pr (X = 0) ≤ Var (X)/E (X)^{2} = o(1). Hence a.a., at least one of the events A_{i} occurs. □

Proof of Theorem 2.2, assuming Theorem 1.3. According to Theorem 3.1, it suffices to show that almost all pairs of permutations generate a nonidentity permutation of degree ≤ n/4 as a short word. This, in turn, follows from Lemma 6.2.

Indeed, either some τ^{i} has degree < n/4, or there is almost always some στ^{i} with a cycle of length j > 3n/4, where in both cases i ≤ 10 log n. In the latter case, (στ^{i})^{j} has degree < n/4.

Finally, we need to show that none of these permutations is the identity. Note that τ as well as every στ^{i} is uniformly distributed in S_{n}. Therefore the probability that either τ or any of the στ^{i} (1 ≤ i ≤ 10 log n) has order ≤ n is O(log n/n^{1/4}) by Proposition 4.3. □

7 Partial Permutation Graphs In this section we develop notation and terminology for a theory of partial permutation graphs which will provide the language for the asymptotic structure theory to follow in the subsequent sections.

Let V be a set of size n. For π ∈ Sym(V), let E_{π} = {(v, v^{π}) | v ∈ V } ⊆ V × V. Then the map π ↦ (V, E_{π}) defines a bijection between Sym(V) and the set of directed graphs on vertex set V such that every vertex has in-degree 1 and out-degree 1. We will refer to such graphs as permutation graphs. More generally, if G is a graph on vertex set V such that every in-degree and out-degree is at most 1, then we call G a partial permutation graph.

Notation 7.1. Let E ⊆ V^{2}. We will implicitly identify the edge set E with the graph (V, E). Except where otherwise specified, by “component” of E, we shall always mean “weakly connected component containing at least one edge.”

Definition 7.2. Let π ∈ Sym(V), let t ≥ 0, and let v ∈ V. The t-trajectory of v under π, denoted traj(v, π, t), is the partial permutation graph with edge set

{(v^{π^{j−1}}, v^{π^{j}}) | 1 ≤ j ≤ t}.

Note that (for t > 0) these edges form a connected subgraph of E_{π}, which is therefore either a path or a cycle, according to whether the π-cycle containing v has size greater than t or not. | traj(v, π, t)| is always the lesser of t and the size of the π-cycle containing v.

Definition 7.3. Let τ ∈ Sym(V). The τ-shear function is the map shear_{τ} : V^{2} → V^{2} defined by shear_{τ} (x, y) = (x, y^{τ}). For E ⊆ V^{2}, we define shear_{τ} (E) := {shear_{τ} (e) | e ∈ E}.

The shear operator provides a way of viewing composition of permutations as an edgewise operation on partial permutation graphs, which respects trajectories, as we now state formally.

Observation 7.4. Let σ, τ ∈ Sym(V), and set π = στ. Then

E_{π} = shear_{τ} (E_{σ}),

where E_{π} and E_{σ} denote the edge sets of the permutation graphs of π and σ, respectively.

Consequently, for every partial permutation ρ ⊆ σ, we have shear_{τ} (E_{ρ}) ⊆ E_{π}.

Definition 7.5. Let τ ∈ Sym(V). We say τ is fixedpoint-free if τ has degree n, i. e., for every v ∈ V, v^{τ} ≠ v.

Next we define a projection operator, which will be the key tool allowing us to apply results about fixedpoint-free τ to the general case.

Definition 7.6. For T ⊆ V, we define the projection π ↦ π_{T}, mapping Sym(V) → Sym(T), as follows. Let π ∈ Sym(V). For i ∈ T, let k denote the smallest positive integer such that i^{π^{k}} ∈ T. Set i^{π_{T}} = i^{π^{k}}.

We extend this notion to partial permutations π in the natural way: if there exists k such that i^{π^{k}} ∈ T, then take k minimal and set i^{π_{T}} = i^{π^{k}}.

We now state some basic facts about projections. Observations 7.8 and 7.10 will be used in the proof of Lemma 8.1.

Observation 7.7. Let π be any partial permutation on V, and let T ⊆ V. Projection onto T defines a one-to-one correspondence between those cycles of π which have non-empty intersection with T, and the cycles of π_{T}. It also defines a one-to-one correspondence between those paths of π which intersect T in at least 2 points, with the paths of π_{T}.

Observation 7.8. Let v ∈ V, ℓ ≥ 1, T ⊆ V, and let π be uniformly random in Sym(V). Let E = traj(v, π, ℓ).

(A) Suppose v ∉ T. Then, for every s ≥ 0, (A1) Conditioned on the event that E is a cycle

containing exactly s points of T, the distribution of E_{T} is uniformly random over cycles of length s on T.

(A2) Conditioned on E a path containing exactly s points of T, the E_{T} is uniformly random over paths of length s − 1 on T.

(B) Suppose v ∈ T. Then, for every s ≥ 0,

(B1) Conditioned on the event that E is a cycle containing exactly s points of T, the distribution of E_{T} is uniformly random over cycles of length s on T, containing v.

(B2) Conditioned on E a path containing exactly s points of T, the E_{T} is uniformly random over paths of length s − 1 on T, starting from v.

Observation 7.9. Let τ ∈ Sym(V). Then projection onto supp(τ) commutes with shear_{τ}, considered as operators on the set of all partial permutations of V.

Observation 7.10. Let τ ∈ Sym(V) and T = supp(τ). Let C be a cycle containing at least one vertex of T. Then shear_{τ} (C) has the same number of connected components as shear_{τ} (C_{T}). Let P be a path containing at least one vertex of T. Then shear_{τ} (P) has either 0, 1 or 2 more components than shear_{τ} (P_{T}). Hence for any trajectory E (hitting T or not) shear_{τ} (E) has 0, 1, or 2 more components than than shear_{τ} (E_{T}).

Finally, we introduce a notion of “contraction” by a partial permutation.

Definition 7.11. (Contraction of a set by a partial permutation) Let ρ be a partial permutation on vertex set R. Note that each component of ρ is either a path (this includes isolated points) or a cycle (this includes cycles of length one). We define the contracted set R/ρ to be the set of those components of ρ which are paths (including isolated points). (Note that we throw out all cycles and contract all paths.) If v ∈ V is contained in a path of ρ, and hence has a corresponding point in V/ρ, we say v survives contraction by ρ; if not, we say v is killed under contraction by ρ.

Definition 7.12. (Contraction of a permutation by a partial permutation) Let ρ be a partial permutation on R, and π ∈ Sym(R). Assume ρ ⊆ π. We define the contraction π^{∗} = π/ρ ∈ Sym(R/ρ), as follows. For p ∈ R/ρ, let p be a path from tail(p) to head(p). For p, q ∈ R/ρ, we set p^{π^{∗}} = q if head(p)^{π} = tail(q).

Observation 7.13. Fix a partial permutation ρ of R. Sample π ∈ Sym(R) uniformly at random, conditioned on ρ ⊆ π. Then π/ρ is distributed uniformly over Sym(R/ρ).

Observation 7.13 will be used in the proofs of Lemma 9.1 and Theorem 1.3.

8 Shears usually have many components Suppose τ ∈ Sym(V) has degree αn. For a random path of length t, we would intuitively expect the operation of shearing by τ to cut the path into about αt pieces. We now present a formal justification for this intuition, as long as t is not too large. Indeed, if αt = Ω(log n) and t = o(n), then it is almost certain that all trajectories of length t are cut into Θ(αt) pieces (not including trajectories in cycles of length less than t, of course).

Lemma 8.1. Let v ∈ V, t ≥ 1, and τ ∈ Sym(V). Let α := deg(τ)/n. Sample π ∈ Sym(V) uniformly at random, and let p denote the number of components of shear_{τ} (traj(v, π, t)). Then

Pr(p ≤ \frac{αt}{4} | | traj(v, π, t)|=t)≤ 2e^{−αt/8} + (\frac{54et}{n})^{αt/12}.

We will first prove that, when τ is fixed-point-free, small random sets are very far from being fixed by τ. The proof of Lemma 8.1 is at the end of the section.

Lemma 8.2. Let v ∈ V, t ≥ 1, and let τ ∈ Sym(V) be fixed-point-free. Sample Π uniformly at random from among subsets of V of size t + 1 containing v. Then, for all s ≥ 1,

Pr (|Π ∩ Π^{τ} | ≥ s) ≤ (\frac{6et^{2}}{sn} )^{s/2} .

Proof. The theorem holds vacuously if t > n/4, so we assume t ≤ n/4.

Generate Π = {v_{1}, …, v_{t+1}} by setting v_{1} = v, and sequentially sampling v_{2}, …, v_{t+1} from V \{v}, without replacement. For 0 ≤ i ≤ t+1, let Π_{i} = {v_{j} | j ≤ i}, and let Z_{i} = |Π_{i} ∩Π_{i}^{τ} |. For 1 ≤ i ≤ t+1, set Y_{i} = Z_{i} −Z_{i−1}. Note that Y_{i} is a random variable taking values in {0, 1, 2}. We investigate Z_{t+1} = ∑_{i=1}^{t+1} Y_{i} = |Π ∩ Π^{τ} |.

Suppose we are given Π_{i}. Conditioned on this information, v_{i+1} is uniformly distributed over V \ Π_{i}, a set of size n − i. Hence

Pr (Y_{i+1} ≠ 0) ≤ \frac{|Π_{i}^{τ} ∪ Π_{i}^{τ^{−1}}|}{n − i} ≤ \frac{2i}{n − i}.

Now we apply Corollary 5.2 to the random variables Y_{i} with μ_{i} = \frac{2(i−1)}{n−(i−1)}, b = 2 and

μ = ∑_{i=1}^{t+1} μ_{i} ≤ \frac{2}{n − t} ∑_{i=0}^{t} i = \frac{t(t + 1)}{n − t} ≤ \frac{3t^{2}}{n} ,

obtaining, for every s > 0,

Pr (Z_{t+1} ≥ s) ≤ (\frac{6et^{2}}{sn} )^{s/2} . □

We are now ready to prove the main result of this section.

Proof of Lemma 8.1. Let T = supp(τ), let E = traj(v, π, t), and let S denote the set of vertices of T hit by E.

By Observation 7.10, the number of components of shear_{τ} (E) is at least that of shear_{τ} (E_{T}). Since all the tails of shear_{τ} (E_{T}) are in S and all the heads of shear_{τ} (E_{T}) are in S^{τ}, it follows that the number of components of shear_{τ} (E_{T}) is at least |S| − 2 |S ∩ S^{τ} |. Hence, if p denotes the number of components of shear_{τ} (E), then

Pr(p ≤ \frac{αt}{6} | |E| = t) ≤ Pr(|S| ∉ [\frac{αt}{2}, 3αt] | |E| = t)

+Pr(|S ∩ S^{τ} | > \frac{|S|}{3} | |S| ∈ [\frac{αt}{2}, 3αt] , |E| = t).

By Lemma 5.3,

Pr(|S| ∉ [ \frac{αt}{2}, 3αt] | |E| = t) ≤ 2e^{−αt/8}.

By Observation 7.8, if we condition on the value of |S|, and on the vertex w ∈ S that occurs first along trajectory E starting from v, then S is a uniformly random subset of T of size |S| containing w. Now, since τ acts on T without fixed points, we can apply Lemma 8.2 to S, obtaining

Pr(|S ∩ S^{τ} | ≥ \frac{|S|}{3} | |S| ∈ [\frac{αt}{2}, 3αt])

≤ max_{s} (\frac{18es}{αn})^{s/6} ≤ (\frac{54et}{n})^{αt/12},

where the maximum is over s ∈ [\frac{αt}{2}, 3αt]. □

9 Shears rarely have large components Our main result in this section is in some sense dual to the main result of the previous section. As before, suppose τ ∈ Sym(V) has support of size αn. For any v ∈ V, we would expect the trajectory of v under a random permutation π, unless a very short cycle, to go at most O(1/α) steps before hitting the support of τ. This suggests the main result of this section (Lemma 9.2) which says that, even if ℓ is quite large, the operation of shearing by τ splits trajectories of length ℓ into only small components (as long as n − ℓ is sufficiently bigger than n/α). The full strength of this result will be needed in the proof of Theorem 1.3 (Section 10).

To prove this result, we approach it from another perspective, which strengthens the connection to the previous section. If shearing by τ^{−1} cuts even fairly short cycles of π = στ into enough pieces, then they are unlikely to all fall into a single ℓ-step trajectory of σ.

Lemma 9.1. Let τ ∈ Sym(V), t, ℓ > 0 and v, w ∈ V. Sample σ ∈ Sym(V) uniformly at random, and let π = στ. Let C = traj(v, π, t). Let p denote the number of components of shear_{τ^{−1}}(C). Then

Pr (shear_{τ^{−1}}(C) ⊆ traj(w, σ, ℓ) | C) ≤ (\frac{ℓ}{n − t − 1})^{p−1}.

Proof. Let ρ = shear_{τ^{−1}}(C).

If ρ is a single cycle, then p = 1 and the result is trivial. If ρ properly contains a cycle, then since traj(w, σ, ℓ) is a subset of a single cycle, the probability is zero.

Finally, if ρ contains no cycle, then it consists of p paths of length ≥ 1, with total length t. Let V (ρ) denote the set of points hit by ρ, so that V (ρ)/ρ is a set of p points in V/ρ. Now, if ρ ⊆ traj(w, σ, ℓ), then

(9.8)  V (ρ)/ρ ⊆ V (traj(w/ρ, σ/ρ, ℓ)).

But by Observation 7.13, the conditional distribution of σ/ρ, given ρ, is uniform over Sym(V/ρ). Even if we assume pessimistically that w/ρ ∈ V (ρ)/ρ, and that | traj(w/ρ, σ/ρ, ℓ)| = ℓ, the probability of the event in

(9.8) is at most \begin{matrix}( & {ℓ \atop p−1} & ) \\ ( & {n−t−1 \atop p−1} & ) \end{matrix} ≤ (\frac{ℓ}{n − t − 1})^{p−1} . □

Our next Lemma says that, as long as supp(τ) is not too small, revealing a (not too long) trajectory of σ probably reveals only very short paths in π = στ.

Lemma 9.2. Let τ ∈ Sym(V) and set α = deg(τ)/n. Let ℓ ∈ {1, …, n}, and let w ∈ V. Sample σ ∈ Sym(V) uniformly at random, and let π = στ. Let X be the number of edges in the largest component of shear_{τ} (traj(w, σ, ℓ)). Then, for all t ≥ 0,

Pr(X ≥ t) ≤ n((\frac{ℓ}{n − t − 1})^{αt/4−1} + 2e^{−αt/8}+(\frac{54et}{n})^{αt/12}).

Proof. For every v ∈ V, define events A_{v} = {traj(v, π, t) ⊆ shear_{τ} (traj(w, σ, ℓ))} and B_{v} = {| traj(v, π, t)| = t}. Note that X ≥ t if and only if there exists v such that both A_{v} and B_{v} occur.

Hence, by the union bound,

Pr (X ≥ t) ≤ ∑_{v} Pr (A_{v} ∧ B_{v}),

and so it suffices to prove, for every v ∈ V, that

Pr(A_{v} ∧ B_{v}) ≤ (\frac{ℓ}{n − t − 1})^{αt/4−1} + 2e^{−αt/8} + (\frac{12et}{n})^{αt/32}.

Let v ∈ V, let p_{v} denote the number of connected components of shear_{τ^{−1}}(traj(v, π, t)), and define the event C_{v} = {p_{v} ≤ αt/4}. Then

A_{v} ∧ B_{v} ⊆ (A_{v} ∧ ¬C_{v}) ∪ (B_{v} ∧ C_{v}),

and hence

Pr (A_{v} ∧ B_{v}) ≤ Pr (A_{v} | ¬C_{v}) + Pr (C_{v} | B_{v}).

Now Lemma 8.1 says exactly that Pr (C_{v} | B_{v}) ≤ 2e^{−αt/8} + (\frac{54et}{n})^{αt/12}, while Lemma 9.1 implies that

Pr(A_{v} | ¬C_{v}) ≤ E ((\frac{ℓ}{n − t − 1})^{p_{v}−1}| p_{v} > αt/4)

≤ (\frac{ℓ}{n − t − 1})^{αt/4−1} ,

which completes the proof. □

10 Proof of Theorem 1.3 Observation 10.1. Let v ∈ V, τ ∈ Sym(V), ℓ ≥ 1, and let α = deg(τ)/n. Choose σ ∈ Sym(V) uniformly at random. Let ρ = shear_{τ} (traj(v, σ, ℓ)). Then, for every t ∈ {1, …, n}, the probability that the point v survives contraction by ρ is at least

1 − \frac{t}{n} − n((\frac{ℓ}{n − t − 1})^{αt/4−1} + 2e^{−αt/8}+(\frac{54et}{n})^{αt/12}).

Proof. If v is killed under contraction by ρ, then either v is in a cycle of π = στ of length < t, which has probability (t − 1)/n, or ρ has a component of size ≥ t, which has probability bounded in Lemma 9.2. □

Proof of Theorem 1.3. The conclusion of the theorem is equivalent to this: for every 1 ≤ k, ℓ ≤ n, (10.9)

|Pr (X ≤ k and Y > ℓ) − \frac{k(n − ℓ)}{n^{2}} | ≤ n^{−1/8+o(1)}.

Since Pr (Y > n − n^{7/8−o(1)}) ≤ n^{−1/8+o(1)}, it suffices to prove (10.9) in the case ℓ < n − n^{7/8−o(1)}. We will prove the stronger claim that, for 1 ≤ k ≤ n, 1 ≤ ℓ ≤ n − n^{7/8} log^{2} n,

|Pr (X ≤ k | Y > ℓ) − \frac{k}{n}| ≤ n^{−1/8+o(1)}.

Henceforth, let ℓ ≤ n − n^{7/8} log^{2} n be fixed.

Let v be the first vertex in V, so Y = |c(σ, v)| and X = |c(π, v)|. Consider the partial permutation ρ := shear_{τ} (traj(v, σ, ℓ)) ⊆ π. Since π = στ is uniformly distributed a priori, it follows that the conditional distribution of π, given traj(v, σ, ℓ), is uniform over the set of permutations containing ρ. We will analyze the conditional distribution of X, given ρ, by studying the contraction of π by ρ.

Let C denote the cycle of π containing v. We say ρ is bad if at least one of the following holds:

(a) v is in a cycle of ρ, i. e., C ⊆ ρ,

(b) ρ has a component of size ≥ n^{3/8}, or

(c) ≥ \sqrt{n} edges of ρ are contained in cycles.

By Observation 10.1, Lemma 9.2, and Proposition 4.8, the probability that ρ is bad is ≤ n^{−1/8+o(1)}, even conditioned on the event Y ≥ ℓ.

From now on, fix ρ, and assume ρ is good. When we talk about probabilities below, we will always mean conditional probabilities, conditioned on this value of ρ.

Label each point w ∈ V/ρ by the number p_{w} of points in the maximal path of ρ which contracts to it. Now, by Observation 7.13, since π is uniformly distributed over extensions of ρ, π/ρ is uniformly distributed over Sym(V/ρ). Since ρ is good, the contraction C/ρ is non-empty. This implies the length of C/ρ is uniformly distributed over 1, …, n − ℓ, and that the set of vertices hit by C/ρ consists of v/ρ, together with a random (|C/ρ|−1)-subset S of the remaining n−ℓ−1 vertices. If Z denotes the sum of the labels on S, then X = Z + p_{v}.

Condition further on the values of all the labels, so that the only randomness remaining is the set S. Since ρ is good, these n−ℓ labels are all in {1, …, n^{3/8}} and sum to n − c = n − O(\sqrt{n}), where c is the number of edges in cycles of ρ. Normalizing these labels to [0, 1], and applying Theorem 5.6, we find, for every z ∈ [0, n − c],

|Pr (Z ≤ z) − \frac{z}{n − c}| ≤ \frac{4\sqrt{n log n}}{n^{5/8}} ≤ n^{−1/8+o(1)}.

Since Pr (X ≤ x) = Pr (Z ≤ x − p_{v}) and since (x − p_{v})/(n − c) = x/n + O(n^{−1/2}) the result follows by the triangle inequality. □

11 Proof of Theorem 1.2 Proof. Given a pair of independent random permutations τ, σ ∈ S_{n}, we need to show that the lengths of the first cycles of στ^{i} and στ^{j} are nearly independent for 1 ≤ i < j < s where s = n^{(7/32−ε) ln n}.

Let σ_{1} = στ^{i}. Note that σ_{1} is uniformly distributed over S_{n}. Let k = j − i. Then στ^{j} = σ_{1}τ^{k}. According to Theorem 1.3, we are done if we can show that a.a., for all k ≤ s, deg(τ^{k}) ≥ n^{3/4}. But this is exactly the assertion of Theorem 4.4 for p = 3/4.

We also need to show that the lengths of the first cycles of τ and στ^{i} are nearly independent. In fact, these two permutations are independent. □

12 Open Problems Theorem 1.3 introduces a new type of problem in the statistical theory of permutations: the nearindependence of parameters of the permutations σ and τσ where τ is given and satisfies a lower bound on its degree (such as deg(τ) = Ω(n)) and σ is selected uniformly at random.

Theorem 1.3 shows that under these conditions, the lengths of the first cycle of σ and of τσ are nearly independent. Does the same hold for the second, third, etc. cycles; for the number of cycles; for the logarithm of the order? We remark that the number of cycles of a random permutation, as well as the logarithm of its order, are asymptotically normally distributed ([15, 12]).

We believe that all these parameters will be nearly independent for σ and τσ. In fact we expect that for any constant k, if τ_{1}, …, τ_{k} are given permutations such that the degree of each quotient τ_{i}^{−1}τ_{j} (i ≠ j) is Ω(n) and σ is random then the lengths of the first cycle of τ_{i}σ (i = 1, …, k) are nearly independent; and the same holds for the other parameters mentioned.

References

[1] N. Alon, J. Spencer: The Probabilistic Method. Wiley-Interscience, 1992.

[2] L. Babai: The probability of generating the symmetric group. J. Comb. Th.–A 52 (1989), 148–153.

[3] L. Babai, R. Beals, Á. Seress: On the diameter of the symmetric group: polynomial bounds. 15th ACM-SIAM SODA (2004), 1101–1105.

[4] L. Babai, G. L. Hetyei: On the diameter of random Cayley graphs of the symmetric group. Combinatorics, Probability, and Computing 1 (1992), 201–208.

[5] L. Babai, G. Hetyei, W.M. Kantor, A. Lubotsky, Á. Seress: On the diameter of finite groups. 31st IEEE FOCS, 1990, pp. 857–865.

[6] L. Babai, Á. Seress: On the Degree of Transitivity of Permutation Groups: A Short Proof. J. Combinatorial Theory–A 45 (1987), 310–314.

[7] L. Babai, Á. Seress: On the diameter of Cayley graphs of the symmetric group. J. Combinatorial Theory–A 49 (1988), 175–179.

[8] J. D. Bovey: The probability that some power of a permutation has small degree. Bull. London Math. Soc. 12 (1980), 47–51.

[9] J. D. Dixon: The probability of generating the symmetric group. Math. Z. 110 (1969), 199–205.

[10] J. R. Driscoll, M. L. Furst: Computing short generator sequences. Info. & Comp. 72 (1987), 117–132.

[11] P. Erdős, P. Turán: On some problems of a statistical group theory I., Z. Wahrscheinlichkeitstheorie verw. Geb. 4 (1965), 175–186.

[12] P. Erdős and P. Turán: On some problems of a statistical group theory III, Acta Math. Acad. Sci. Hung. 18 (1967), 309–320.

[13] P. Erdős and P. Turán: On some problems of a statistical group theory VII, Period. Math. Hung. 2 (1972), 149–163.

[14] S. Even, O. Goldreich: The minimum length generator sequence is NP -hard. J. Algor. 2 (1981), 311–313.

[15] V. L. Goncharov: On the Field of Combinatory Analysis, Isvestija Akad. Nauk. SSSR, Ser. mat. 8 (1944), 3-48 (Russian. English translation: Translations of the AMS, Ser. 2, 19 (1962), 1-46.)

[16] M-C. Heydemann: Cayley graphs and interconnection networks. In: Graph Symmetry (Montreal, 1996), NATO Adv. Sci. Inst. Ser. C, Math. Phys. Sci. 497, Kluwer Acad. Publ., Dordrecht 1997, pp. 167–224.

[17] W. Hoeffding: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58 (1963), 13–30.

[18] M. R. Jerrum: The complexity of finding minimum length generator sequences. Theoretical Computer Science 36 (1985), 265–289.

[19] R. E. Korf: Finding optimal solutions to Rubik’s Cube using pattern databases. In: Proc. 14th Nat. Conf. on Artificial Intelligence (AAAI-97), Amer. Assoc. for Artificial Intelligence, 1997, pp. 700-705.

[20] L. Lovász: Combinatorial Problems and Exercises. Akadémiai Kiadó, Budapest, and North-Holland, Amsterdam, 1979.

[21] P. McKenzie: Permutations of bounded degree generate groups of polynomial diameter. Info. Proc. Lett. 19 (1984), 253–254.

[22] R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, Cambridge, 1995.

[23] Á. Seress: Permutation Group Algorithms. Cambridge Univ. Press, 2003.