\documentclass[11pt]{article}
\ifx\pdftexversion\undefined
\usepackage [dvips]{graphicx}
\else 
\usepackage[pdftex]{graphics}
\fi
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{palatino}
\usepackage{mathdots}

\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.0 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}

\title{Notes for Math 261 -- September 26, 2005}
\author{Paul K. Horn}
\begin{document}

%%%%% Boilerplate
    September 26, 2005\\
    Paul K Horn
    \begin{center}
    {\Huge Random Walks on Graphs and Directed Graphs}
    \end{center}
\hrule
\vspace{.2in}
%%%%% Boilerplate

{\Large Introduction}
\section{Introduction} 

In this course we study random walks on graphs and directed graphs (or 
reversible Markov chains and non-reversible Markov chains).  In order 
to accomplish this goal we look at both probabilistic and spectral methods.  
While it may seem somewhat surprising, spectral methods provide a powerful 
tool to study random walks, as many related invariants such as mixing rate are 
controlled by a graph's eigenvalues.  Also, some recent developments have 
focused
on algorithmic aspects of random walks.

Much of the work that has been done concerns (undirected) graphs.  
For instance, for spectral methods having a symmetric matrix makes things
nicer; while the directed case is much harder.  Since graphs tend to be very
large and complicated, spectral methods help immensely in allowing us to 
dictate the shape and properties of the graph with just a few invariants,
as opposed to trying to keep track of everything.  

It is natural, however, to consider the more complicated directed case.  
Directed graphs occur often in the real worlds; graphs such as the web-graph
are directed.  Recently there have been some developments in the directed 
graph case.  

Essentially, our work boils down to studying 3 things: random walks, random
graphs, and spectral methods.

\section{Random Graphs}
What is meant by "random graph"?  Really, when we consider random 
graphs, what we are doing is considering all graphs on $n$ vertices, given 
some appropriately defined probability space.  A way to think about random
graphs is that we put all graphs into a pot, and when we pluck graphs out of
the pot we do so according to their probability 
distribution.  The easiest probability distribution to think about is just
picking a graph uniformly, that is we are equally likely to chose any 
of the graphs.
\subsection{Erd\"os-Reyni Model}
Erd\"os and Reyni pioneered the field of random graphs in 1960.  They 
introduced the $G(n,p)$ model of random graphs on $n$ vertices with a 
probability parameter $p$, $0 < p < 1$.   
Here we give two definitions.

{\bf Definition 1} Each pair $(u,v)$ is {\it independently} chosen to be an
edge with probability $p$.

{\bf Definition 2} 
$Pr(X = G) = p^{\#\mbox{of edges in G}}(1-p)^{\#\mbox{of non-edges}}$ 

In the second definition, $X$ is a {\bf random variable}.  This is like the
arm that reaches into our pot, and plucks out our graph.  Also of importance
in the independence in definition 1; this means that selection of any given
edge does not depend on any of the other pairs being selected or not selected. 
This assumption is vital to much of the analysis that is done.  The probability
of two independent events is equal to the product of the probabilities of 
the individual events.  

As an example, consider the eight (labeled) graphs on 3 vertices.  If we take
$p = \frac{1}{2}$, then we look at all graphs have a probability of 
$\frac{1}{8}$, so we have a uniform distribution.  If we change $p$, however,
we no longer have a uniform distribution.  For example the graph pictured below
would be chosen with probability $p(1-p)^{2}$.\\  
\begin{center} \includegraphics{tiny} \end{center}

\subsection{Ramsey Numbers} As an application, we briefly consider Ramsey 
numbers.  The Ramsey number $R(k,k)$ is the smallest $n$ such that any two
coloring of $K_n$ contains a monochromatic $K_k$.  As an example, $R(3,3)=6$.  
The following diagram demonstrates that $R(3,3) > 5$; we give a two coloring
of $K_5$ such that the induced subgraph on either color forms a $C_5$. 
\begin{center} 
\includegraphics{k5}
\end{center}
We have the following theorem \cite{ER}
\begin{theorem} If ${n \choose k} 2^{1-{k \choose 2}} < 1$ then $R(k,k) > n$.
\end{theorem}
What is the smallest $n$ satisfying this theorem?  
Stirling's approximation \cite{BOL} tells us
\begin{eqnarray*}
\sqrt{2\pi n}(n/e)^{n} \leq n! \leq e^{1/12n} \sqrt{2\pi n}(n/e)^{n}
\end{eqnarray*}
In particular we can use this to say that
\begin{eqnarray*}
{n \choose k} \leq \left(\frac{en}{k}\right)^{k}
\end{eqnarray*}
and in order for
\begin{eqnarray*}
\left(\frac{en}{k}\right)^{k} 2^{1-{k \choose 2}} < 1
\end{eqnarray*}
we have
\begin{eqnarray*}
k(\log_2(n) + \log_2(e) + \log_2(k)) + 1 - {k \choose 2} &<& 0
\end{eqnarray*}
which tells us
\begin{eqnarray*}
2\log_2 n < k
\end{eqnarray*}
or $n \approx 2^{k/2}$.  The best known bound for the Ramsey number
$R(k,k)$ is
\begin{eqnarray*}
  \frac{\sqrt{2}}{e}(1 + o(1))k2^{k/2} \leq R(k,k) \leq {2k-2 \choose k-1} \approx 
4^{k}
\end{eqnarray*}
The lower bound is due to Spencer, and uses the Lov\'asz Local Lemma \cite{AS}. This bound beats the original lower bound,
 $R(k,k) > \frac{1}{\sqrt{2}e}(1+o(1))k2^{k/2}$, by a factor of two.  This 
original bound
was given by Erd\"os and R\'enyi \cite{ER}; the proof is not dissimilar to
the proof we give for theorem 1, but requires more careful analysis.  
Information on upper bounds can be found in Graham, Rothschild, and Spencer 
(1990) \cite{GRS}.  
Note that although the inequality $R(k,k) \leq {2k - 2 \choose k-1}$
is often proper (by a parity argument), getting even a $(1-\epsilon)$ 
improvement is open.  

\begin{proof}[Proof of Theorem 1]  We color the edges of a complete 
graph on $n$ vertices randomly, so that edges are chosen to be blue 
independently with probability $1/2$.  Note that the blue (and red) edges
are random graphs $G(n,1/2)$.  Consider a subset $S$ of $k$ vertices.  The
probability that the induced $K_k$ on $S$ is blue is
\begin{eqnarray*}
P(\mbox{$K_k$ is blue}) = \left(\frac{1}{2}\right)^{{k \choose 2}}
\end{eqnarray*}
thus
\begin{eqnarray*}
P(\mbox{$K_k$ is monochromatic}) = \frac{1}{2^{{k \choose 2} -1}}.
\end{eqnarray*}
Therefore
\begin{eqnarray*}
P(\mbox{There exists a monochromatic $K_k$}) \leq {n \choose k}
2^{1-{k \choose 2}}
\end{eqnarray*}
If this probability is less than 1, then there exists a graph on $n$ vertices
such that no monochromatic $K_k$ exists; proving the theorem.
\end{proof}
\section{Random Walks}
We first consider walks on undirected graphs.  A {\bf walk} is a sequence 
of vertices $v_0,v_1,\dots, v_t$ where $v_i \sim v_{i+1}$.  (that is 
$\{v_i,v_{i+1}\} \in E(G)$) for $i=0,\dots, t-1$.  

One way to think about random walks is a pebble starts at vertex $v_0$, and 
moves from there, with the probability it moves from vertex $u$ to $v$ 
(assuming it sits at $u$) given by
\begin{eqnarray*}
P(u,v) = \left\{ \begin{array}{cl}\frac{1}{d_u} & \mbox{if $v \sim u$} \\
0 & \mbox{else}
\end{array}
\right.
\end{eqnarray*}
(where $d_u$ is the degree of vertex $u$).  This is a walk using a transition
probability matrix.  

A second way of looking at random walks is to look at the probability 
 distribution of
destinations after $t$ steps.  In this case, we think of a mass of size one
starting at the initial vertex $v_0$, then spreading itself out over the
vertices according to the transition rules; the mass at a particular
vertex at time $t$ represents the probability that a walk would end there at
time $t$.  
Formally we can define an initial distribution 
\begin{eqnarray*}
f_0 = \left\{ \begin{array}{cl} 1 & \mbox{at $v_0$} \\
0 & \mbox{elsewhere}
\end{array}
\right. 
\end{eqnarray*}
Then we can recursively define the distribution at time $t$ by
\begin{eqnarray*}
f_{t}(v) = \sum_{u \sim v} f_{t-1}(u)P(u,v)
\end{eqnarray*}
by representing $f_t$ as a vector, and $P$ as a transition matrix we
get the following nice representation:
\begin{eqnarray*}
f_t = f_{t-1}P
\end{eqnarray*}
and in general 
\begin{eqnarray*}
f_{t} = f_{0}P^{t}
\end{eqnarray*}
It is useful to note that multiplying on the left by $f$ (as opposed to the
more traditional multiplication on the right) allows us to have a more
convenient multiplication.  Thus this becomes our convention.  
\begin{thebibliography}{99}
\bibitem{AS} N. Alon, J. Spencer, The Probabilistic Method, second edition, 
John Wiley and Sons, 2000
\bibitem{ER} P. Erd\"os, A. R\'enyi, "On the evolution of random graphs", 
Maygyar. Tud. Akad. Mat. Kutat\'o Int. K\"ozl. 5 (1960) 17-61.  
\bibitem{GRS} R.L. Graham, B.L. Rothschild, and J.H. Spencer, Ramsey Theory,
second edition, Wiley, New York, 1990.
\bibitem{BOL} B. Bollob\'as, Modern Graph Theory, Springer 1998.  
\end{thebibliography}
 \end{document}