\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{bm}
\usepackage{latexsym}
\usepackage{epsfig}

\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}


\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in {{\sf STAT 260B: Open problems in probability} 
\hfill \sf #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\em #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecture date: #3}{Scribe: #4}{Lecture #1}}


\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\sloppy


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{answer}[theorem]{Answer}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{example}[theorem]{Example}
\newenvironment{proof}{\noindent \textbf{Proof:}}{$\Box$}

\newtheorem{claim}[theorem]{Claim}

\newcommand{\ignore}[1]{}


\renewcommand{\Pr}{{\bf P}}
\renewcommand{\P}{{\bf P}}
\newcommand{\Px}{\mathop{\bf P\/}}
\newcommand{\E}{{\bf E}}
\newcommand{\Ex}{\mathop{\bf E\/}}

\newcommand{\Var}{{\bf Var}}
\newcommand{\Cov}{{\bf Cov}}
\newcommand{\Varx}{\mathop{\bf Var\/}}

\newcommand{\bits}{\{-1,1\}}

\newcommand{\nsmaja}{\textstyle{\frac{2}{\pi}} \arcsin \rho}

\newcommand{\Inf}{\mathrm{Inf}}
\newcommand{\I}{\mathrm{I}}
\newcommand{\J}{\mathrm{J}}

\newcommand{\eps}{\epsilon}
\newcommand{\lam}{\lambda}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Z}{\mathbb Z}
\newcommand{\C}{\mathbb C}
\newcommand{\CalE}{{\mathcal{E}}}

\newcommand{\CalU}{{\mathcal{U}}}
\newcommand{\F}{{\mathcal{F}}}
\newcommand{\CalC}{{\mathcal{C}}}
\newcommand{\CalM}{{\mathcal{M}}}
\newcommand{\CalR}{{\mathcal{R}}}
\newcommand{\CalS}{{\mathcal{S}}}
\newcommand{\CalV}{{\mathcal{V}}}
\newcommand{\CalX}{{\boldsymbol{\mathcal{X}}}}
\newcommand{\CalG}{{\boldsymbol{\mathcal{G}}}}
\newcommand{\CalY}{{\boldsymbol{\mathcal{Y}}}}
\newcommand{\CalZ}{{\boldsymbol{\mathcal{Z}}}}
\newcommand{\CalF}{{\mathcal{Z}}}
\newcommand{\boldG}{{\boldsymbol G}}
\newcommand{\boldQ}{{\boldsymbol Q}}
\newcommand{\boldR}{{\boldsymbol R}}
\newcommand{\boldS}{{\boldsymbol S}}
\newcommand{\boldX}{{\boldsymbol X}}
\newcommand{\bfX}{{\boldsymbol X}}
\newcommand{\boldB}{{\boldsymbol B}}
\newcommand{\boldY}{{\boldsymbol Y}}
\newcommand{\boldZ}{{\boldsymbol Z}}
\newcommand{\boldV}{{\boldsymbol V}}
\newcommand{\boldsigma}{{\boldsymbol \sigma}}
\newcommand{\boldupsilon}{{\boldsymbol \upsilon}}
\newcommand{\hone}{{\boldsymbol{H1}}}
\newcommand{\htwo}{\boldsymbol{H2}}
\newcommand{\hthree}{\boldsymbol{H3}}
\newcommand{\hfour}{\boldsymbol{H4}}
\newcommand{\poly}{\boldsymbol{poly}}


\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\Maj}{\mathrm{Maj}}
\newcommand{\Thr}{\mathrm{Thr}}
\newcommand{\littlesum}{{\textstyle \sum}}

\newcommand{\half}{{\textstyle \frac12}}

\newcommand{\Stab}{\mathbb{S}}
\newcommand{\StabThr}[2]{\Gamma_{#1}(#2)}
\newcommand{\TestFcn}{\Psi}

\renewcommand{\phi}{\varphi}
\def \la      {\langle}
\def \ra      {\rangle}

\DeclareMathOperator{\Prob}{Prob}
\DeclareMathOperator{\sizeof}{sizeof}

\begin{document}
\lecture{3}{3}{Jan 24}{Ron Peled}
\begin{section}{Free minimal spanning forest, union with percolation and Wired minimal spanning forest}
Let $G=(V,E)$ be a connected, locally finite graph. Let us define the Free Minimal Spanning Forest (FMSF) on $G$.

The FMSF is a random subset of the edges of $G$, forming a forest. To define the FMSF first attach to each edge $e\in E$ a random label $U(e)$ such that $\{U(e)\}_{e\in E}$ are IID uniform $[0,1]$. Then calculate for each $e\in E$:
\begin{equation*}
Z(e) = \inf_{\phi=(e_1,\ldots,e_k)}\max_{1\le i\le k} U(e_i)
\end{equation*}
Where the infimum runs over all finite paths in $G$ connecting the end points of $e$ and not containing $e$ itself. If there are no such paths we let $Z(e)=1$. Then the FMSF is $\{e\in E\ | U(e)<Z(e)\}$.
 
Some facts about the FMSF (exercises):
\begin{itemize}
\item The FMSF of a finite graph $G$ is a tree, called the minimal spanning tree (MST).
\item Suppose $G_1=(V_1,E_1)$ is an induced subgraph of $G_2=(V_2,E_2)$, that is, $V_1\subseteq V_2$ and $E_1=\{(u,v)\in E_2\ |\ u,v\in V_1\}$.

Consider the FMSF's $F_1$ and $F_2$ of $G_1$ and $G_2$ respectively and couple them together by using the same random labels $\{U(e)\}$ for both. We easily see that $F_2\cap E_1\subseteq F_1$, since if an edge $e\in F_2\cap E_1$ it means that in $G_2$ there is no path connecting the end points of $e$ all of whose labels are smaller than $U(e)$. In this case there is certainly no such path in the subgraph $G_1$.

In particular, if $G=(V,E)$ is an infinite graph and $G_1\subseteq G_2\subseteq \ldots$ where $G_i=(V_i,E_i)$ is an infinite increasing sequence of induced finite subgraphs of $G$ with $\cup_i V_i=V$ and with each $G_i$ being connected. Then the MST's $F_i$ in $G_i$ (coupled by having all use the same labels $\{U(e)\}$) converge monotonically to the FMSF in $G$ in the sense that for each edge $e\in E$. For all $i$ such that $e\in E_i$, the indicator $1_{\{e\in F_i\}}$ is monotonically decreasing and $1_{\{e\in F_i\}}\to 1_{\{e\in F\}}$ (a.s.).
\end{itemize}
*\underline{Exercise}: Find an infinite graph $G$ where the FMSF is not connected (to be solved next lecture).

A non elementary example of a solution to the exercise is the graph $T\times \Z$ where $T$ is a regular tree and the product graph has as vertex set the product of the two vertex sets and has an edge between $(t,m)$ and $(s,n)$ iff either $t=s$ and $m$ is connected to $n$ in $\Z$ or $m=n$ and $t$ is connected to $s$ in $T$.

Pemantle and Peres \cite{PP1} showed that this graph has infinitely many components to its FMSF by showing that there can be no automorphism invariant (in distribution) random tree on this graph.

***\underline{Exercise}: Find a direct proof of the fact that the FMSF has infinitely many components for $T\times\Z$.

We also mention a related "construction" which illustrates some of the pitfalls of proving existence of continuous time processes. Given a graph $G=(V,E)$ and random labels $\{U(e)\}$ on its edges as before. One may try to define a continuous time process indexed by the time set $T=[0,1]$ which at any time $t$ is a random subgraph of $G$, such that at time $t\in T$ we add all the edges $(u,v)\in E$ which have $U(u,v)=t$ and with the endpoints $u$ and $v$ not already connected by some path at a previous time. On the one hand, intuition says that this should give the FMSF of $G$ at time $t=1$, but on the other hand, the subgraph obtained at each time is clearly connected.

The paradox is resolved by noting that such a process does not actually exist. One needs to be careful when trying to construct a process which at each time can add infinitely many edges according to global dependencies on the subgraph constructed up to that time. Such a process may not exist.

We now prove a theorem concerning the union of the FMSF with independent bond percolation:
\begin{theorem} Let $G=(V,E)$ be a connected, locally finite graph. For $\eps>0$, let $W_\eps\subseteq E$ be an independent bond percolation on $G$ with probability $\eps$ of an open edge. That is, $W_\eps\subseteq E$ and each $e\in G$ satisfies $\P(e\in W_\eps)=\eps$ independently of other edges. Let $F$ be the FMSF of $G$ and suppose that $W_\eps$ and $F$ are independent, then $W_\eps\cup F$ is a.s. connected.
\end{theorem}
\begin{proof}
The key step is to observe that for $e\in E$, given $Z(e)$ and that $e\notin F$ then $U(e)\sim \text{uniform}(Z(e),1)$. This is intuitively obvious and we shall not prove it here. We note also that this remains true conditioned on $\{U(e_j)\}$ for finitely many $e_j\notin F$.

It follows that we can couple the bond percolation and the FMSF of $G$ in such a way that
\begin{equation}
\begin{split}
\label{percolation_union_condition}
F^{(\eps)}:=F\cup W_\eps &= F\cup\{e\in E\ |\ Z(e)\le U(e)< Z(e) + \eps(1-Z(e))\} =\\
&= \{e\in E\ |\ 1-U(e)>(1-\eps)(1-Z(e))\}
\end{split}
\end{equation}
Where we've used the fact that a.s. $Z(e)\ne 1$ for all $e\in E$.

Now note that since $G$ is connected, it is enough to show for any edge $(u,v)\in E$ that $u$ and $v$ are connected in $F^{(\eps)}$. Fix a particular realization of the labels $\{U(e)\}$. Take an edge $e=(u,v)\notin F^{(\eps)}$, then by \eqref{percolation_union_condition} we know
\begin{equation}
\label{not_in_Feps_eq}
1-U(e)<(1-\eps)(1-Z(e))
\end{equation}
Since a.s. equality does not hold. And by the definition of $Z(e)$, this means that we have a path $\phi=(e_1,e_2,\ldots,e_k)$ connecting $u$ and $v$ for which $\max_i U(e_i)$ is so close to $Z(e)$ that
\begin{equation}
\label{U_e_first_decrease}
\frac{1-U(e)}{1-\eps}<\min_i(1-U(e_i))
\end{equation}
Now if all $\{e_i\}$ are in $F^{(\eps)}$ we are done. Otherwise there again exists a $j$ with $Z(e_j)<U(e_j)$, and then we have another path $\phi=(e_1^2,e_2^2,\ldots,e_{k_2}^2)$ connecting the edges of $e_j$ and satisfying$\frac{1-U(e_j)}{1-\eps}<\min_i(1-U(e_i^2))$. Combining with \eqref{U_e_first_decrease} we get
\begin{equation*}
\frac{1-U(e)}{(1-\eps)^2}<\min_i(1-U(e_i^2))
\end{equation*}
Again, if all $\{e_i^2\}$ are in the $F^{(\eps)}$ we are done, otherwise we iterate the preceding procedure. After the $k$'th iteration we get
\begin{equation}
\frac{1-U(e)}{(1-\eps)^k}<\min_i(1-U(e_i^k))
\end{equation}
But this inequality shows that we must stop at a finite stage $k$ since $\frac{1}{1-\eps}>1$ and so the left hand side will eventually be bigger than $1$. This finishes the proof of the theorem.
\end{proof}

*\underline{Exercise}: Show that this is false if $W_\eps$ is just an invariant ergodic percolation with marginals $\eps$.

\begin{definition}
For a connected graph $G=(V,E)$, the Wired Minimal Spanning Forest (WMSF) $F_w$ in $G$ consists of the edges $\{e\in E\ |\ U(e)<Z_w(e)\}$ with
\begin{equation*}
Z_w(e) = \min(Z(e),\inf\sup_j U(e_j))
\end{equation*}
Where $Z(e)$ is the same as in the FMSF and to describe the $\inf$, let $P_u$ be the collection of all paths from $u$ to infinity, then the $\inf$ is taken over $\{p_1\cup p_2\ |\ p_1\in P_u, p_2\in P_v, p_1\cap p_2=\emptyset, e\notin p_1\cup p_2\}$. That is all paths between $u$ and $v$ which "go through infinity" and do not contain $e$.
\end{definition}
Note that unlike the FMSF, the WMSF in a tree does not have to be a tree. And furthermore if a percolation which removes edges with probability $\eps$ was made on the WMSF, only finite components would remain.
\end{section}
\begin{thebibliography}{999}
\bibitem{PP1} Pemantle, R. and Peres, Y. \emph{Nonamenable products are not treeable}. Israel J. Math. 118 (2000), 147--155.
\end{thebibliography}
\end{document}