18.317 Combinatorics, Probability, and Computations on Groups 17 October 2001

Lecture 14

Lecturer: Igor Pak Scribe: C. Goddard

Hall Bases Continued

Last lecture we finished with the theorem:

Theorem 1. Given a ω - complete word in \overline{B} = (B_{1}, B_{2}, …), a Hall Basis in G, then ω\overline{α} - uniform in G.

Now two lectures ago, we wanted to prove the following lemma:

Lemma 2. κ for U(n, p) = \{(\begin{matrix}1 & ∗ & ⋯ & ∗ \\ 0 & 1 & ⋯ & ∗ \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 1 \end{matrix}) ∗ ∈ 𝔽_{p}\} is strong uniform.

We proved a corollary to this:

Corollary 3. The mixing time for a random walk on U(n, p) = O(n^{2} log n).

Now we want to prove Theorem 1 ⇒ Lemma 2.

Proof: Let G = U(n, p), that is the group of n × n upper triangular matrices with 1’s on the diagonal. Consider the basis: \overline{B} = (B_{1}, B_{2}, …, B_{n−1}) where

B_{i} = \{(\begin{matrix}1 & 0 & ⋯ & 0 \\ 0 & 1 & 1 & ⋮ \\ ⋮ & & ... & 0 \\ 0 & ⋯ & 0 & 1 \end{matrix}) with a 1 in the ith diagonal.\}

Thus |B_{i}| = n − i.

Now we have to check \overline{B} is a Hall basis for U(n, p). This is “obvious” since we know that <γ_{i}(B_{i})> = H_{i} since, firstly <B_{i}> = G_{i}, where G_{i} consists of 0’s everywhere below the ith diagonal except the main diagonal, and H_{i} is the quotient G_{i−1}/G_{i}, so H_{i} ≅ (ℤ_{p})^{n−i}.

For the mixing time, we know X_{t} = E_{i_{1}j_{1}}(α_{1}) · E_{i_{2}j_{2}}(α_{2}) · . . . · E_{i_{t}j_{t}}(α_{t}) by definition since

E_{ij}(α) = (\begin{matrix}1 & 0 & ⋯ & 0 \\ 0 & 1 & α & 0 \\ ⋮ & ... & 0 & ⋮ \\ 0 & ⋯ & 0 & 1 \end{matrix}) ie 1’s on the diagonal and 0’s elsewhere except α in the ijth position

Now we want to look at κ, which is the first time all the indices i, j occur in this product. So in the notation of the previous lecture, Λ = {(i, j), 1 ≤ i < j ≤ n}. Say that there are N words that contain all i, j and look at the complete words. Thus,

Pr(X_{t} = h|κ = t) = \frac{1}{N} · ∑_{ω} Pr(ω\overline{α} = h)

where we sum over the complete words ω of length t such that no shorter word is a complete word. Therefore from Theorem 1, ω is uniform. So,

Pr(X_{t} = h|κ = t) = \frac{1}{N} · N · \frac{1}{|G|} = \frac{1}{|G|}

Thus, κ is strong uniform. Note, we can generalise this to any nilpotent group with generators corresponding to our generators, and the mixing time = O(|Λ| log |Λ|).

Brief Outline of Open Problems for Research Projects

Hamilton Paths in Cayley Graphs

There are two conflicting conjectures relating to the Hamilton paths in Cayley graphs, namely: Conjecture 4. (Lovasz) ∀G, <S> = G, S = S^{−1}, the Cayley graph Γ(G, S) contains a Hamilton path. Conjecture 5. (Babai) ∃α > 0 such that ∃ infinitely many Cayley graphs with no paths on length > (1 − α) · #vertices.

Aim: try and find out which one of these is true on a special groups and generating sets. Examples: 1) Try Hall’s 19 (up to automorphisms) Cayley graphs of A_{5} with 2 generators (aim for negative answer.)

2) Try S_{n} and conjugacy classes (aim for positive answer.)

3) Try general nilpotent groups (positive.)

4) Try three involutions in general groups (positive.) NB: every finite simple group can be generated by three involutions.

5) Try wreath and semidirect product of finite groups (positive; easy for direct products.)

Diameter Problem

Suppose we have A_{n}, S_{n} and <S> = A_{n}, where S is a set of generators. Conjecture 6. diameter(A_{n}, S) < cn^{2}, c - constant. Also works for S_{n}.

Look at the following weaker versions of this:

1. For the worst case when |S| = 2, we have the following: Theorem 7. (Babai, Hetyei) diam < e^{\sqrt{n} log n(1+o(1))}. This gives a bound of the maximum order of permuations in S_{n}.

Aim: Find something similar for SL(n, p). Conjecture 8. G - simple ⇒ diam = O((log |G|)^{c}). So diam ≤ (n^{2} log p)^{2} which would be hard to prove, but e^{n} may be manageable.

2. Average Case. Theorem 9. (Dixon) <σ_{1}, σ_{2}> = A_{n} with Pr → 1 as n → ∞. Theorem 10. (Babai-Seress) diam(Γ(A_{n}, {σ_{1}, σ_{2}})) = n^{O(log n)} w.h.p. Aim: get something close for PSL(n, p).

3. Problem.

Conjecture 11. (Kantor) diam(Γ(A_{n}, {σ_{1}, σ_{2}})) = O(n log n) w.h.p. Some people believe this is not true. Question: True or False? Weaker version: Prove that Γ(A_{n}, {σ_{1}, σ_{2}}) are NOT exanders w.h.p.

Random Graphs vs Random Cayley Graphs

1.

Theorem 12. (Ramsey Theory) In random undirected graph Γ with n vertices, there exists a m = c · log n complete subgraph in Γ and a m = c · log n complete subgraph in \overline{Γ} w.h.p. Now suppose Γ is a random Cayley graph over a fixed group G. People believe the same is true. Aim: prove it (N. Alon proved the result with m = c\sqrt{log n}.)

2.

Theorem 13. Γ - random graph on n vertices ⇒ Aut(Γ) = 1 with high probability. NB: Erdős and Rényi proved that one has to remove θ(n^{2}) edges before a nontrivial automorphism appears. Question: if Γ - random Cayley graph, is Aut(Γ) = G with high probability? L. Goldberg and M. Jerrum conjecture this for G = ℤ_{n}.

Percolation on finite Cayley graphs

Fix a Cayley graph Γ and probability p. Delete edges with Pr = (1 − p) independently and look at the connected components. Say Γ ⊃ large cluster if ∃ connected component > \frac{1}{2}|Γ|. Conjecture 14. (Benjamini) If diam(Γ) < c · \frac{|G|}{log^{2} |G|}, then Cayley graph Γ contains large cluster with Pr > \frac{1}{2} for p < 1 − ε where ε is independent of the size of the graph.

Itai Benjamini confirms the conjecture for abelian groups. Question: Is this true for G nilpotent? What about S_{n}?