\documentclass{article}

\usepackage{amsmath,amssymb, amscd}
\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}
\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}

\begin{document}
\lecture{29}{26 November 2001}{Igor Pak}{Etienne Rassart}

\section*{Two theorems on the product replacement graph}

Let $\Gamma_k(G)$ be the graph with vertex set $\{(g_1,\ldots,g_k)\in G^k : \langle g_1,\ldots,g_k\rangle = G\}$ and edges
\begin{eqnarray*}
(g_1,\ldots,g_i,\ldots,g_k) & \longleftrightarrow & (g_1,\ldots,g_ig_j^{\pm 1},\ldots,g_k)\\
& \longleftrightarrow & (g_1,\ldots,g_j^{\pm 1}g_i,\ldots,g_k)\,,
\end{eqnarray*}
for a finite group $G$.

{\bf Conjecture } $\Gamma_k(G)$ is connected if $k\geq d(G)+1$.

{\bf Theorem } \emph{$\Gamma_k(G)$ is connected if $k\geq d(G)+m(G)$.}

{\bf Corollary } \emph{$\Gamma_k(G)$ is connected if $k\geq 2\log_2|G|$.}


\begin{theorem}{\rm({\bf Babai})}

If $k=2\big\lceil\log_2|G|\big\rceil$ then there is a constant $c>0$ such that $\mathrm{diam}\,\Gamma_k(G)\leq c\cdot{\log_2}^{\!\!2}|G|$.
\end{theorem}

\begin{proof} Let $r=\big\lceil\log_2|G|\big\rceil$, so that $k=2r$ and $m(G)\leq r$.

There is a path in $\Gamma_k(G)$ from $(g_1,\ldots,g_k)$ to $(1,\ldots,1,h_1,1,\ldots,1,h_r,1,\ldots,1)$, where $\langle h_1,\ldots,h_r\rangle=G$. Since we can exchange elements, we can assume that we send $(g_1,\ldots,g_k)$ to $(h_1,\ldots,h_r,1,\ldots,1)$.

We want to go from $(h_1,\ldots,h_r,1,\ldots,1)$ to $(h_1,\ldots,h_r,a_1,\ldots,a_r)$ in such a way that
\begin{displaymath}
\big\{a_1^{\varepsilon_1}\cdots a_r^{\varepsilon_r} : \varepsilon_i\in\{0,1\}\big\}=G\,.
\end{displaymath}

Set $a_1$ to be some $h_i\neq 1$. Then
\begin{displaymath}
(h_1,\ldots,h_r,1,\ldots,1) \longrightarrow (h_1,\ldots,h_r,a_1,1,\ldots,1) \quad \textrm{and} \quad |\{a_1^{\varepsilon_1}\}| = 2\,.
\end{displaymath}

From there we proceed by induction. Suppose we have $(g_1,\ldots,g_k)$ connected to $(h_1,\ldots,h_r,a_1,\ldots,a_i,1,\ldots,1)$ with $|\{a_1^{\varepsilon_1}\cdots a_i^{\varepsilon_i}\}|=2^i$.

Let $C=\{a_1^{\varepsilon_1}\cdots a_i^{\varepsilon_i}\}$ and $A=C\cdot C^{-1}$. A first observation is that if $A\neq G$ then we can find $x$ not in $A$ such that $x$ is at distance at most $2i+1$ from the identity (distance with respect to the generating set $\{h_1,\ldots,h_r,a_1,\ldots,a_i\}$): we take $x$ to be one away from an element on the boundary of $A$. Then we can use $a$'s to get to the boundary and one of the $h$'s for the final step to $x$.

So if we let $a_{i+1}=x$ then we can go from $(h_1,\ldots,h_r,a_1,\ldots,a_i,1,\ldots,1)$ to $(h_1,\ldots,h_r,a_1,\ldots,a_i,a_{i+1},1,\ldots,1)$ in $O(\log|G|)$ steps (since $i\leq r$). Also, $|\{a_1^{\varepsilon_1}\cdots a_{i+1}^{\varepsilon_{i+1}}\}|=2^{i+1}$.

So
\begin{displaymath}
\begin{CD}
(h_1,\ldots,h_r,1,\ldots,1) @>{O(\log^2|G|)}>{\textrm{steps}}> (h_1,\ldots,h_r,a_1,\ldots,a_r) @>{O(\log^2|G|)}>{\textrm{steps}}> (1,\ldots,1,a_1,\ldots,a_r)\,.
\end{CD}
\end{displaymath}

Hence
\begin{displaymath}
\begin{CD}
(g'_1,\ldots,g'_k) @>{O(\log^2|G|)}>> (h'_1,\ldots,h'_r,1,\ldots,1) @>{O(\log^2|G|)}>> (h'_1,\ldots,h'_r,a'_1,\ldots,a'_r)\\
@. @. @VV{O(\log^2|G|)}V \\
@. @. (1,\ldots,1,a'_1,\ldots,a'_r)\\
@. @. @VV{O(\log|G|)}V \\
@. @. (a'_1,\ldots,a'_r,1,\ldots,1)\\
@. @. @VV{O(\log^2|G|)}V \\
@. @. (a'_1,\ldots,a'_r,a_1,\ldots,a_r)\\
@. @. @VV{O(\log^2|G|)}V \\
@. @. (1,\ldots,1,a_1,\ldots,a_r)\\
@. @. @VV{O(\log^2|G|)}V \\
(g_1,\ldots,g_k) @<<{O(\log^2|G|)}< (h_1,\ldots,h_r,1,\ldots,1) @<<{O(\log^2|G|)}< (h_1,\ldots,h_r,a_1,\ldots,a_r)
\end{CD}
\end{displaymath}

So there remains to check that we can go from $(g_1,\ldots,g_k)$ to $(1,\ldots,1,h_1,1,\ldots,1,h_r,1,\ldots,1)$ in reasonable time. If we had $(h_1,\ldots,h_r,t_1,\ldots,t_r)$ instead, we could actually use the $t_i$'s instead of $x$ if some of them lie outside of $C\cdot C^{-1}$ (starting with $t_1$ and adding an element at a time as before; if $t_i$ is inside, we construct $x$ outside as above).

So we can go from $(h_1,\ldots,h_r,t_1,\ldots,t_r)$ to $(h'_1,\ldots,h'_r,t'_1,\ldots,t'_r)$ in $O(\log^2|G|)$ steps.

All the transpositions throughout this process are done in $O(\log|G|)$ steps (overall).
\end{proof}

\begin{theorem}{\rm({\bf Dunwoody})}

If $G$ is solvable and $k\geq d(G)+1$ then $\Gamma_k(G)$ is connected.
\end{theorem}

\begin{proof}
Consider the chain
\begin{displaymath}
\{1\} = G_0 \subseteq G_1 \subseteq \ldots \subseteq G_l = G\,,
\end{displaymath}
where $G_{i-1}$ is minimal $G$-invariant in $G_i$. We proceed by induction.

If $l=0$, there is nothing to prove. If $l\geq 1$, let $M=G_1$. Because $G$ is solvable, $M$ is normal in $G$ and abelian.

Fix $(h_1,\ldots,h_{k-1})$ such that $\langle h_1\ldots,h_{k-1}\rangle = G$.

We can go from $(g_1,\ldots,g_k)$ to $(m,m_1h_1,\ldots,m_{k-1}h_{k-1})$ for $m, m_i \in M$. This is done by working in the quotient group $G/M$, applying the inductive hypothesis, then lifting back to the whole group by taking a representative in each coset.

Next observe that $(m_ih_i)^{-1}\cdot m\cdot(m_ih_i) = h_i^{-1}\cdot m\cdot h_i = m^{h_i}$ since $M$ is abelian. This implies that
\begin{displaymath}
\mathit{word}(m_1h_1,\ldots,m_{k-1}h_{k-1})^{-1}\cdot m\cdot\mathit{word}(m_1h_1,\ldots,m_{k-1}h_{k-1}) = \mathit{word}(h_1,\ldots,h_{k-1})^{-1}\cdot m\cdot\mathit{word}(h_1,\ldots,h_{k-1})\,.
\end{displaymath}

Now $\langle h_1,\ldots,h_{k-1}\rangle = G$, so $(m,m_1h_1,\ldots,m_{k-1}h_{k-1}) \longrightarrow (m^g,m_1h_1,\ldots,m_{k-1}h_{k-1})$ for any $g\in G$ (write $g$ as $\mathit{word}(h_1,\ldots,h_{k-1})$).

Also, $\langle m^g : g \in G\rangle = M$ since $M$ is minimal, and thus $m_1 = m^{g_{i_1}}m^{g_{i_2}}\cdots m^{g_{i_n}}$ for some $g_{i_j} \in G$.

Therefore
\begin{displaymath}
\begin{CD}
(g_1,\ldots,g_k) \hspace{1.5cm}@>>{\phantom{aaaaaaaaaaaaaa}}> (m,m_1h_1,\ldots,m_{k-1}h_{k-1})\\
@. @VVV \\
@. (m^{g_{i_1}}, m_1h_1,\ldots,m_{k-1}h_{k-1})\\
@. @VVV \\
@. (m^{g_{i_1}}, (m^{g_{i_1}})^{-1}m_1h_1,\ldots,m_{k-1}h_{k-1})\\
@. @VVV \\
@. (m^{g_{i_2}}, (m^{g_{i_1}})^{-1}m_1h_1,\ldots,m_{k-1}h_{k-1})\\
@. @VVV \\
@. (m^{g_{i_2}}, (m^{g_{i_2}})^{-1}(m^{g_{i_1}})^{-1}m_1h_1,\ldots,m_{k-1}h_{k-1})\\
@. @VVV \\
@. \ldots\\
@. @VVV \\
@. (m^a, h_1,m_2h_2,\ldots,m_{k-1}h_{k-1}) \quad\textrm{(some $a \in G$)}\\
@. @VVV \\
@. \ldots\\
@. @VVV \\
@. (m^z, h_1,h_2,\ldots,h_{k-1}) \quad\textrm{(some $z \in G$)}\\
@. @VV{\textrm{ since } \langle h_1\ldots,h_{k-1}\rangle = G}V \\
@. (1, h_1,h_2,\ldots,h_{k-1})
\end{CD}
\end{displaymath}
\medskip

Now $(h_1,\ldots,h_{k-1})$ was arbitrary, so any two $(g_1,\ldots,g_k)$ are connected in $\Gamma_k(G)$.

\end{proof}

\end{document}