\documentclass{article} \usepackage{amsmath,amssymb,amsfonts} \usepackage{amsthm} \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{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{example}{Example} \renewenvironment{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{14}{17 October 2001}{Igor Pak}{C. Goddard} \section*{Hall Bases Continued} Last lecture we finished with the theorem: \begin{theorem} \label{completeThenUniform} Given a $\omega$ - complete word in $\overline{B} = (B_1, B_2, \ldots)$, a Hall Basis in G, then $\omega^{\overline{\alpha}}$ - uniform in $G$. \end{theorem} Now two lectures ago, we wanted to prove the following lemma: \begin{lemma} \label{stoppingStrongUniform} $\varkappa$ for $\mathrm{U}(n,p) = \left\{\begin{pmatrix}1&\ast&\cdots&\ast\\ 0&1&\cdots&\ast\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&1\end{pmatrix}\:\ast\in\mathbb F_p\right\}$ is strong uniform. \end{lemma} We proved a corollary to this: \begin{corollary} The mixing time for a random walk on $\mathrm{U}(n,p) = \mathrm{O}(n^2 \log n)$. \end{corollary} Now we want to prove Theorem \ref{completeThenUniform} $\Rightarrow$ Lemma \ref{stoppingStrongUniform}. \begin{proof} Let $G = \mathrm{U}(n,p)$, that is the group of $n \times n$ upper triangular matrices with 1's on the diagonal. Consider the basis: $\overline{B} = (B_1, B_2, \ldots, B_{n-1})$ where $$B_i = \left\{ \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & 1 & \vdots \\ \vdots & & \ddots & 0 \\ 0 & \cdots & 0 & 1 \\ \end{pmatrix}\: \mbox{with a 1 in the $i$th diagonal.} \right\}$$ Thus $|B_i| = n - i$. Now we have to check $\overline{B}$ is a Hall basis for $\mathrm{U}(n,p)$. This is ``obvious'' since we know that $\mathrm{<}\gamma_i(B_i)\mathrm{>} = H_i$ since, firstly $\mathrm{<}B_i\mathrm{>} = G_i$, where $G_i$ consists of $0$'s everywhere below the $i$th diagonal except the main diagonal, and $H_i$ is the quotient $G_{i-1} / G_{i}$, so $H_i \cong (\mathbb{Z}_p)^{n-i}$. For the mixing time, we know $X_t = E_{i_1j_1}(\alpha_1) \cdot E_{i_2j_2}(\alpha_2) \cdot \ldots \cdot E_{i_tj_t}(\alpha_t)$ by definition since $$E_{ij}(\alpha) = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \alpha & 0 \\ \vdots & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1\\ \end{pmatrix}\: \mbox{ie 1's on the diagonal and 0's elsewhere except $\alpha$ in the $ij$th position} $$ Now we want to look at $\varkappa$, which is the first time all the indices $i$, $j$ occur in this product. So in the notation of the previous lecture, $\Lambda = \{ (i,j), 1 \leq i < j \leq n\}$. Say that there are $N$ words that contain all $i$, $j$ and look at the complete words. Thus, $$\Pr(X_t = h | \varkappa = t) = \frac{1}{N} \cdot \sum_{\omega} \Pr(\omega^{\overline{\alpha}} = h)$$ where we sum over the complete words $\omega$ of length $t$ such that no shorter word is a complete word. Therefore from Theorem \ref{completeThenUniform}, $\omega$ is uniform. So, $$\Pr(X_t = h | \varkappa = t) = \frac{1}{N} \cdot N \cdot \frac{1}{|G|} = \frac{1}{|G|}$$ Thus, $\varkappa$ is strong uniform. \end{proof} Note, we can generalise this to any nilpotent group with generators corresponding to our generators, and the mixing time $= \mathrm{O}(|\Lambda| \log|\Lambda|)$. \section*{Brief Outline of Open Problems for Research Projects} \subsection*{Hamilton Paths in Cayley Graphs} There are two conflicting conjectures relating to the Hamilton paths in Cayley graphs, namely: \begin{conjecture}{\bf (Lovasz)} \label{lovasz} $\forall G,\ \mathrm{<}S\mathrm{>} = G,\ S = S^{-1}$, the Cayley graph $\mathrm{\Gamma}(G, S)$ contains a Hamilton path. \end{conjecture} \begin{conjecture}{\bf (Babai)} \label{babai} $\exists \alpha > 0$ such that $\exists$ infinitely many Cayley graphs with no paths on length $> (1 - \alpha) \cdot \# vertices$. \end{conjecture} Aim: try and find out which one of these is true on a special groups and generating sets. {\it Examples:} \smallskip \noindent $1)$ \, Try Hall's 19 (up to automorphisms) Cayley graphs of $A_5$ with $2$ generators (aim for negative answer.) \noindent $2)$ \, Try $S_n$ and conjugacy classes (aim for positive answer.) \noindent $3)$ \, Try general nilpotent groups (positive.) \noindent $4)$ \, Try three involutions in general groups (positive.) \, NB: every finite simple group can be generated by three involutions. \noindent $5)$ \, Try wreath and semidirect product of finite groups (positive; easy for direct products.) \subsection*{Diameter Problem} Suppose we have $A_n$, $S_n$ and $\mathrm{<}S\mathrm{>} = A_n$, where $S$ is a set of generators. \begin{conjecture} $\mathrm{diameter}(A_n, S) < cn^2$, $c$ - constant. Also works for $S_n$. \end{conjecture} Look at the following weaker versions of this: \begin{enumerate} \item For the worst case when $|S| = 2$, we have the following: \begin{theorem}{\bf (Babai, Hetyei)} $\mathrm{diam} < e^{\sqrt{n} \log n(1 + \mathrm{o}(1))}$. This gives a bound of the maximum order of permuations in $S_n$. \end{theorem} Aim: Find something similar for $\mathrm{SL}(n, p)$. \begin{conjecture} $G$ - simple $\Rightarrow \mathrm{diam} = \mathrm{O}((\log |G|)^c)$. \end{conjecture} So $\mathrm{diam} \leq (n^2 \log p)^2$ which would be hard to prove, but $e^{n}$ may be manageable. \item Average Case. \begin{theorem}{\bf (Dixon)} $\mathrm{<}\sigma_1, \sigma_2\mathrm{>} = A_n$ with $\Pr \rightarrow 1$ as $n \rightarrow \infty$. \end{theorem} \begin{theorem}{\bf (Babai-Seress)} $\mathrm{diam}(\mathrm{\Gamma}(A_n, \{\sigma_1, \sigma_2\})) = n^{\mathrm{O}(\log n)}$ \, w.h.p. \end{theorem} Aim: get something close for $\mathrm{PSL}(n,p)$. \item Problem. \begin{conjecture}{\bf (Kantor)} $\mathrm{diam}(\mathrm{\Gamma}(A_n, \{\sigma_1, \sigma_2\})) = \mathrm{O}(n \log n)$ w.h.p. \end{conjecture} Some people believe this is not true. Question: True or False? Weaker version: Prove that $\mathrm{\Gamma}(A_n, \{\sigma_1, \sigma_2\})$ are NOT exanders w.h.p. \end{enumerate} \subsection*{Random Graphs vs Random Cayley Graphs} \begin{enumerate} \item \begin{theorem} {\bf (Ramsey Theory)} \ In random undirected graph $\mathrm{\Gamma}$ with $n$ vertices, there exists a $m=c \cdot \log n$ complete subgraph in $\mathrm{\Gamma}$ and a $m=c \cdot \log n$ complete subgraph in $\mathrm{\overline{\Gamma}}$~w.h.p. \end{theorem} Now suppose $\mathrm{\Gamma}$ 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}$.) \item \begin{theorem} $\mathrm{\Gamma}$ - random graph on $n$ vertices $\Rightarrow \mathrm{Aut}(\Gamma) = 1$ with high probability. \end{theorem} NB: Erd\H os and R\'enyi proved that one has to remove $\theta(n^2)$ edges before a nontrivial automorphism appears. Question: if $\mathrm{\Gamma}$ - random Cayley graph, is $\mathrm{Aut}(\Gamma) = G$ with high probability? L. Goldberg and M. Jerrum conjecture this for $G = \mathbb{Z}_n$. \end{enumerate} \subsection*{Percolation on finite Cayley graphs } Fix a Cayley graph $\mathrm{\Gamma}$ and probability $p$. Delete edges with $\Pr = (1 - p)$ independently and look at the connected components. Say $\mathrm{\Gamma} \supset$ large cluster if $\exists$ connected component $> \frac{1}{2} |\Gamma|$. \begin{conjecture}{\bf (Benjamini)} If $\mathrm{diam}(\Gamma) < c \cdot \frac{|G|}{\log^2 |G|}$, then Cayley graph $\Gamma$ contains large cluster with $\Pr > \frac{1}{2}$ for $p < 1 - \varepsilon$ where $\varepsilon$ is independent of the size of the graph. \end{conjecture} Itai Benjamini confirms the conjecture for abelian groups. Question: Is this true for G nilpotent? What about $S_n$? \end{document}