\documentclass{article}
\usepackage{amsmath,amssymb}
\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{0}{October 29, 2001}{Igor Pak}{M. Alekhnovich}

\section*{Mixing time \& long paths in graphs}

Let $\Gamma$ be a Cayley graph of group $G$: $\Gamma=Caley(G,S),$
$|S|=D,$ $|\Gamma|=n$.
Recall the following notation from the previous lectures:

$\{x_t^v\}$ - random walk on $\Gamma$ starting at $v\in \Gamma$.

$Q_v^t(g)=Pr(x_t^v=g)$

$\tau_4=\min \{t: ||Q_v^t-u||<\frac{1}{4}\ \forall v\in \Gamma\}$

In this lecture we will prove the following result:


\begin{theorem}\label{main}
Let $\Gamma$ be a $D$-regular graph with $\tau_4\le k$ s.t.
$D>8k^2$. Then $\Gamma$ contains a (self-avoiding) path of length greater
than $\frac{|\Gamma|}{16k}$.
\end{theorem}

This theorem holds for an arbitrary $D$-regular graph as well but in this
lecture we will confine ourselves only to Cayley graphs.

\begin{definition}
Let \ $\alpha_v(A) = Pr\left(x_t^v\not \in A,\ \forall\
t\in[1..k]\right)$, \ $\beta_v(A)=1-\alpha_v(A)$.
\end{definition}

Clearly, \, $\beta_v(A)\le \sum_{t=1}^k Pr(x_t^v\in A)=\sum_{t=1}^k Q_v^t(A).$

\begin{proposition} \ FOr any \, $A \subseteq G$, we have:
\ $\sum_{v\in \Gamma} \beta_v(A) \le k|A|$.
\end{proposition}

\begin{proof}
$$\sum_{v\in \Gamma} \beta_v(A)\le \sum_{v\in \Gamma}\sum_{t=1}^k Q_v^t (A)=
\sum_{t=1}^k \sum_{z\in A}\sum_{v\in\Gamma} Q_v^t(z)=k|A|$$
\end{proof}

\begin{lemma}\label{l1} For any $A \subseteq G$ and any $\beta>0$ we have:
$$\#\{v\in \Gamma:\beta_v(A)<\beta\}\ge n-\frac{k|A|}\beta$$
\end{lemma}

\begin{proof}
Let $m=\#\{v\in \Gamma:\beta_v(A)\ge \beta\}$. Since
$m\beta\le \sum_{v\in \Gamma}\beta_v(A)\le k|A|$ we have
$m\le \frac{k|A|}{\beta}$ and
$$\#\{v\in \Gamma:\beta_v(A)<\beta\}=n-m\ge  n-\frac{k|A|}\beta.$$
\end{proof}

\begin{lemma}\label{l2}
Let
$$\rho:=\min_{\begin{array}{c}|B|=k\\ v\not\in B\end{array}}
Pr(x_1^v,...,x_k^v\not\in B \land [\mbox{all $x_i^v$ are distinct}])$$
$$\delta:=1-\rho$$
Then $\rho>1-\frac{2k^2}D;$ $\delta<\frac{2k^2}{D}.$
\end{lemma}

\begin{proof}
$$\rho\ge \left(1-\frac{|B|+1}D\right)\cdot...\cdot\left(1-\frac{|B|+k}D\right)>
{\left(1-\frac{2k}D\right)}^k>1-\frac{2k^2}D$$
\end{proof}

\begin{lemma}\label{l3}
Let $$\xi_v(A)=\min_{\begin{array}c B\subset G, |B|=k\\ v\not\in A\cup B\end{array}}
\alpha_v(A\cup B)$$
$$Z(A,\beta)=\{v\in\Gamma:\xi_v(A)>1-\beta-\frac{2k^2}D\}$$
Then $\forall A\subset \Gamma$ $|Z(A,\beta)|>n - \frac{k|A|}\beta.$
\end{lemma}

\begin{proof}
$$\xi_v(A)\ge 1-\beta_v(A)-\delta>^{(Lemma~\ref{l2})}1-\beta-\frac{2k^2}D$$
if $\beta_v(A)<\beta$. Hence, by Lemma~\ref{l1}
$$\xi_v(A)>1-\beta-\frac{2k^2}D$$
for more than $n-\frac{k|A|}\beta$ points.
\end{proof}

\begin{definition}[failure probability]
Assume that $v$ and $A$ are given. The random walk starting in $v$ is {\em successful}
iff all $x_i$ $i\in[1..k]$ are distinct and don't belong to $A$.
Let the {\em failure probability} be
$$fp(v,A)=1-Pr(x_1^v,...,x_k^v\not\in A\land [\mbox{all $x_i^v$ are distinct}]).$$
\end{definition}

Clearly $||A_v^k-U||\ge \frac{|Z|}{|\Gamma|}-Q_v^k(Z)$. By the statement of
the theorem $||A_v^k-U||<\frac 1 4$.
Thus $Q_v^k(Z)>\frac {|Z|}n-\frac 1 4$ for any $Z\subseteq \Gamma.$

\begin{mproof}{\bf Proof (of the Theorem):}

Fix $\gamma:=\frac 1 2;$ $\beta:=\gamma-\frac{2k^2}D\le \frac 1 2 - \frac 1 4 = \frac 1 4.$
Let $A$ be some set s.t.
$\exists v\not \in A$ for which failure probability is less or equal than $\gamma$.
Let us denote
$$p=Pr(x_1^v,...,x_k^v\not\in A\land [\mbox{all $x_i$ are distinct}]\land
 fp(x_k^v, A\cup \{x_1^v,...,x_{k-1}^v\})<\gamma).$$
Then
$$p\ge Pr(x_k^v\in Z(A,\beta))-\gamma\ge \left(\frac {|Z(A,\beta)|}{|\Gamma|}-\frac 1 4\right)-\gamma>
1-\frac{k|A|}{\beta n}-\frac 1 4 - \frac 1 2= \frac 1 4 - \frac{k|A|}{\frac 1 4 n},$$
which is greater than $0$ as long as $|A|<\frac{n}{16 k}.$

Let us set $A=\emptyset$ at the start. By Lemma~\ref{l2}, $\exists v\ fp(v,A)<\gamma.$
Since $p>0$ we can choose at least one self-avoiding path with ``good'' end-point.
We can continue the process of constructing the path as long as
$p>0$ which is equivalent to $|A|<\frac n {16 k}$. Thus there exists a path
of length greater or equal
$\frac n {16 k}$.
\end{mproof}

At the end, I would like to mention about the following conjecture
of Lov\'asz:

{\em\noindent Every Cayley graph has a Hamiltonian path.}

The main Theorem shows that it is not very easy to produce a counterexample
to this conjecture in class of groups with small mixing time.

Also, we proved Theorem~\ref{main} in a non-constructive way, but in
fact using these ideas one can find a long path in polynomial time.
For this, it is sufficient to test $x_k^v\in Z$ efficiently.
\end{document}