18.317 Combinatorics, Probability, and Computations on Groups 21 November 2001

Lecture 28

Lecturer: Igor Pak Scribe: Fumei Lam

Product Replacement Graphs

Definition 1 Let G be a finite group and let k ≥ d(G), where d(G) is the minimum number of generators of G. The product replacement graph Γ_{k}(G) is a graph on k-tuples (g_{1}, g_{2}, … g_{k}) ∈ G^{k} satisfying < g_{1}, g_{2}, … g_{k} >= G. The edges of Γ_{k}(G) are

\{\overline{g}, R_{ij}^{±}(\overline{g}) \},
\{\overline{g}, L_{ij}^{±}(\overline{g}) \},

where

R_{ij}^{±}(g_{1}, … g_{i}, … g_{j}, … g_{k}) = (g_{1}, … g_{i}g_{j}^{±1}, … g_{j}, … g_{k})},
L_{ij}^{±}(g_{1}, … g_{i}, … g_{j}, … g_{k}) = (g_{1}, … g_{j}^{±1}g_{i}, … g_{j}, … g_{k})}.

There are k(k − 1) choices for pairs (i, j), and two choices each for R or L and + or −. By allowing vertices in Γ_{k}(G) to contain loops, this implies Γ_{k}(G) is a D− regular graph with D = 4k(k − 1).

Example. For G = Z_{p}^{m}, d(G) = m, the vertices of Γ_{m}(Z_{p}^{m}) are matrices

A = [ \begin{matrix}a_{11} & a_{12} & ⋯ & a_{1m} \\ a_{21} & a_{22} & ⋯ & a_{2m} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ a_{m1} & a_{m2} & ⋯ & a_{mm} \end{matrix} ]

with det(A) ≠ 0, a_{ij} ∈ F_{p}.

The operations R_{ij}^{±} and L_{ij}^{±} correspond to left multiplication by

E^{±} = \begin{cases}1 on the diagonal \\ ±1 in entry ij \\ 0 otherwise. \end{cases}

Note that since the group is abelian, the operations L and R are the same. So Γ_{m}(Z_{p}^{m}) is the Cayley graph Γ(GL(m, p), {E_{ij}(±1)}). Since E^{±} has determinant ±1, Γ_{m}(Z_{p}^{m}) has p − 1 connected components, each corresponding to different values for the determinant.

Conjecture 2 If k ≥ d(G) + 1, then Γ_{k}(G) is connected.

The following weaker conjecture is also unknown. Conjecture 3 If k ≥ 3, then Γ_{k}(S_{n}) is connected. Lemma 4 (Higman) Let k = 2. Then the conjugacy class of [g_{1}, g_{2}] (< g_{1}, g_{2} >= G) is invariant on connected components of Γ_{2}(G). Proof: For (g_{1}, g_{2}) ∈ V (Γ_{2}(G)), {L^{±}(g_{1}, g_{2}), R^{±}(g_{1}, g_{2})} = {(g_{1}g_{2}, g_{2}), (g_{1}g_{2}^{−1}, g_{2}), (g_{2}g_{1}, g_{2}), (g_{2}^{−1}g_{1}, g_{2})}. Then

[g_{1}g_{2}, g_{2}] = g_{1}g_{2}g_{2}g_{2}^{−1}g_{1}^{−1}g_{2}^{−1} = [g_{1}, g_{2}],
[g_{2}g_{1}, g_{2}] = g_{2}g_{1}g_{2}g_{1}^{−1}g_{2}^{−1}g_{2}^{−1} = g_{2}[g_{1}, g_{2}]g_{2}^{−1} = [g_{1}, g_{2}]^{g_{2}^{−1}},
[g_{1}g_{2}^{−1}, g_{2}] = g_{1}g_{2}^{−1}g_{2}g_{2}g_{1}^{−1}g_{2}^{−1} = [g_{1}, g_{2}],
[g_{2}^{−1}g_{1}, g_{2}] = g_{2}^{−1}g_{1}g_{2}g_{1}^{−1}g_{2}g_{2}^{−1} = g_{2}^{−1}[g_{1}, g_{2}]g_{2} = [g_{1}, g_{2}]^{g_{2}}.

Example. Let G = A_{n} for n odd, k = 2 and consider a = (123 … n), b = (123 … p) with p |̸n. Then the commutators lie in different conjugacy classes, implying the number of connected components of Γ_{2}(A_{n}) → ∞ as n → ∞. Theorem 5 Let m(G) denote the maximum size of a nonredundant generating set. For k ≥ d(G) + m(G), Γ_{k}(G) is connected. In order to prove the theorem, we first define graph Γ̃_{k}(G) as the graph Γ_{k}(G) with additional edges defined by the operators

I_{m}(g_{1}, g_{2}, … g_{m}, … g_{k}) = (g_{1}, g_{2}, … g_{m}^{−1}, … g_{k})
π_{ij}(g_{1}, g_{2}, … g_{i}, … g_{j}, … g_{k}) = (g_{1}, g_{2}, … g_{j}, … g_{i}, … g_{k}).

Then we have the following lemma. Lemma 6 The number of connected components of Γ_{k}(G) is less than or equal to the number of connected components of Γ̃_{k}(G). Proof: Define the operation T_{ij}(g_{1}, g_{2}, … g_{i}, … g_{j}, … g_{k}) = (g_{1}, g_{2}, … g_{j}^{−1}, … g_{i}, … g_{k}), i.e., T_{ij} switches entries g_{i} and g_{j} and inverts g_{j}. Note that T_{ij} = L_{ij}^{−}L_{ji}^{+}R_{ij}^{−} and

T_{ij}^{2}(g_{1}, g_{2}, … g_{i}, … g_{j}, … g_{k}) = (g_{1}, g_{2}, … g_{i}^{−1} … g_{j}^{−1} … g_{k}).

Now note that since Γ_{k}(G) is a subgraph of Γ̃_{k}(G), this implies every connected component of Γ̃_{k}(G) splits into at most 2 components in Γ_{k}(G).

As a corollary, if Γ̃_{k}(G) is connected for k ≥ d(G) + 1, then Γ_{k}(G) is connected.

Since m(G) ≥ 1 for all groups, we need only consider Γ̃_{k}(G) to prove the theorem.

Theorem 7 For k ≥ d(G) + m(G), Γ̃_{k}(G) is connected.

Proof:

By definition of m = m(G), any element (g_{1}, g_{2}, … g_{k}) ∈ Γ_{k}(G) contains a generating subset of m elements g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}. Use the operators π_{ij} to obtain

(g_{1}, g_{2}, … g_{k}) → (g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}, …)

where the remaining k − m elements are those not in {g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}}. Now since g_{i_{1}}, g_{i_{2}}, … g_{i_{m}} form a generating set, we can use the L^{±} and R^{±} operations to obtain

(g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}, …) → (g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}, 1, 1, … 1)
→ (g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}, h_{1}, h_{2}, … h_{k−m}),

where h_{1}, h_{2}, … h_{k−m} is a generating set of G (this is possible, since k − m ≥ d). Then we again use the L^{±}, R^{±} operators to obtain

(g_{i_{1}}, g_{i_{2}}, … g_{i_{m}}, h_{1}, h_{2}, … h_{k−m}) → (1, 1, … 1, h_{1}, h_{2}, … h_{k−m}).

Therefore, every element in Γ̃_{k}(G) is connected to the element (1, 1, … 1, h_{1}, h_{2}, … h_{k−m}), implying Γ̃_{k}(G) is connected.

Now Theorem 5 follows immediately from Lemma 6 and Theorem 7. We also have the following corollary.

Corollary 8 For k ≥ 2⌊log_{2} |G|⌋, Γ_{k}(G) is connected.

The following theorem shows that Γ_{3}(A_{n}) contains very large connected components.

Theorem 9 There exists Γ′ ⊂ Γ_{k}(A_{n}) such that Γ′ is connected for all k ≥ 3 and

\frac{|Γ′|}{|Γ_{k}(A_{n})|} → 1 as n → ∞.

Proof: For k = 3, pick g_{1}, g_{2}, g_{3}, h_{1}, h_{2}, h_{3} ∈ A_{n} uniformly and independently. We will show that with high probability, the elements (g_{1}, g_{2}, g_{3}), (h_{1}, h_{2}, h_{3}) ∈ Γ_{3}(A_{n}) are connected. Since < g_{1}, g_{2} >= A_{n} with high probability, we can use L^{±}, R^{±} operations to obtain

(g_{1}, g_{2}, g_{3}) → (g_{1}, g_{2}, h_{3}).

Similarly, since h_{2} and h_{3} were chosen uniformly, < g_{1}, h_{3} >=< h_{2}, h_{3} >= A_{n} with high probability, so we have

(g_{1}, g_{2}, h_{3}) → (g_{1}, h_{2}, h_{3}) → (h_{1}, h_{2}, h_{3}).

Since the probability two random elements generate A_{n} is at least 1− \frac{1}{n}, the probability two random elements are connected is at least 1 − \frac{1}{3n} and the theorem follows.