\documentclass{article}
\include{macros}

\begin{document}
% lecture number : lecture title : scribe

%\include{macros.tex}
\lecture{1}{Overview}{Asaf Nachmias}{asafnach@math.berkeley.edu}

\section{Minimal spanning trees and forests}

Let $G=(V,E)$ be a finite graph and let $\{ w_e \} _{e \in E}$ be
distinct real weights on the edges. The {\em minimal spanning
tree} (MST for short) of the graph is the spanning tree $T$, for
which the sum of weights $w(T) = \sum _{e \in T} w(e) \,$ is
minimal amongst all spanning trees of $G$. Assume from now on that
$\{w_e \} _{e \in E}$ are i.i.d. uniform on $[0,1]$.

Let $G$ be a connected, infinite graph with finite degrees and fix
two vertices $v,w$ in it. Let $G_n$ be a sequence of induced
finite subgraphs such that $\cup _n G_n = G$ and let $L_n$ be the
distance in between $v$ and $w$ in the MST on $G_n$.

{\bf Question.} Is $\{ L_n \}$ a tight sequence? I.e., is true
that as $M \to \infty$,
$$ \sup _n \P (L_n > M) \to 0 \, ?$$

The following exercise gives an equivalent definition of a minimal
spanning tree.

{\bf Exercise.} Let $E_H$ be the set of edges that are ``heaviest
in a cycle'', i.e.
$$ E_H = \{e : \exists \textrm{ cycle } e=e_1,e_2,\ldots,e_k
\textrm{ with } w_e = \max _{i\leq k} w_{e_i} \} \, .$$ Then
$T=E-E_H$ is the minimal spanning tree.

Using the exercise we define the {\em free minimal spanning
forest} (FMSF for short) of an infinite, connected graph $G$ with
finite degrees simply as the forest obtained by removing the edges
$E_H$ from the graph. It is easy to observe that this has no
finite connected components. The event that the FMSF is connected
is has probability $0$ or $1$ by translation invariance. It is
also known that with probability $1$, the FMSF of $\Z ^2$ is
connected.

{\bf Question.} Is the FMSF of $\Z ^d$ connected for $d\geq 3$ ?
\newline {\bf Question.} Is it true that for every transitive
graph $G$ we have that with probability $1$ the number of
components is either $1$ or $\infty$?

\section {Ising and Potts Model, especially on trees}

Consider the problem of broadcasting on trees. Assume $T$ is a
rooted $b$-ary tree of depth $n$, assign the root a random value
from $\{1\, \ldots ,q\}$ for some fixed integer $q$. We assign
each vertex in the tree a value in the following manner. Let
$\epsilon> 0$, and for each child of the root copy the value of
the root with probability $1-\epsilon$, or, with probability
$\epsilon$ draw a uniform random value for it from $\{1\, \ldots
,q\}$. Continue recursively to assign values to all vertices of
the tree, including the leaves. We say {\em reconstruction} is
possible if there is some algorithm that reads the values of the
leaves and outputs a number from $\{1\, \ldots ,q\}$ such that the
probability of this number being the root value is greater than
$1/q+\delta$ for some $\delta
> 0$ not depending on $n$.

It is known (see \cite{MP}) that there exists $\epsilon _c(b,q)$
such that for any $\epsilon > \epsilon_c(b,q)$ reconstruction is
impossible, and for any $\epsilon < \epsilon_c(b,q,)$
reconstruction is possible. Furthermore,
$$1- 2\epsilon_c(2,b) = {1 \over \sqrt{b}} \, .$$

{\bf Question.} What is $\epsilon_c(q,b)$ for $q>2$? It is
conjectured that is satisfies
$$1-q\epsilon_c(q,b) = {1 \over \sqrt{b}} \, .$$

The conjecture arises because of the following. Assume that the
only information one receives is how many leaves are there of each
kind. In this model, reconstruction also exhibits a phase
transition (see \cite{MP}), denote this point by $\epsilon _{\rm
census}$, which satisfies
$$ 1- q\epsilon _{\rm census} = {1 \over \sqrt{b}} \, .$$


\begin{thebibliography}{99}

\bibitem{MP} Mossel E. and Peres Y. (2003), Information flows on
trees, {\em Ann. Appl. Probab.} {\bf 13} no. 3 817--844.

\end{thebibliography}







\end{document}