\documentclass{article} \usepackage{amsmath,amssymb} \usepackage[dvips]{color} \setlength{\oddsidemargin}{0.25 in} \setlength{\evensidemargin}{-0.25 in} \setlength{\topmargin}{-0.6 in} \setlength{\textwidth}{6.5 in} \setlength{\textheight}{8.5 in} \setlength{\headsep}{0.75 in} \setlength{\parindent}{0 in} \setlength{\parskip}{0.1 in} \newcounter{lecnum} % % The following macro is used to generate the header. % \newcommand{\lecture}[4]{ \pagestyle{myheadings} \thispagestyle{plain} \newpage \setcounter{lecnum}{#1} \setcounter{page}{1} \noindent \begin{center} \framebox{ \vbox{\vspace{2mm} \hbox to 6.28in { {{\bf 18.317~Combinatorics, Probability, and Computations on Groups} \hfill #2} } \vspace{4mm} \hbox to 6.28in { {\Large \hfill Lecture #1 \hfill} } \vspace{2mm} \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} } \vspace{2mm}}} \end{center} \markboth{Lecture #1: #2}{Lecture #1: #2} \vspace*{4mm} } \input{epsf} %usage: \fig{LABEL}{FIGURE-HEIGHT}{CAPTION}{FILENAME} \newcommand{\fig}[4]{ \begin{figure} \setlength{\epsfysize}{#2} \centerline{\epsfbox{#4}} \caption{#3} \label{#1} \end{figure} } \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{claim}[theorem]{Claim} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{definition}[theorem]{Definition} \newtheorem{conjecture}[theorem]{Conjecture} \newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}} \newenvironment{mproof}[1]{{\bf #1}}{\hfill\rule{2mm}{2mm}} \def\E#1{{\rm E}[#1]} \def\i{\hspace*{5mm}} \newcounter{lineno} \setcounter{lineno}{0} \def\n{\addtocounter{lineno}{1} \hbox to 7mm{\hfill \arabic{lineno}:}\hspace{2mm}} \def\resetn{\setcounter{lineno}{0}} \def\tqbfk{\tqbf_k^\exists} \def\ep{\epsilon} \def\erd{Erd\H{o}s} \def\qed{\thinspace\nobreak \vrule width 7pt height 5.5pt depth 1.5pt} \begin{document} \lecture{28}{21 November 2001}{Igor Pak}{Fumei Lam} \section*{Product Replacement Graphs} \begin{definition} Let $G$ be a finite group and let $k \geq d(G)$, where $d(G)$ is the minimum number of generators of $G$. The product replacement graph $\Gamma_k (G)$ is a graph on $k$-tuples $(g_1, g_2, \ldots g_k) \in G^k$ satisfying $< g_1, g_2, \ldots g_k > = G$. The edges of $\Gamma_k(G)$ are $$\{ \overline{g}, \, R_{ij}^{\pm}(\overline{g} ) \, \},$$ $$\{ \overline{g}, \, L_{ij}^{\pm}(\overline{g} ) \, \},$$ \noindent where $$R_{ij}^{\pm}(g_1, \ldots g_i, \ldots g_j, \ldots g_k) = (g_1, \ldots g_ig_j^{\pm 1}, \ldots g_j, \ldots g_k) \},$$ $$L_{ij}^{\pm}(g_1, \ldots g_i, \ldots g_j, \ldots g_k) = (g_1, \ldots g_j^{\pm 1}g_i, \ldots g_j, \ldots g_k) \}.$$ \end{definition} There are $k(k-1)$ choices for pairs $(i,j)$, and two choices each for $R$ or $L$ and $+$ or $-$. By allowing vertices in $\Gamma_k(G)$ to contain loops, this implies $\Gamma_k(G)$ is a $D-$ regular graph with $D = 4k(k-1)$. {\bf Example.} For $G = Z_p^m, d(G) = m$, the vertices of $\Gamma_m(Z_p^m)$ are matrices $$A = \left[ \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1m} \\ a_{21} & a_{22} & \cdots & a_{2m} \\ \vdots & \vdots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mm} \\ \end{array} \right]$$ with $det(A) \not= 0, a_{ij} \in F_p$. The operations $R_{ij}^{\pm}$ and $L_{ij}^{\pm}$ correspond to left multiplication by $$E^{\pm} = \begin{cases} 1 \text{ on the diagonal } \\ \pm 1 \text{ in entry ij }\\ 0 \text{ otherwise}.\\ \end{cases} $$ Note that since the group is abelian, the operations $L$ and $R$ are the same. So $\Gamma_m(Z_p^m)$ is the Cayley graph $\Gamma(GL(m,p), \{ E_{ij}(\pm 1) \} )$. Since $E^{\pm}$ has determinant $\pm 1$, $\Gamma_m(Z_p^m)$ has $p-1$ connected components, each corresponding to different values for the determinant. \begin{conjecture} If $k \geq d(G) + 1$, then $\Gamma_k(G)$ is connected. \end{conjecture} The following weaker conjecture is also unknown. \begin{conjecture} If $k \geq 3$, then $\Gamma_k(S_n)$ is connected. \end{conjecture} \begin{lemma} (Higman) Let $k = 2$. Then the conjugacy class of $[g_1, g_2]$ ($< g_1, g_2 > = G$) is invariant on connected components of $\Gamma_2(G)$. \end{lemma} \begin{proof} For $(g_1, g_2) \in V(\Gamma_2(G))$, $\{ L^{\pm} (g_1, g_2), R^{\pm} (g_1, g_2) \} = \{ (g_1g_2, g_2), (g_1g_2^{-1}, g_2), (g_2g_1, g_2), (g_2^{-1}g_1, g_2) \}$. Then $$[g_1g_2, g_2] = g_1g_2g_2g_2^{-1}g_1^{-1}g_2^{-1} = [g_1,g_2],$$ $$[g_2g_1, g_2] = g_2g_1g_2g_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_1g_2^{-1}, g_2] = g_1g_2^{-1}g_2g_2g_1^{-1}g_2^{-1} = [g_1,g_2],$$ $$[g_2^{-1}g_1, g_2] = g_2^{-1}g_1g_2g_1^{-1}g_2g_2^{-1} = g_2^{-1}[g_1,g_2]g_2 =[g_1,g_2]^{g_2}.$$ \end{proof} {\bf Example.} Let $G = A_n$ for $n$ odd, $k = 2$ and consider $a = (1 2 3 \ldots n), b = (1 2 3 \ldots p)$ with $p \not| n$. Then the commutators lie in different conjugacy classes, implying the number of connected components of $\Gamma_2(A_n) \rightarrow \infty$ as $n \rightarrow \infty$. \begin{theorem} Let $m(G)$ denote the maximum size of a nonredundant generating set. For $k \geq d(G) + m(G)$, $\Gamma_k(G)$ is connected. \end{theorem} In order to prove the theorem, we first define graph $\widetilde{\Gamma}_k(G)$ as the graph $\Gamma_k(G)$ with additional edges defined by the operators $$I_m(g_1, g_2, \ldots g_m, \ldots g_k) = (g_1, g_2, \ldots g_m^{-1}, \ldots g_k)$$ $$\pi_{ij}(g_1, g_2, \ldots g_i, \ldots g_j, \ldots g_k) = (g_1, g_2, \ldots g_j, \ldots g_i, \ldots g_k).$$ Then we have the following lemma. \begin{lemma} The number of connected components of $\Gamma_k(G)$ is less than or equal to the number of connected components of $\widetilde{\Gamma}_k(G)$. \end{lemma} \begin{proof} Define the operation $T_{ij}(g_1, g_2, \ldots g_i, \ldots g_j, \ldots g_k) = (g_1, g_2, \ldots g_j^{-1}, \ldots g_i, \ldots 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, \ldots g_i, \ldots g_j, \ldots g_k) = (g_1, g_2, \ldots g_i^{-1} \ldots g_j^{-1} \ldots g_k).$$ Now note that since $\Gamma_k(G)$ is a subgraph of $\widetilde{\Gamma}_k(G)$, this implies every connected component of $\widetilde{\Gamma}_k(G)$ splits into at most 2 components in $\Gamma_k(G)$. \end{proof} As a corollary, if $\widetilde{\Gamma}_k(G)$ is connected for $k \geq d(G) + 1$, then $\Gamma_k(G)$ is connected. \newpage Since $m(G) \geq 1$ for all groups, we need only consider $\widetilde{\Gamma}_k(G)$ to prove the theorem. \begin{theorem} For $k \geq d(G) + m(G)$, $\widetilde{\Gamma}_k(G)$ is connected. \end{theorem} \begin{proof} By definition of $m = m(G)$, any element $(g_1, g_2, \ldots g_k) \in \Gamma_k(G)$ contains a generating subset of $m$ elements $g_{i_1}, g_{i_2}, \ldots g_{i_m}$. Use the operators $\pi_{ij}$ to obtain $$(g_1, g_2, \ldots g_k) \rightarrow (g_{i_1}, g_{i_2}, \ldots g_{i_m}, \ldots )$$ where the remaining $k - m$ elements are those not in $\{ g_{i_1}, g_{i_2}, \ldots g_{i_m} \} $. Now since $g_{i_1}, g_{i_2}, \ldots g_{i_m}$ form a generating set, we can use the $L^{\pm}$ and $R^{\pm}$ operations to obtain \begin{eqnarray*} (g_{i_1}, g_{i_2}, \ldots g_{i_m}, \ldots) & \rightarrow & (g_{i_1}, g_{i_2}, \ldots g_{i_m}, 1, 1, \ldots 1 ) \\ & \rightarrow & ( g_{i_1}, g_{i_2}, \ldots g_{i_m}, h_1, h_2, \ldots h_{k-m} ), \end{eqnarray*} where $h_1, h_2, \ldots h_{k-m}$ is a generating set of $G$ (this is possible, since $k-m \geq d$). Then we again use the $L^{\pm}, R^{\pm}$ operators to obtain $$ ( g_{i_1}, g_{i_2}, \ldots g_{i_m}, h_1, h_2, \ldots h_{k-m}) \rightarrow (1, 1, \ldots 1, h_1, h_2, \ldots h_{k-m}).$$ Therefore, every element in $\widetilde{\Gamma}_k(G)$ is connected to the element $(1, 1, \ldots 1, h_1, h_2, \ldots h_{k-m})$, implying $\widetilde{\Gamma}_k(G)$ is connected. \end{proof} Now Theorem 5 follows immediately from Lemma 6 and Theorem 7. We also have the following corollary. \begin{corollary} For $k \geq 2 \lfloor \log_2 \vert G \vert \rfloor, \Gamma_k(G)$ is connected. \end{corollary} The following theorem shows that $\Gamma_3(A_n)$ contains very large connected components. \begin{theorem} There exists $\Gamma' \subset \Gamma_k(A_n)$ such that $\Gamma'$ is connected for all $k \geq 3$ and $$\frac{\vert \Gamma' \vert}{\vert \Gamma_k(A_n) \vert} \rightarrow 1 \text{ as } n \rightarrow \infty.$$ \end{theorem} \begin{proof} For $k = 3$, pick $g_1, g_2, g_3, h_1, h_2, h_3 \in 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) \in \Gamma_3(A_n)$ are connected. Since $< g_1, g_2 > = A_n$ with high probability, we can use $L^{\pm}, R^{\pm}$ operations to obtain $$(g_1, g_2, g_3) \rightarrow (g_1, g_2, h_3).$$ Similarly, since $h_2$ and $h_3$ were chosen uniformly, $< g_1, h_3 > = = A_n$ with high probability, so we have $$(g_1, g_2, h_3) \rightarrow (g_1, h_2, h_3) \rightarrow (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. \end{proof} \end{document}