\documentclass{amsart} \usepackage{amsthm} \usepackage{amssymb} \usepackage{url} \usepackage[...]{youngtab} \usepackage{graphicx} \usepackage{enumitem} \newtheorem{thm}{Theorem}[section] \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{defn}[thm]{Definition} \newtheorem{rem}[thm]{Remark} \newtheorem{ex}[thm]{Exercise} \newtheorem{conj}[thm]{Conjecture} \newtheorem{quest}[thm]{Question} \def\Z{\mathbb{Z}} \def\R{\mathbb{R}} \def\F{\mathcal{F}} \def\Q{\mathcal{Q}} \def\P{\mathbb{P}} \newcommand{\prob}{\mbox{Pr}} \newcommand{\expect}{\mathbb{E}} \newcommand{\nCk}{\left( \! \! \! \begin{array}{c} #1 \\ #2 \end{array} \! \! \! \right)} \newcommand{\disp}{\displaystyle} \renewcommand{\baselinestretch}{1.25} \begin{document} \title{Lecture notes: Random graphs and percolation theory} \author{Matthew Kahle} \address{Department of Mathematics \\ The Ohio State University} \date{\today} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Introduction} These notes are based on a graduate course Random graphs and percolation theory'' at Ohio State University in Fall 2012. The notes were typed by several participants in the course. In particular, many thanks go to: Huseyin Acan, Charles Baker, Chris Kennedy, Jung Eun Kim, Yoora Kim, Greg Malen, Fatih Olmez, Kyle Parsons, Dan Poole, and Younghwan Son. Disclaimer: we have not had a chance to carefully edit all these notes yet, so please proceed with caution! \clearpage \section{(Wednesday, August 22)} This course will be about various types of random graphs. In today's class, we partly motivate this study with a discussion of the probabilistic method''. This method is essential in many areas of mathematics now, but Ramsey theory is an important classical one. The function $R(s,t)$ is defined to be the smallest number $N$ such that for every coloring of the edges of the complete graph $K_n$ with red and blue, there is either a red $K_s$ or a blue $K_t$ subgraph. For example $R(3,3)=6$. For large $s$ and $t$ there is little hope for an exact formula for $R(s,t)$, but we might at least hope to understand the asymptotics. An easy induction argument shows that $R(s,t) \le R(s-1,t) + R(s,t-1)$. Together with the fact that $R(s,1) = R(1,t) = 1$, this gives by induction that $$R(s,t) \le {s+t \choose s}.$$ \begin{ex}[easy] Show that this implies that $R(s,s) \le 4^s$. Better yet, show that $R(s,s) =O \left( 4^s / \sqrt{s} \right)$. \end{ex} \begin{ex} [open] Improve the base of the exponent $4$, or else show that it can not be improved. E.g. prove or disprove that $R(s,s) = O \left( 3.999^s \right)$. \end{ex} The best upper bound I know of is due to David Conlon \cite{Conlon}. \begin{thm} [Conlon, 2009] There exists a contain $c$ such that $$R(s+1,s+1) \le s^{- c \log s / \log \log s} {2s \choose s}.$$ \end{thm} For lower bounds we apply the probabilistic method. Taking a random coloring of the edges gives the following bound. \begin{thm} [Erd\H{o}s] If $${n \choose k} 2^{1 - {k \choose 2}} < 1$$ then $R(k,k) > n$. \end{thm} The proof is a simple union bound. \begin{ex}Show as a corollary that $$R(s,s) \ge {\sqrt{2}}^s$$ \end{ex} The proof is easy but the technique is still powerful. In fact the following is wide open. \begin{ex}[open] Give an explicit description of any sequence of graphs which gives an exponential lower bound on $R(s,s)$. \end{ex} This can be rephrased as follows. \begin{ex}[open] Give an explicit infinite sequence of graphs $\{ G_n \}_{n=1}^{\infty}$, so that $G_n$ has $n$ vertices and such that the largest clique and the largest independent set in $G_n$ are both of order $O( \log n)$. \end{ex} It seems strange that although asymptotically almost every graph according to the measure $G(n,1/2)$ has this property, \footnote{In the next lecture we will define the binomial random graph $G(n,p)$.} it is hard to exhibit any explicit examples. This is sometimes referred to as the problem of finding hay in a haystack. \begin{ex}[open] Improve the base of the exponent $\sqrt{2}$, or else show that it can not be improved. E.g. prove or disprove that $$R(s,s) = \Omega \left( 1.415^s \right).$$ \end{ex} \bigskip The main source for this lecture was Chapter 1 of Alon and Spencer's book \cite{Alon}. \clearpage \section{(Friday, August 24)} \begin{defn} For a natural number $n$ and $0\leq p\leq 1$, an Erd\H{o}s-R\'{e}nyi graph $G(n,p)$ is defined to be a graph on $n$ vertices where each pair of vertices is joined by an edge with probability $p$, with the edges chosen jointly and independently. \end{defn} Note that if $G$ is any particular graph on $n$ vertices, then the probability of obtaining $G$ is $p^{e_G}(1-p)^{{n\choose 2}-e_G}$. \begin{defn} For $0\leq m\leq {n\choose 2}$, the Erd\H{o}s-R\'{e}nyi graph $G(n,m)$ is a graph on $n$ vertices with $m$ edges, chosen among all ${{n\choose 2}\choose m}$ such graphs uniformly. \end{defn} Each definition has its advantages and disadvantages; one particular advantage of $G(n,p)$ is that all edges are chosen independently, so local phenomena are modeled more easily than in $G(n,m)$. Very roughly, $G(n,m)$ resembles $G(n,p)$ with $p=m/{n\choose 2}$. Conversely, $G(n,p)$ resembles $G(n,m)$ with $m=p\cdot{n\choose 2}$. We will use the following notation extensively. Let $f(n),g(n)$ be sequences of positive real numbers. \begin{itemize} \item $f=O(g)$ iff there exists a constant $M>0$ such that $f(n)\leq Mg(n)$ for all sufficiently large $n$; we also write $g=\Omega(f)$. \item $f=o(g)$ iff $\lim_{n\rightarrow\infty} f(n)/g(n)=0$; we also write $f\ll g$, $g\gg f$, or $g=\omega(f)$. \item $f=\Theta(g)$ iff $f=O(g)$ and $g=O(f)$; we also write $f\asymp g$. \item $f\sim g$ iff $\lim_{n\rightarrow\infty} f(n)/g(n)=1$. \end{itemize} If $\Q$ is any graph property (e.g. connected, contains a $K_3$, etc.), we say $G(n,p)$ has property $\Q$ a.a.s. (asymptotically almost surely) or w.h.p. (with high probability) if $\prob[G(n,p)\in \Q]\rightarrow 1$ as $n\rightarrow\infty$. For example, we can say the following about connectedness: \begin{enumerate} \item If $p\gg \frac{\log n}{n}$, then $G(n,p)$ is connected a.a.s. \item If $p\ll \frac{\log n}{n}$, then $G(n,p)$ is disconnected a.a.s. \item If $p\ll n^{-2}$, then $G(n,p)$ has no edges a.a.s. \end{enumerate} In the above statements, we have suppressed the implicit variation of $p$ with $n$; that is, we might more properly write $G(n,p(n))$. As another example, we will prove the following proposition as a special case of a more general theorem on subgraph containment later: \begin{prop} Let $Q$ be the set of graphs containing $K_4$ as a subgraph. Then $$\prob[G(n,p)\in \Q]\rightarrow\left\{ \begin{array}{cl} 0 & \mbox{ if } p\ll n^{-2/3} \\ f(c)&\mbox{ if } p=cn^{-2/3} \\ 1 & \mbox{ if } p\gg n^{-2/3}, \end{array}\right.$$ where $f(c)$ is a function independent of $p$. \end{prop} We are often interested in graph properties $\Q$ that are monotone in the following sense: let $G$ and $H$ be graphs on $n$ vertices such that $G\subseteq H$. Then $\Q$ is said to be \emph{monotone increasing} if $G\in \Q$ implies $H\in \Q$ (e.g.\ connected, contains $K_m$, contains a cycle). Similarly, $\Q$ is \emph{monotone decreasing} if $H\in \Q$ implies $G\in \Q$ (e.g.\ $k$-colorable, maximum degree at most 5). \begin{defn} Let $Q$ be a monotone increasing graph property and $\hat{p}$ a sequence of probabilities. Then $\hat{p}$ is a threshold for $\Q$ if $$\prob[G(n,p)\in \Q]\rightarrow\left\{ \begin{array}{cl} 0 & \mbox{ if } p\ll \hat{p} \\ 1 & \mbox{ if } p\gg \hat{p}, \end{array}\right.$$ \end{defn} \begin{thm} Every nontrivial monotone graph property has a threshold. \end{thm} In the context of the above statement, a property is trivial'' if it holds for every graph or no graph, and nontrivial otherwise. Now, fix a nontrivial monotone increasing property $\Q$. To prove the theorem, the following lemma is useful: \begin{lem} If $p_1\leq p_2$, then $\prob[G(n,p_1)\in \Q]\leq \prob[G(n,p_2)\in \Q]$. \end{lem} \begin{proof} The proof uses the useful notion of 2-round sprinkling'': if $G(n,p)$ and $G(n,q)$ are chosen independently on $[n]$, then their union is $G(n,p+q-pq)$ by inclusion-exclusion. Setting $p=p_1$ and $q=\frac{p_2-p_1}{1-p_1}$, view $G(n,p_2)$ as the union of $G(n,p)$ and $G(n,q)$. Then $G(n,p_1)\subseteq G(n,p_2)$, and the conclusion follows since $\Q$ is increasing. \end{proof} \begin{defn} Let $a\in (0,1)$. Then $p(a)\in (0,1)$ is defined to be the number such that $\prob[G(n,p(a))\in \Q]=a$. \end{defn} Note that since $\prob[G(n,p)\in \Q]$ is simply a (potentially very complicated) polynomial in $p$, $p(a)$ exists and is unique, and indeed is continuous and increasing as a function of $a$. Using this definition, we have the following fact, to be proved next time: \begin{prop} Let $\hat{p}$ be a sequence of probabilities. Then $\hat{p}$ is a threshold for $\Q$ if and only if $p(a,n)\asymp \hat{p}(n)$ for all $a\in (0,1)$. \end{prop} \clearpage \section{(Monday, August 27)} We began by rehashing some definitions from last time. \begin{defn} We recall the symbols defining how sequences $p(n)$, $q(n)$ of strictly positive real numbers relate. \begin{itemize} \item $f = O(g)$ if and only if $\exists c > 0, N \in \mathbb{N}$ such that $n > N$ implies $f(n) \leq cg(n)$. \item $p(n) \ll q(n)$ if and only if $p(n) = o(q(n))$ if and only if $\disp \lim_{n \to \infty} \frac{p(n)}{q(n)} = 0$. \item $p(n) \gg q(n)$ if and only if $p(n) = \omega(q(n))$ if and only if $\disp \lim_{n \to \infty} \frac{p(n)}{q(n)} = \infty$. \item $p(n) \asymp q(n)$ if and only if $p(n) = \Theta(q(n))$ if and only if $p(n) = O(q(n))$ and $q(n) = O(p(n))$; i.e., there are constants $0 < c < C$, $N \in \mathbb{N}$ such that $n > N$ implies $cq(n) \leq p(n) \leq C q(n)$. \end{itemize} \end{defn} \begin{defn} If $Q$ is a non-trivial, monotone, increasing graph property, then $\hat{p} = \hat{p}(n)$ is said to be a \textit{threshold} for $Q$ if, as $n \to \infty$, $$\prob [G(n, p(n)) \in Q] \to \left\lbrace \begin{array}{r l} 1, & p \gg \hat{p} \\ 0, & p \ll \hat{p} \end{array} \right.$$ \end{defn} \begin{defn} $p(a) = p(a; n)$ is defined to be the unique number $q$ in $(0, 1)$ such that $\prob [G(n, q) \in Q] = a$. (The well-defined-ness of this number more or less follows from the intermediate value theorem, and the probablility a polynomial in $p$: For fixed $n$, $p \mapsto \prob [G(n, p) \in Q$ is continuous and strictly increasing.) \end{defn} \subsection{Every monotone graph property has a threshold} We now wish to show that every increasing (nontrivial) graph property has a threshold. To start, we now clarify the proof of the fact given at the end of class on Friday, Aug. 24th, 2012.\footnote{There was no real error in the proof from last time; only one observation fixes the proof.} \begin{lem} $\hat{p}$ is a threshold if and only if $\hat{p} \asymp p(a)$ for any fixed $a$, $0 < a < 1$. \end{lem} \textit{Proof.} (only if''): Assume $\hat{p}$ is a threshold. If $0 < a < 1$ but $\hat{p} \not\asymp p(a)$, then there exists a subsequence $n_1, n_2, \dotsc$ along which $\disp \frac{p(a)}{\hat{p}} \to 0$ or $\disp \frac{p(a)}{\hat{p}} \to \infty$. In the first case, as $k \to \infty$, $\disp \frac{p(a; n_k)}{\hat{p}(n_k)} \to 0$. Extend the subsequence $p(a; n_k)$ to any full sequence $q(n)$ such that $q(n_k) = p(a; n_k)$ and that $\disp \frac{q(n)}{\hat{p}(n)} \to 0$ as $n \to \infty$.\footnote{For example, for any $n \neq n_k$ for some $k$, just define $q(n) = 2^{-n}\hat{p}(n)$.} Therefore, by the definition of a threshold, $$\prob [G(n, q(n)) \in Q] \to 0 \text{ as } n \to \infty,$$ and hence, since subsequential limits equal the full limits, $$\prob [G(n_k, p(a; n_k) \in Q] \to 0 \text{ as } n \to \infty.$$ Yet by definition of $p(a)$, $$\prob [G(n_k, p(a; n_k) \in Q] = a \forall k \in \mathbb{N}.$$ Contradiction. The second possibility yields a similar contradiction. Therefore, we must have $\hat{p} \asymp p(a)$ for all $a$, $0 < a < 1$. (if''): Assume $\hat{p}$ is not a threshold. Then there exists a sequence $p = p(n)$ such that $\disp \frac{p}{\hat{p}} \to 0$ and $\liminf \prob [G(n, p) \in Q] \gneqq 0$, or $p$ exists such that $\disp \frac{p}{\hat{p}} \to \infty$ and $\limsup \prob [G(n, p) \in Q] \lneqq 0$. In the first case, there exists $a > 0$ and a subsequence $n_1 < n_2 < \dotsb$ along which $\prob [G(n, p) \in Q] \geq a$, so that by definition of $p(a)$, $p(a; n_k) \leq p(n_k)$.\footnote{This depends in the monotonicity of $\prob [G(n, p) \in Q]$ on $p$, proved last time.} Thus, since $p \ll \hat{p}$, for all $c > 0$, there exists $N \in \mathbb{N}$ such that $n > N$ implies $p(n) < c \hat{p}$. Hence, for $k > N$, $n_k > N$, so that $p(a; n_k) < c \hat{p}(n_k)$. Therefore, $\hat{p}$ is not $O(p(a))$, so $\hat{p} \not\asymp p(a)$. The second case proceeds similarly. \rightline{$\square$} \begin{thm} Every nontrivial monotone increasing property has a threshold. \end{thm} The proof method relies on an extension of the 2-fold sprinkling process began last time to an $m$-fold sprinking process.\\ \noindent{\bf Proof. } Fix $\epsilon$, $0 < \epsilon < \frac{1}{2}$. Choose $m = m(\epsilon)$ large enough that $(1 - \epsilon)^m < \epsilon$. Fix $n$ temporarily, and take $m$ independent copies of $G(n, p(\epsilon))$, named $G_1, \dotsc, G_m$. By $m$-fold sprinkling and the inclusion-exclusion principle, their union (literally superimposing the graphs, and identifying common edges) is a $G(n, p^{\prime})$, where $p^{\prime} = 1 - (1 - p(\epsilon))^m \leq m p(\epsilon)$. Therefore, we have that $$\prob [G_1 \cup \dotsc \cup G_m \in Q] = \prob [G(n, p^{\prime}) \in Q] \leq \prob [G(n, m p(\epsilon)) \in Q].$$ Yet by the independence of the choices, and since $\prob [G_i \in Q] = \prob [G(n, p(\epsilon)) \in Q] = \epsilon$, we have that $$\prob [G_1 \cup \dotsc \cup G_m \not\in Q] = \prod_{i = 1}^m \prob [G_i \not\in Q] = (1 - \epsilon)^m < \epsilon,$$ and hence $$\prob [G(n, m p(\epsilon)) \in Q] \geq 1 - \prob [G_1 \cup \dotsc \cup G_m \not\in Q] \geq 1 - \epsilon.$$ Therefore, by definition of $p(a)$, $p(1-\epsilon) \leq m p(\epsilon)$, since $p \to \prob [G(n, p) \in Q]$ is increasing in $p$ by $Q$ an increasing graph property. By the monotonicity of $p(a)$, however, we have $$p(\epsilon) \leq p \left( \frac{1}{2} \right) \leq p(1 - \epsilon) \leq m p(\epsilon).$$ Note also that $m$ depends on $\epsilon$, and not on $n$. Therefore, the same inequalities hold for every $m$, and hence $$p(\epsilon) \asymp p \left( \frac{1}{2} \right) \asymp p(1 - \epsilon),$$ for every $0 < \epsilon < \frac{1}{2}$. Therefore, by the Lemma, $\hat{p} = p \left( \frac{1}{2}\right)$ is a threshold. \newline \rightline{$\blacksquare$} \smallskip \subsection{Sharp Thresholds} We next discussed various definitions of a stricter kind of threshold. \begin{defn} $\hat{p}$ is said to be a sharp threshold for $Q$ if $$\prob [G(n, p) \in Q] \to \left\lbrace \begin{array}{r l} 1, & p \geq (1 + \eta) \hat{p} \text{ for some } \eta > 0\\ 0, & p \leq (1 - \eta) \hat{p} \text{ for some } \eta > 0 \end{array} \right.$$ \end{defn} A (non-sharp) threshold, by contrast, requires that $p$ is eventually greater than \textit{any} constant multiple of $\hat{p}$ before requiring that the limit goes to 1. Therefore, sharp thresholds are indeed thresholds. Another characterization of sharp thresholds comes from the concept of the widths of the windows of change.'' \begin{defn} Fix $0 < \epsilon < \frac{1}{2}$. Then define the $2(1-\epsilon)$-width $\delta = \delta(\epsilon) = p(1 - \epsilon) - p(\epsilon)$. \end{defn} Small widths imply that a relatively small change in the input edge probability controls whether or not the output probability of a graph having property $Q$ is likely or unlikely. In fact, we have the following fact. \begin{lem} $\hat{p}$ is a sharp threshold if and only if for all $\epsilon$, $0 < \epsilon < \frac{1}{2}$, $\delta = \delta(\epsilon) = o \left( \hat{p} \right)$. \end{lem} \noindent{\it Proof. } (only if'') Suppose $\hat{p}$ is a threshold. Then we claim that for all $a$, $0 < a < 1$, that for all $\eta$, $0 < \eta <1$, there exists $N = N(a, \eta)$ such that $n > N$ implies $(1 - \eta)\hat{p} < p(a) < (1 + \eta)\hat{p}$. Suppose, by way of contradiction, that the above does not hold. Then for some $a$, for some $\eta > 0$, either $p(a) \leq (1 - \eta) \hat{p}$ infinitely often or $(1 + \eta) \hat{p} \leq p(a)$ infinitely often. In the first case, we have an infinite subsequence $n_1 < n_2 < \dotsb$ such that $p(a; n_k) \leq (1 - \eta) \hat{p}(n_k)$. Re-extend $p(a; n_k)$ to a sequence $q(n)$ such that $q(n_k) = p(a; n_k)$ and that $q(n) \leq (1 - \eta) \hat{p}(n)$ for all $n$.\footnote{For example, for any $n \neq n_k$ for some $k$, just define $q(n) = (1 - \eta)\hat{p}(n)$.} Then $q(n) \leq (1 - \eta) \hat{p}(n)$, so by the fact that $\hat{p}$ is a threshold, we have that $\prob (G(n, q) \in Q) \to 0$ as $n \to \infty$; in particular, $\prob [G(n_k, p(a; n_k) \in Q ] = \prob [G(n_k, q(n_k)) \in Q] \to 0$ as $k \to \infty$. Yet $\prob [G(n_k, p(a; n_k) \in Q] = a$ by definition, for all $k$. Hence, $a \to 0$ as $k \to \infty$. Contradiction. The second possibility ($(1 + \eta) \hat{p} \leq p(a)$ infinitely often) also causes a contradiction in the same way. Therefore, the claim holds. From the claim, and from monotonicity of $p(a)$, it follows that for any $a$, $b$, $0 < a < b < 1$, we have that for $n > \max \left\lbrace N(a, \eta), N(b, \eta) \right\rbrace$, $$0 < p(b) - p(a) < [(1 + \eta) - (1 - \eta)] \hat{p} = 2 \eta \hat{p}.$$ Since $\eta$ is arbitrary, it is clear that $p(b) - p(a) = o(\hat{p})$. Fixing $0 < \epsilon < \frac{1}{2}$, and setting $a = \epsilon$ and $b = 1 - \epsilon$, we have that $\delta(\epsilon) = p(1 - \epsilon) - p(\epsilon) = o(\hat{p})$. This works for all such $\epsilon$. (if'') Exercise. \newline \rightline{$\square$} \smallskip Another basic fact in this setting shows that if sharp thresholds exist, then $p\left(\frac{1}{2} \right)$ reprises its role as the universal threshold. \begin{lem} \begin{enumerate} \item If a sharp threshold for a nontrivial, increasing property $Q$ exists, then for all $\epsilon$, $0 < \epsilon < 1$, \begin{equation} \frac{p(\epsilon)}{p(\frac{1}{2})} \to 1 \text{ as } n \to \infty. \label{eqn:epsilon12Ratio} \end{equation} \item If for a given nontrivial, increasing property $Q$ the limit in \ref{eqn:epsilon12Ratio} holds for all $\epsilon,$ $0 < \epsilon < 1$, then $\displaystyle p\left( \frac{1}{2}\right)$ is a sharp threshold. \end{enumerate} In particular, if any sharp threshold exists, $\displaystyle p\left( \frac{1}{2}\right)$ is also a sharp threshold. \end{lem} \textit{Proof.} Suppose $\hat{p}$ is a sharp threshold for a nontrivial, increasing property $Q$. First, take $\epsilon$ with $0 < \epsilon < \frac{1}{2}$. Then by the previous lemma, for any $c > 0$, for $n > \max \left\lbrace N(\epsilon, c), N(1 - \epsilon, c \right\rbrace$, $$p \left(\frac{1}{2} \right) - p(\epsilon) \leq p(1 - \epsilon) - p(\epsilon) \leq c \hat{p}.$$ Dividing both sides by $\displaystyle p\left( \frac{1}{2}\right)$ and moving some terms around, we get that $$1 - c \frac{\hat{p}(n)}{p\left( \frac{1}{2}\right)} \leq \frac{p(\epsilon)}{p\left( \frac{1}{2}\right)}.$$ Yet since $\hat{p}$ is a sharp threshold, it is a regular threshold, and hence $\hat{p} \asymp p\left( \frac{1}{2}\right)$. In particular, then, there exists a constant $k$ such that $\frac{\hat{p}(n)}{p\left( \frac{1}{2}\right)} \leq k$. Therefore, for large enough $n$, $$1 - ck \leq 1 - c \frac{\hat{p}(n)}{p\left( \frac{1}{2}\right)} \leq \frac{p(\epsilon)}{p\left( \frac{1}{2}\right)}.$$ Since $k$ is fixed and $c$ is arbitrary, this shows that $\displaystyle \liminf \frac{p(\epsilon)}{p\left( \frac{1}{2}\right)} \geq 1$. Yet $\epsilon < \frac{1}{2}$, so $p(\epsilon) \leq p\left( \frac{1}{2}\right)$ and hence $\displaystyle \limsup \frac{p(\epsilon)}{p\left( \frac{1}{2}\right)} \leq 1$. The case $\frac{1}{2} < \epsilon < 1$ is similar, and of course the case $\epsilon = \frac{1}{2}$ is trivial. Now, suppose that $Q$ is a nontrivial, increasing graph property such that for all $\epsilon,$ $0 < \epsilon < 1$, \ref{eqn:epsilon12Ratio} holds. Therefore, for all $C > 1$, there is $M = M(\epsilon, C)$ such that $n > M$ implies $$\frac{1}{C} p\left( \frac{1}{2}\right) < p(\epsilon) < C p\left( \frac{1}{2}\right).$$ Suppose that for some $\eta > 0$, $q(n) \geq (1 + \eta) p\left( \frac{1}{2}\right)$ for all $n$. Then for $C := 1 + \eta$, and fixing $\epsilon \in (0, 1)$, $n > M = M(\epsilon, C)$, the above gives $$q(n) \geq (1 + \eta) p\left( \frac{1}{2}\right) = C p\left( \frac{1}{2}\right) > p(\epsilon),$$ and hence, by the monotonicity of $\prob [ G(n, p) \in Q]$ in $p$ proved last time, for $n > M$, $$\prob [ G(n, q) \in Q] \geq \prob [G(n, p(\epsilon) \in Q] = \epsilon.$$ Since this works for all $\epsilon \in (0, 1)$, we have that $\prob [G (n, q) \in Q] \to 1$ as $n \to \infty$. Similarly, if for some $\eta > 0$, $q(n) \leq (1 - \eta) p\left( \frac{1}{2}\right)$, then $\prob [G (n, q) \in Q] \to 0$ as $n \to \infty$.\\ \rightline{$\square$} \subsection{An example} We now apply our work on thresholds to a common choice of graph property. We begin today and continue on Wednesday, Aug. 29th. \begin{ex} One nontrivial, increasing graph property is the existence of subgraphs isomorphic to complete graphs of a specified size. To set notation, let a graph $G$ be in $Q_m$ if and only if $G$ contains a subgraph isomorphic to $K_m$, the complete graph on $m$ vertices. Let $N_m$ be the random variable counting the number of $K_m$'s in a given graph; then $G \in Q_m$ if and only if $N_m(G) \gneqq 0$. Our first claim is that for fixed $n$, and taking expectation over the space of graphs $G(n, p)$, $\displaystyle \expect [N_m] = \nCk{n}{m} p^{\nCk{m}{2}}$. Note that for fixed $n$, there are only finitely many distinct $m$-tuples of vertices with which to create a $K_m$. Therefore, if $i \in \nCk{[n]}{m}$ is an $m$-tuple of vertices of $G(n)$, then let the set $A_i$ be the subset of graphs in $G(n, p)$ in which the $m$-tuple of vertices $i$ creates a $K_m$. Since indiviudal edges exist with probability $p$, and since $\nCk{m}{2}$ edges are needed to form $K_m$, we have for each $i$ that $\displaystyle \prob(A_i) = p^{\nCk{m}{2}}$. For notational convenience, let $Y_i = \mathbb{1}_{A_i}$ be the indicator function of $A_i$; then $\displaystyle \expect{Y_i} = p^{\nCk{m}{2}}$. Further, since $N_m$ is the total number of $K_m$'s, and each possible $K_m$ is indexed by some $i \in \nCk{m}{2}$, we have that $N_m$ is merely the sum of the indicator variables $Y_i$: $\displaystyle N_m = \sum_{i \in \nCk{[n]}{m}} Y_i$. Since expectation is linear, the expectation operator passes through the finite sum indicated, so we have that \begin{eqnarray*} \expect (N_m) & = & \expect \left[ \sum_{i \in \nCk{[n]}{m}} Y_i \right]\\ & = & \sum_{i \in \nCk{[n]}{m}} \expect (Y_i)\\ & = & \sum_{i \in \nCk{[n]}{m}} p^{\nCk{m}{2}} = \nCk{n}{m} p^{\nCk{m}{2}} \end{eqnarray*} Thus, the claim is proved. \end{ex} \begin{rem} The above work demonstrated that the summability of expectations happens despite the lack of independence of some pairs of subsets; for example, if $m = 4$ and $n \geq 5$, the existence of $K_4$'s on the vertex sets $\left\lbrace 1, 2, 3, 4 \right\rbrace$ and $\left\lbrace 1, 2, 3, 5 \right\rbrace$ are certainly not independent. We resolve this issue in two ways. First, we note that independence of random variables $X, Y$ implies that the expectation of their \textit{product} is 0: $\expect (XY) = 0$. Thus, independence or dependence of random variables does not matter until we start studying variances and the second-moment method. Second, we note that if $m$ is fixed and $n$ is large, then there are many pairwise independent events: e.g., in the $m = 4$ example above, the existence of $K_4$'s on the vertex sets $\left\lbrace 1, 2, 3, 4\right\rbrace$, $\left\lbrace 5, 6, 7, 8 \right\rbrace$, $\left\lbrace 9, 10, 11, 12\right\rbrace$, are independent. The heuristic is that if $n$ is large relative to $m$, then most'' pairs are independent. \end{rem} \begin{ex} Continuing the example above, we also note that by Stirling's formula, if $m$ is fixed, then $\displaystyle \expect [N_m] =\nCk{n}{m} p^{\nCk{m}{2}} \asymp n^m p^{\nCk{m}{2}}$. Therefore, if $p(n) = n^{\frac{-2}{(m-1)}}$, then by the fact that $\displaystyle \nCk{m}{2} = \frac{m(m-1)}{2}$, we have that $n^m p^{\nCk{m}{2}} = n^{m - m} = 1$. Therefore, it is simple to check that if $p \gg n^{\frac{-2}{m-1} }$, then $\expect [N_m] \to \infty$, and if $p \ll n^{\frac{-2}{(m-1)} }$, then $\expect [N_m] \to 0$. From this, we can make the conjecture that a threshold of the graph property $Q_m$ is in fact $n^{\frac{-2}{(m - 1)}}$. In fact, we can show the following. \begin{thm} \begin{enumerate} \item If $p \ll n^{\frac{-2}{(m-1)} }$, then $\prob[ G(n, p) \supseteq K_m] \to 0$ as $n \to \infty$.\\ \item If $p \gg n^{\frac{-2}{(m-1)} }$, then $\prob[ G(n, p) \supseteq K_m] \to 1$ as $n \to \infty$.\\ \item If $p = cn^{\frac{-2}{(m-1)} }$, then $\prob[ G(n, p) \supseteq K_m] \to f(c)$ as $n \to \infty$, where $0 < f(c) < 1$ is a constant depending on $c$ alone, not $n$ or $m$.\\ \end{enumerate} \end{thm} This result demonstrates that $n^{\frac{-2}{(m-1)}}$ is in fact a threshold, but not a sharp threshold (by specifics of the constant $f(c)$, $c$ can be greater than $1$ but $\prob [G(n, p) \supseteq K_m] \not\to 1$). \end{ex} For an example of a sharp threshold, we consider the property of connectedness. \begin{thm} \begin{enumerate} \item If $\displaystyle p \geq \frac{\log(n) + \omega(1)}{n}$, then $\prob[ G(n, p) \text{ is connected} ] \to 1$. \item If $\displaystyle p \leq \frac{\log(n) - \omega(1)}{n}$, then $\prob[ G(n, p) \text{ is connected} ] \to 0$. \item If $\displaystyle p = \frac{\log(n) + c}{n}$, then $\displaystyle \prob[ G(n, p) \text{ is connected} ] \to e^{-e^{-c}}$. \end{enumerate} \end{thm} Recall that $q = \omega(1)$ means that some function is diverging, however slowly, to infinity; in particular, $\eta \log(n)$ is a reasonable choice (showing that we have a sharp threshold), but $\log( \log( \log( \dotsb \log(n) \dotsb ))$ also works. The width of this window is slightly larger than $\frac{2}{n}$, since you have to allow slow-growing functions. (Our discussion of thresholds followed Section 1.5 of \cite{JLR}.) \clearpage \section{Wednesday, August 29} We will use the second moment method to prove that the threshold function for $G(n,p)$ includes $K_4$ is $p=n^{-2/3}$. \begin{defn} $Var[X]:=\expect [(X-\expect[X])^2] = \expect[X^2-2X\expect[X]+\expect[X]^2]= \expect[X^2]-\expect[X]^2.$ \end{defn} \noindent \textbf{Notation} $\sigma^2= Var[X]$, where $\sigma$ is the standard varaiation. \bigskip \begin{thm}[Chebyshev's Inequality] Let $\mu:=\expect[X]$. Then, $\prob[|X-\mu| \ge \lambda\sigma] \le \frac{1}{\lambda^2}$ \end{thm} \begin{proof} We have $\sigma^2= Var[X]= \expect[(X-\mu)^2] \ge \lambda^2\sigma^2 \prob[|X-\mu| \ge \lambda\sigma].$ Dividing by $\sigma^2\lambda^2$ we get $\frac{1}{\lambda^2}\ge \prob[|X-\mu|\ge \lambda\sigma].$ \end{proof} Suppose $X= X_1+\cdots+X_m$. Then, $Var[X]= \sum_{i=1}^{m} Var[X_i]+ \sum_{i\neq j}Cov[X_i,X_j]$ where $Cov[X_i,X_j]:= \expect[X_iX_j] -\expect[X_i]\expect[X_j].$ If $X_i$ and $X_j$ are independent r.v.'s, then $Cov[X_i,X_j]=0$. The converse of this statement is not true. For a counterexample, let $Y$ be the uniform random varibable on the interval $[-1,1]$ and let $Z=Y^2$. Clearly $Y$ and $Z$ are not independent but $Cov[Y,Z]=0$. If $X=X_1+\cdots+X_m$ where each $X_i$ is a Bernoulli r.v. with $\prob[X_i=1]=p_i, \quad \prob[X_i=0]=1-p_i,$ then $Var[X]=p_i(1-p_i)\le p_i$. SO, $Var[X] \le \expect[X] +\sum_{i\ne j} Cov[X_i,X_j].$ In general, if $X$ is a non-negative integer r.v., then $\prob[X>0]= \sum_{i\ge 1} \prob[X=i] \le \sum_{i\ge 1} i\prob[X+1] =\expect[X].$ This is a special case of the following theorem. \begin{thm}[Markov's Inequality] $\prob[X\ge a] \le \frac{\expect[X]}{a}$ for any non-negative r.v. $X$. \end{thm} In particular, if $X_n$ is a sequence of non-negative integer r.v.'s such that $\expect[X_n]\to 0$, then $X_n=0$ a.a.s. In other words, $\prob[X_n=0]\to 1 \textrm{ as } n\to \infty.$ What if $\expect[X_n]\to \infty$? Is it true that $X_n>0$ a.a.s.? \textbf{Example} Let $X_n$ be a sequence of r.v.'s such that $X_n = \begin{cases} e^n & \textrm{ with probability } \frac{1}{n} \\ 0 & \textrm{ with probability } 1-\frac{1}{n} \end{cases}$ Then, the expected value $\expect[X_n]=e^n/n \to \infty$ but $\prob[X_n>0]=1/n \to 0$. \begin{thm} Let $X$ be a non-negative integer valued r.v. Then, $\prob[X=0]\le \frac{Var[X]}{\expect[X]^2}.$ \end{thm} \begin{proof} Set $\lambda= \mu/\sigma$. Then, $\prob[X=0] \le \prob[|X-\mu|\ge \mu] = \prob[|X-\mu|\ge \lambda\sigma] \le \frac{1}{\lambda^2}= \frac{\sigma^2}{\mu^2}.$ \end{proof} \begin{cor} If $\expect[X]\to \infty$ and $Var[X]= o\left( \expect[X]^2\right)$, then $X>0$ a.a.s. \qed \end{cor} the same proof shows that $\prob[|X-\mu|\ge \epsilon\mu] \le \frac{Var[X]}{\epsilon^2\expect[X]^2}.$ So if $\expect[X] \to \infty$ and $Var[X]=o\left( \expect[X]^2\right)$, then $X\sim \expect[X]$ a.a.s. In other words, for any fixed $\epsilon >0$, $(1-\epsilon)\expect[X] \le X \le (1+\epsilon)\expect[X]$ with probability approaching 1 as $n \to \infty$. Now set $X=X_1+\cdots+X_m$ where $X_i$ is the indicator random variable for the event $A_i$. Set $\Delta = \sum_{i\sim j} \prob[A_i \textrm{ and } A_j]$ where $i\sim j$ means that $i\ne j$ and $A_i, A_j$ are not independent. In particular we have $Cov[X_i,X_j]= \expect[X_iX_j]-\expect[X_i][X_j] \le \expect[X_iX_j]= \prob[A_i \textrm{ and } A_j],$ so $Var[X]\le \expect[X]+\Delta$. \begin{cor} If $\expect[X]\to \infty$ and $\Delta= o\left( \expect[X]^2\right)$, then $X>0$ a.a.s. (Actually $X\sim \expect[X]$ a.a.s). \end{cor} \begin{thm} $n^{-2/3}$ is a threshold for $G(n,p)\supset K_4$. \end{thm} \begin{proof} Let $X=X_n$ be the number of $K_4$'s in $G(n,p)$. Previously we have seen that $\expect[X_n]= {n \choose 4}p^6 \asymp n^4p^6$. (1) If $p \ll n^{-2/3}$, then $\expect[X]\to 0$, so $X=0$ a.a.s.\\ (2) If $p \gg n^{-2/3}$ then $\expect[X]\to \infty$. To apply second moment method we need to compute $\Delta$. For $i \in {[n] \choose 4}$, let $A_i$ be the event that i spans a clique". Then, $\prob[A_i]=p^6$ The events $A_i$ and $A_j$ are not independent iff $|i\cap j|=2 \textrm{ or } 3$. Let $\Delta=\Delta_2+\Delta_3$ where $\Delta_2$ is the contribution of the pairs $(i,j)$ with $|i \cap j|=2$ and $\Delta_3$ is the contribution of the pairs $(i,j)$ with $|i \cap j|=3$. Then $\Delta_2 \asymp n^6p^{11}, \quad \Delta_3 \asymp n^5p^9.$ On the other hand, $\expect[X]^2 \asymp n^8p^{12} .$ We conclude the proof by noting that, $\frac{\Delta_2}{\expect[X]^2} \asymp \frac{n^6p^{11}}{n^8p^{12}} =\frac{1}{n^2p} \to 0,$ and $\frac{\Delta_3}{\expect[X]^2} \asymp \frac{n^5p^{9}}{n^8p^{12}} =\frac{1}{n^3p^3} \to 0$ as $n \to \infty$. \end{proof} \begin{ex} What is a threshold for $G(n,p)$ contains $K_m$ for fixed $m$? \end{ex} \begin{ex} Is it always true that threshold for contains $H$" is $n^{-v_H/e_H}$ for any fixed graph $H$? \end{ex} \clearpage \section{Friday, August 31} \begin{quest} Is $n^{-v_H/e_H}$ always a threshold for the property containment of $H$ in $G(n,p)$ as a subgraph, i.e. $G(n,p)\supseteq H$? \end{quest} The answer is no. Note that when $H=K_4$, it is shown in previous lectures that $n^{-4/6}=n^{-2/3}$ is a threshold. Consider $H=K_4\cup \{\text{extra edge}\}$. Is $n^{-5/7}$ a threshold? If $p\ll n^{-5/7}$, then $\expect[X_H]\to 0$ and hence $X_H=0$ a.a.s. If $p\gg n^{-5/7}$, $p$ can still be much less than the threshold for containment of a $K_4$, since $n^{-2/3}\gg n^{-5/7}$. So if $p\gg n^{-5/7}$, it may even be that $X_{K_4}=0$ a.a.s. (eg. $p=n^{-20/29}$.) Therefore $n^{-5/7}$ is not the threshold for containment of $H$. \begin{defn} $p(H)$ is defined to be $e_H/v_H$ and called the \emph{density of $H$}.\\ $H$ is said to be \emph{balanced} if $p(H')\leq p(H)$ for every subgraph of $H'\subseteq H$. \end{defn} \begin{prop} Threshold of containment of $H$ is $n^{-v_H/e_H}$ $\iff$ $H$ is balanced. \end{prop} \begin{proof} [Following chapter 4 of \cite{Alon}.] $\implies$: Suppose $n^{-v_H/e_H}$ is a threshold for containment of $H$ and assume to the contrary that $H$ is not balanced. Then there exists a subgraph $H'$ with $p(H')=\frac{e_{H'}}{v_{H'}} > \frac{e_H}{v_H} = p(H)$. Choose $\alpha$ such that $p(H')<\alpha0 \text{ and } X\sim \expect(X) \text{ a.a.s. }$$Define X_1,X_2,\ldots,X_m to be \emph{symmetric} random variables when there exists a measure preserving automorphism of underlying probability space taking X_i to X_j for every i,j.$$\Delta = \sum_{i \sim j}\prob(A_i \cap A_j) = \sum_i \prob(A_i)\sum_{j\sim i} \prob(A_j|A_i).$$Notice that when X_1,X_2,\ldots,X_m are symmetric, \sum_{j\sim i} \prob(A_j|A_i) doesn't depend on i, so call it \Delta^*. Then \Delta=\Delta^* \cdot \expect(X), which impies the following corollary: \begin{cor} Let X_1,X_2,\ldots,X_m be symmetric indicator random variables of A_i's and X=\sum_{i=1}^m X_i. Then$$\expect(X)\to \infty \text{ and } \Delta^*=o(\expect(X)) \implies X>0 \text{ and } X\sim \expect(X) \text{ a.a.s. }$$\end{cor} Now we are ready to prove the other direction. For each V-set S\in {[n] \choose V}, let A_S be the event that G|_S contains H-subgraph and X_S=1_{A_S}. Note that p^v\leq \prob(A_S)\leq v! p^v. Now set X=\sum_{S\in {[n] \choose V}} X_S. Then X>0 if and only if there exists at least one H-subgraphs. Note that X doesn't give the exact count of H-subgraphs.$$\expect (X) = \sum \expect (X_S) = {n \choose v} \prob(A_S) = n^v p^e.$$So if p\ll n^{-v/e}, then X=0 a.a.s. Suppose p\gg n^{-v/e}. Let's compute \Delta^*=\sum_{T\sim S}\prob (A_T|A_S). Notice that here T\sim S also means that T\not= S and S,T share a common edge. Fix S.$$\Delta^*=\sum_{i=2}^{v-1}\sum_{|S\cap T|=i}\prob(A_T|A_S).$$For each i, there are O(n^{v-i}) choices for T. Fix S,T with |T\cap S|=i. Let's compute \prob(A_T|A_S). There are O(1) copies of H on T. Each has at least i\frac{e}{v} edges on vertices of S, since H is balanced. This leaves at least e-i\frac{e}{v} edges outside of S. Then$$\Delta^* = \sum_{i=2}^{v-1} O(n^{v-1}p^{e-i\frac{e}{v}})=\sum_{i=2}^{v-1} O((n^vp^e)^{1-\frac{i}{v}})=\sum_{i=2}^{v-1}o(n^vp^e).$$Corollary applies. X>0 a.a.s. \end{proof} \begin{thm} H is said to be strictly balanced if p(H')0 a.a.s. \end{thm} \clearpage \section{(Wednesday, September 5)} Let G=K_3 and p=\frac{c}{n} for c \in \left(0,\infty \right) a constant. We seek the probability that there exists any G subgraph of G(n,p). If we let X_G be the random variable counting the number of G subgraphs of G(n,p) we'll see that \prob\left[ X_G = m\right] \to f(m). \begin{defn} z \in P_0 (\mu) means z is chosen according to a Poisson distribution with mean \mu. That is \prob[z=t]=\frac{\mu^t e^{-\mu}}{t!} \end{defn} Note that$$\displaystyle\sum\limits_{t=0}^\infty \frac{\mu^t}{t!}e^{-\mu} = e^{-\mu}\displaystyle\sum\limits_{t=0}^\infty \frac{\mu^t}{t!} = e^{-\mu}e^\mu = 1$$so P_0(\mu) is in fact a probability distribution on the nonnegative integers. Also note that$$\displaystyle\sum\limits_{t=0}^\infty t \prob[z=t] = \displaystyle\sum\limits_{t=1}^\infty \frac{\mu^t}{(t-1)!}e^{-\mu} = \mu e^{-\mu}\displaystyle\sum\limits_{t=0}^\infty \frac{\mu^t}{t!} = \mu e^{-\mu}e^\mu = \mu$$so the mean of P_0(\mu) is \mu as desired. Now again letting G=K_3, p=\frac{c}{n} and X_G be the number of K_3 subgraphs of G(n,p) we have that \expect[X_G] = \binom{n}{3}p^3 which tends to \frac{c^3}{6} as n\to\infty. In fact X_G \overset{D}{\longrightarrow} P_0 \left(\frac{c^3}{6}\right) (approaches in distribution). That is \prob[X_G = t] \to \frac{\mu^t e^{-\mu}}{t!} as n \to \infty where \mu = \frac{c^3}{6}. In particular the probability that there are no K_3 subgraphs is approaching e^{-c^3/6}. Note that if all \binom{n}{3} events were independent, then we would have \prob[X_G = 0] = (1-p^3)^{\binom{n}{3}} \approx e^{-p^3 n^3 / 6} \to e^{-c^3/6}. We will next apply the method of (factorial) moments also know as Brun's sieve. \begin{thm} Suppose X = X_n is a distribution on nonnegative integers such that E[X] \to \mu as n \to \infty and for every fixed r, \expect\left[\binom{X}{r}\right] \to \frac{\mu^r}{r!}. Then X \overset{D}{\longrightarrow} P_0 (\mu). \end{thm} Now note that If X = X_1+X_2+\cdots +X_m is a sum of indicator random variables corresponding to events A_1, A_2,\ldots,A_m then \expect\left[\binom{X}{r}\right] = \displaystyle\sum\limits_{{i_1, i_2,\ldots,i_r} \in \binom{[m]}{r}} \prob[A_{i_1} \wedge A_{i_2} \wedge \ldots \wedge A_{i_r}]. Returning to our example where G = K_3 we know that \expect[X_G] \to \frac{c^3}{6}. Now when considering \expect\left[\binom{X_G}{2}\right] we realize that two triangles will either be disjoint, intersect in a vertex, or intersect in an edge. The expected number of two disjoint triangles is p^6 \binom{n}{6}\binom{6}{3}\frac{1}{2} \approx \frac{1}{2}\left(\frac{n^3}{6}\right)^2 p^6 \approx \frac{\mu}{2}. While on the other hand the expected number of two triangles intersecting in a vertex is p^6 \binom{n}{3}\binom{n-3}{2}\frac{3}{2} = O(n^5 p^6) = o(1). Similarly the expected number of two triangles sharing an edge is p^5 \binom{n}{4}\binom{4}{2} = O(n^4 p^5) = o(1). So \expect\left[\binom{X_G}{2}\right] \to \frac{\mu^2}{2} as n \to \infty as desired. Now for \expect\left[\binom{X_G}{3}\right] consider that the expected number of 3 disjoint triangles is \frac{1}{3!} \binom{n}{3} \binom{n-3}{3} \binom{n-6}{3} p^9 \approx \frac{\mu^3}{3!} and the contribution to \expect\left[\binom{X_G}{3}\right] from 3 intersecting triangles will be small. Thus again we will see that \expect\left[\binom{X_G}{3}\right] \to \frac{\mu^3}{3!}. Continuing in this way and applying the previous theorem we see that X_G \overset{D}{\longrightarrow} P_0 \left(\frac{c^3}{6}\right). \begin{thm} If H is strictly balanced (\frac{e_{H'}}{v_{H'}} < \frac{e_H}{v_H} for every proper subgraph H') and if n p^{e_H/v_H} \to c > 0 as n \to \infty then X_H \overset{D}{\longrightarrow} P_0 (\mu) where \mu = \frac{c^{v_H}}{aut(H)}. (aut(H) is the number of automorphisms of H.) \end{thm} \begin{lem} Let e_t be the minimum number of edges in a t vertex union of k not mutually disjoint copies of a strictly balanced graph G, and suppose 2 \le k \le t < k v_G. Then for m(G) = \frac{e_G}{v_G} we have e_t > t m(G). \end{lem} \clearpage \section{(Friday, September 7)} Reminded: \begin{itemize} \item m_G = \max \frac{e_{G'}}{v_{G'}}, where maximum is taken over all subgraphs G' \item G is strictly balanced if m_{G'} < m_{G} for every proper subgraph G' \end{itemize} We want to show: \begin{thm}\label{lec_7_thm_1} If \begin{enumerate} \item G is strictly balanced, and \item p is such that \mathbb{E}[X_G]\to \mu\in(0,\infty), \end{enumerate} then X_G \to \text{Po}(\mu). \end{thm} Idea: method of moments \begin{itemize} \item If \mathbb{E}\to \mu\in(0,\infty) and \mathbb{E}\big[{X \choose k}\big] \to \frac{\mu^k}{k!}, then X \stackrel{\text{D}}{\to} \text{Po}(\mu). \item If X = X_1 + \ldots + X_m and X_i is indicator r.v. for event B_i, then$$\mathbb{E}\bigg[{X \choose k}\bigg] = \sum_{\text{all$k$subsets of$\{1,2,\ldots,m\}}} \prob[B_{i_1} \cap \ldots \cap B_{i_k}].\end{itemize} \textbf{Proof of Theorem~\ref{lec_7_thm_1}:} Write \mathbb{E}\big[{X_G \choose k}\big] = X_k'+X_k''. Here, X_G is sum of indicator r.v.s. How many? {n \choose v_G} (v_G)!/a_G where a_G:=\text{aut}(G). X_k' denotes contribution to sum from mutually vertex disjoint copies of G, and X_k'' denotes everything else. Note: \begin{align*} X_k'&=\frac{1}{k!}\frac{{n\choose v_G}(v_G)! p^{e_G}}{a_G}\frac{{n-v_G\choose v_G}(v_G)! p^{e_G}}{a_G} \cdots \frac{{n-(k-1)v_G\choose v_G}(v_G)! p^{e_G}}{a_G}\approx \frac{1}{k!}\mu^k \end{align*} since \mu = \mathbb{E}[X_G]=p^{e_G}{n \choose v_G}\frac{(v_G)!}{a_G}\approx \frac{n^{v_G}p^{e_G}}{a_G}, {n \choose v_G} \approx \frac{n^{v_G}}{(v_G)!} and {n -(k-1)v_G\choose v_G} \approx \frac{n^{v_G}}{(v_G)!}. Let e_t be the minimum number of edges in t vertex union of k not mutually disjoint copies of G. \begin{lem}\label{lec_7_lem_1} For k \ge 2 and k \le t < kv_G, we have e_t > t m_G, i.e., \frac{e_t}{t} > m_G (density of union > density of G). \end{lem} \textbf{Proof of Lemma~\ref{lec_7_thm_1}:} For arbitrary graph F, define f_F = m_G v_F-e_F. \\ Note: \begin{enumerate} \item f_G = 0 \item f_H > 0 for any proper subgraph H of G because G is strictly balanced. \item f_{F_1 \cup F_2} = f_{F_1}+f_{F_2}-f_{F_1\cap F_2} for arbitrary graphs F_1,F_2 \end{enumerate} Let F=\cup_{i=1}^{k}G_i. Assume without loss of generality G_1 \cap G_2 \neq \varnothing. \\ Induction on k: we want to show f_F<0 \\ k=2: f_{G_1 \cup G_2} = f_{G_1}+f_{G_2}-f_{G_1\cap G_2} <0~~~(\because f_{G_1} = f_{G_2} = 0, f_{G_1 \cap G_2}>0) \\ k\ge 3: Let F' = \cup_{i=1}^{k-1}G_i and H= F'\cap G_k. Then, f_F = f_{F'}+f_{G_k}-f_H <0~~~(\because f_{F'}<0 by induction, f_{G_k}=0, and f_{H} \ge 0 since H can be any subgraph of G including null graph or G itself) \hfill \square To finish proof of Theorem~\ref{lec_7_thm_1}, we want X_k''=o(1) for every k.X_k''=\sum_{t=k}^{kv_G-1}O(n^t p^{e_t})There are only finite many possibilities for F, for any fixed k,t. Note that n^t p^{e_t}\asymp n^t n^{-e_t/m_G} for p\asymp n^{-1/m_G}. But t-e_t/m_G <0 by Lemma~\ref{lec_7_lem_1}. So, X_k'' = o(1). \hfill \square A few balanced but not strictly balanced examples: \begin{enumerate} \item G = \triangle~\triangle, T = \triangle, p=\frac{c}{n} \\ We have a.a.s. X_G = {X_T \choose 2} = \frac{1}{2}X_T(X_T-1) (because a.a.s. no. \triangle\!\triangle<\triangle) \\ We know X_T \to z\in \text{Po}(\frac{c^3}{6}). \\ Continuous functions preserve converges in distribution. \\ So, X_G \stackrel{\text{D}}{\to} \frac{1}{2}z(z-1), z as above\\ In particular, \prob[X_G = 0] \to (1+\frac{c^3}{6})e^{-\frac{c^3}{6}} \\ (\because \prob[Z=0] = e^{-\frac{c^3}{6}}, \prob[Z=1] = \frac{c^3}{6}e^{-\frac{c^3}{6}}) \item G = \triangle~\Box, T = \triangle, S = \Box, p = \frac{c}{n} \\ a.a.s. X_G = X_T X_S \\ X_T \to z_1 \in \text{Po}(\frac{c^3}{6}) \\ X_S \to z_2 \in \text{Po}(\frac{c^4}{8}) \\ It turns out that (X_T,X_S)\stackrel{\text{D}}{\to} (\text{Po}(\frac{c^3}{6}),\text{Po}(\frac{c^4}{8})) and limit variables are independent (see chapter 6 of JLR). \\ X_G \to z_1z_2 \\ \prob[X_G = 0] = 1-(1-e^{-\frac{c^3}{6}})(1-e^{-\frac{c^4}{8}}) \item G = \triangle\!\_\_\,, p =\frac{c}{n} \\ It can be shown that X_G \to \sum_{i=1}^{Z_T}W_i \\ Z_T \in \text{Po}(\frac{c^3}{6}) \\ Each W_i\in \text{Po}(3c) all independent \\ Idea: Z_t triangles, Each W_i perpends edges \end{enumerate} \begin{ex} What is \prob[X_G = 0] in Example (3)? \end{ex} \clearpage \section{(Monday, September 10)} \textbf{Connection of Three Distributions; Binomial, Poisson and Normal} \subsection{Binomial distribution} Bin(n,p), a distribution on \{0,1,\cdots,n\} means when flipping a coin with the weighted head with probability p and the tail with probability 1-p n times, counting the number of heads. (or it can be considered as a sum of i.i.d Bernolli random variables.) \textbf{Example} The number of edges in G(n,p) is Bin(N,p) for N={n\choose 2}, and p=p. \textbf{Note} If Y \in Bin(n,p), then \mathbb{E}[Y] =np. To see connections of Bin(n,p) and Po(\mu), set \mu=pn\in(0,\infty) and let n\rightarrow \infty ( or p \rightarrow 0). Let Y \in Bin(n,p), then for a fixed k\geq0, \begin{align*} Pr[Y=k]&={n\choose k}p^k(1-p)^{n-k}\\ &\sim\frac{n^k}{k !}\left( \frac{\mu}{n}\right)^ke^{- \frac{\mu}{n}(n-k)} \quad(\because (1-p)\sim e^{-p} )\\ &\rightarrow \frac{\mu^k}{k!}e^{-\mu} \text{ as } n \rightarrow \infty \end{align*} In other words, if pn=\mu, and n\rightarrow\infty then \text{Bin} (n,p)\xrightarrow{\mathcal{D}}\text{Po}(\mu).$$Why is Poisson so ubiquitous? law of rare events" \textbf{Example} Let X_T be the number of triangles in G(n,p) for p=\frac{c}{n}. So \mathbb{E}[X_T] \rightarrow \frac{c^3}{6} \text{ as } n \rightarrow \infty. We showed by method of moments that X_T \xrightarrow{\mathcal{D}}\text{Po}( \frac{c^3}{6}). Is X_T is a binomial random variable? No, but seems to get like one. Model X_T as Bin(N,P), where N={n\choose3}, P=p^3. \textbf{Binomial Revisited} Let Y\in Bin(n,p). If set p \in (0,\, 1) and let n \rightarrow \infty, what can we say about the limiting behavior? \begin{equation}\frac{Y-\mathbb{E}[Y]}{\sqrt{\text{Var}(Y)}}\xrightarrow{\mathcal{D}}\mathcal{N}(0,1), \end{equation} where \mathcal{N}(0,1) a normal distribution with mean 0, variance 1 and probability density function f(x)=\frac{1}{\sqrt{2\pi}}e^{-x^2/2}. So if X\in\mathcal{N}(0,1) then$$ P(X\leq a)=\frac{1}{\sqrt{2\pi}}\int^{a}_{-\infty}e^{-x^2/2}dx,$$and (2) is equivalent that$$ P(Y\leq a)\rightarrow {\sqrt{2\pi}}\int^{a}_{-\infty}e^{-x^2/2}dx$$for every fixed a\in\mathbb{R} and n \rightarrow \infty. This holds in greate generality, even when variance does not exist. \subsection{Central limit theorem} \text{See Feller Vol. 1 and Vol. 2 for more general statement.} \begin{thm} Let S_n=X_1+\cdots+X_n where X_i are i.i.d random variables such that \mathbb{E}[X_i]=M and Var[X_i]=\sigma^2 exist. Then$$Pr\left[ \frac{S_n-n\mu}{\sigma\sqrt{n}}<\beta\right] \rightarrow \int^{\beta}_{-\infty}e^{-x^2/2}dx.$$In other word,$$\frac{S_n-\mathbb{E}[S_n]}{\sqrt{\text{Var}[S_n]}}\rightarrow \mathcal{N}(0,1).$$\end{thm} \begin{cor} If Y\in Bin(n,p) for a fixed p \in (0,\infty), then$$ \frac{Y-\mathbb{E}[Y]}{\sqrt{\text{Var}[Y]}} \rightarrow \mathcal{N}(0,1).$$\end{cor} \begin{thm} Let X=X_n be Poisson distribution with mean\mu=\mu_n and suppose \mu \rightarrow \infty , \, n \rightarrow \infty. Then$$ \frac{X-\mathbb{E}[X]}{\sqrt{\text{Var}[X]}} \rightarrow \mathcal{N}(0,1).$$\end{thm} \setlength{\unitlength}{1.1cm} \begin{picture}(5,5) \thicklines \put(3.9,3.7){\vector(-3,-2){2.9}} \put(5.5,3.7){\vector(3,-2){2.9}} \put(1.8,1.1){\vector(1,0){5.5}} \put(4,4){\large{Bin(n,p)}} \put(0,1){\large{Poisson}} \put(8,1){\large{Normal (Gaussian)}} \put(4,0.7){\mu \rightarrow \infty} \put(1,3.5){p small''} \put(1,3){pn=c} \put(7,3.5){p large (fixed)''} \put(7.5,3){pn \rightarrow \infty} \end{picture} \subsection{Random Graphs} Recall that$$m_G=\max_{\substack{H\leq G, \\ \text{subgraphs}}}\frac{e_H}{v_H}.$$Recently, we have proved \begin{enumerate} \item p=n^{-\frac{1}{m_G}} is the threshold for appearance of G subgraphs. \item If G is strictly balanced and \mathbb{E}[X_G]\rightarrow \mu, then X_G \xrightarrow{\mathcal{D}}\text{Po}(\mu). \end{enumerate} What if p>>n^{-\frac{1}{m_G}}? (See Ch.6 and Thm 6.5 on JTR.) \begin{thm} Let G be a fixed graph, with e_G>0. Suppose that \begin{enumerate} \item np^{m(G)} \rightarrow \infty, \item n^2(1-p) \rightarrow \infty, (i.e. p is not too large) \end{enumerate} then$$\frac{X_G-\mathbb{E}[X_G]}{\sqrt{\text{Var}[X_G]}}\xrightarrow{\mathcal{D}}\mathcal{N}(0,1).$$\end{thm} \textbf{Note} Suppose n^2(1-p) \rightarrow c \in (0,\infty), then \mathbb{E}[ {\# \text{ non-edges }}]={n\choose 2}(1-p)\rightarrow c/2. In fact, X_n=\# non-edges is binomial with finite mean, so it is Poisson in limit with \mu=c/2, and Pr[no non-edges]\rightarrow e^{-c/2}>0. That is, Pr[G(n,p) is a complete graph] is bounded away from zero. \clearpage \section{(Wednesday, September 12)} Let \omega(G) denote the clique number of a graph, G, which is defined as the size of the largest complete subgraph of G. \begin{ex} Suppose p=n^{-0.99}. How does \omega(G(n,p)) behave? \end{ex} Since we know that the threshold for having a K_3 subgraph is n^{-1} and the threshold for having a K_4 subgraph is n^{-\frac{2}{3}}, we have a.a.s. at least one K_3 subgraph and zero K_4 subgraphs. So \prob[\omega(G(n,p)) = 3] \to 1. More generally, since a complete graph is strictly balanced, we know the threshold for having a K_k subgraph (k fixed) is at p = n^{-\frac{k}{{k \choose 2}}} = n^{ \frac{-2}{k-1}} \begin{ex} Fix k and let p = c n^{ \frac{-2}{k-1}}. What can we say about \omega(G(n,p))? \end{ex} First, we know that a.a.s we have K_{k-1} subgraphs and zero K_{k+1} subgraphs. Moreover sometimes, we have K_k and sometimes we don't. Hence a.a.s., \omega(G(n,p)) is either k-1 or k. If X = the number of K_k subgraphs, then X converges in distribution to a poisson random variable with mean \mu, where \mu = \lim \expect[X].$$\expect[X] = {n \choose k} p^{ {k \choose 2}} \sim \frac{n^k}{k!} \frac{c^{ {k \choose 2}}}{n^k} \sim \frac{ c^{ {k\choose2}}}{k!}$$So we have that$$\prob[ \omega \geq k ] = \prob[ \exists K_k \subset G] \to \prob[Po( \frac{ c^{ {k\choose2}}}{k!} ) \geq 1] = 1 - \exp\left(-\frac{c^{k \choose 2}}{k!}\right)$$So \prob[\omega = k-1] \to \exp\left(-\frac{c^{k \choose 2}}{k!}\right) and \prob[\omega = k] \to 1 - \exp\left(-\frac{c^{k \choose 2}}{k!}\right). \begin{rem} For a fixed \alpha > 0, if p = O( n^{-\alpha} ), then the clique number should be concentrated on at most 2 values. \end{rem} \begin{ex} What can we say about larger p? For example, suppose p = \frac{1}{2}. What is \omega(G(n,p))? \end{ex} Heuristically if we solve n^{\frac{-2}{k-1}} =p for k, we find k \sim \frac{2 \log(n)}{-\log(p)}. So we might suspect that k \sim 2 \log_2 n. Define f(k) = \expect[ \text{number of } k-cliques] ={ n \choose k} \left( \frac{1}{2} \right)^{k \choose 2}. \begin{ex} Let \delta > 0. Show that if k \geq (2+\delta) \log_2 n, then f(k) \to 0 and if k \leq (2 - \delta) \log_2 n, then f(k) \to \infty, as n \to \infty. \end{ex} \begin{rem} If N \to \infty and M = o( \sqrt{N} ), then {N \choose M} \sim \frac{N^M}{M!} as N \to \infty \end{rem} Suppose that k = O( \log(n)), then$${ n \choose k} \left( \frac{1}{2} \right)^{k \choose 2} \sim \frac{n^k}{k!} \left( \frac{1}{2} \right)^{k \choose 2} \sim \frac{1}{\sqrt{2 \pi k} } \frac{e^k n^k}{k^k} \left( \frac{1}{2} \right)^{k \choose 2} = \frac{1}{\sqrt{2 \pi}} \exp \left( k+ k \log(n) - (k+\frac{1}{2}) \log(k) - {k \choose 2} \log(2) \right) = \frac{1}{\sqrt{2 \pi}} \exp \left( k \log(n) - \frac{k^2}{2} \log(2) + O( k \log(k) ) \right) = \frac{1}{\sqrt{2 \pi}} \exp \left( k \log(n) - \frac{k^2}{2} \log(2) + O( \log(n) \log(\log n) ) \right)$$If k = (2 + \epsilon) \log_2 (n), then$$f(k) \sim \frac{1}{\sqrt{2 \pi}} \exp \left( - \epsilon \left( 1 + \frac{\epsilon}{2} \right) \frac{1}{\log(2)} \log^2(n) + o( \log^2(n)) \right) $$Depending on the sign of \epsilon, we get the desired result. Following theorem is in Chap 4 of Alon and Spencer. \begin{thm} Let k = k(n) satisfying k \sim 2 \log_2 n and f(k) \to \infty Then a.a.s. \omega(G(n,p)) \geq k. \end{thm} Proof using Second Moment method. (Also see Chap 10 of Alon and Spencer for more precise results using Janson's Inequality). Let A_1, A_2, \dots, A_{ n \choose k} be the events that correspond to one of the {n \choose k} possible k-cliques is present. Let X_1, \dots be the corresponding indicator random variables and X = \sum_l X_l. Fix l, and let \Delta^*=\sum_{j \sim l} \prob[A_j | A_l]. If we can show that \expect[X] \to \infty and \Delta^* = o( \expect[X] ), then we have that a.a.s. X>0. By hypothesis, \expect[X] = f(k) \to \infty. If i corresponds to the number of vertices in the intersection with the fixed clique l of size k, then$$\Delta^* = \sum_{i=2}^{k-1} { k \choose i} {n-k \choose k-i} \left( \frac{1}{2} \right)^{ {k \choose 2} - {i \choose 2}}  = \expect[X] \sum_{i=2}^{k-1} g(i)$$where$$g(i) = \frac{ {k \choose i} {n-k \choose k-i} }{{n \choose k}} 2^{i \choose 2}$$\begin{ex} Show that \sum_i g(i) = o(1) \end{ex} We will show that g(2) and g(k-1) tend to zero.$$g(2) = \frac{ {k \choose 2} {n-k \choose k-2} }{{n \choose k}} 2^{2 \choose 2} \sim \frac{k^2}{2} \frac{n^{k-2}}{(k-2)!} \frac{k!}{n^k} 2 \sim \frac{k^4}{n^2} = o(1)g(k-1) = \frac{ {k \choose k-1} {n-k \choose 1} }{{n \choose k}} 2^{k-1 \choose 2} = \frac{ k (n-k) 2^{-(k-1)} }{{n \choose k} 2^{k \choose 2} } \sim \frac{ 2 k \cdot n\cdot 2^{-k} }{f(k)} \sim \frac{2}{f(k)} \exp\left( \log(k) + \log(n) - k \log(2) \right)$$Since k \sim 2 \frac{ \log(n) }{\log(2)}, this exponent tends to - \infty giving the result we want. Hence X > 0 a.a.s., which implies that \omega(G(n, \frac{1}{2} )) \geq k. \begin{rem} Since \frac{ f(k+1)}{f(k)} = \frac{n-k}{k+1} 2^{-k} and k \sim 2 \log_2 n, we have that \frac{ f(k+1)}{f(k)} = o(n^{-1}). \end{rem} We can let k_0 = k_0(n) be such that f(k_0) \geq 1 > f(k_0+1). For "most" n, f(k) jumps from large f(k_0) to small f(k_0+1). \begin{cor} [Bollobas, Erdos 76; Matule 76] There exists a sequence k = k(n) such that \prob[\omega(G(n,\frac{1}{2}))= k \text{ or } k+1 ] \to 1 \end{cor} Moreover in Bollobas' book (on the chapter on cliques), it is shown that k_0 = 2 \log_2 n - 2 \log_2 \log_2 n + \log_2 \frac{e}{2} + o(1) \begin{quest} What is the threshold for G(n,p) to be connected? \end{quest} One possible approach is to count the number of spanning trees in G(n,p) From Cayley's Theorem, we know that the number of trees on n vertices is n^{n-2}. \begin{ex} Consider \expect[ \text{number of spanning trees}] and the threshold of connectivity. How many spanning trees should we expect to see? \end{ex} \clearpage \section{(Friday, September 14)} Today: Threshold for Connectivity of G(n,p).\\ \\ A naive approach is to count spanning trees. Recall that the graph K_n has n^{n-2} spanning trees. The probability that a particular spanning tree occurs in G(n,p) is p^{n-1}, so$$\mathbb{E}[\# \ \text{of spanning trees}] = n^{n-2}p^{n-1} = n(np)^{p-1}$$\begin{rem} If p\leq \frac{c}{n} for c < 1, then \mathbb{E}[\# \ \text{of spanning trees}]\rightarrow 0 \ \Rightarrow a.a.s \nexists spanning trees \Rightarrow a.a.s G(n,p) is not connected. And if p\geq\frac{c}{n} for c > 1, then \mathbb{E}[\# \ \text{of spanning trees}]\rightarrow \infty. \end{rem} In the case that p\geq\frac{c}{n}, even though \mathbb{E}\rightarrow \infty, this does not necessarily imply that G(n,p) is connected a.a.s. Instead we conclude that Var[X] \neq 0. \begin{thm} Threshold for Connectivity of G(n,p)\\ \begin{enumerate} \item If p\geq\displaystyle\frac{\log n + \omega(1)}{n}, then G(n,p) is connected a.a.s. \item If p\leq\displaystyle\frac{\log n - \omega(1)}{n}, then G(n,p) is disconnected a.a.s. \item If p = \displaystyle\frac{\log n + c}{n}, \ c > 1 constant, then Pr[G(n,p) is connected] \rightarrow e^{-e^{-c}}\\ \end{enumerate} \end{thm} Erd\H{o}s-R\'{e}nyi's idea was to look for components of order i = 1,2,\ldots,\lceil \frac{n}{2}\rceil \begin{itemize} \item[\underline{i=1}:] Isolated vertices. Let X_i = \# components of order i.\\ \mathbb{E}[X_1] = n(1-p)^{n-1}. So if p = \frac{\log n + c}{n}, then$$\mathbb{E}[X_1] = n\left(1-\frac{\log n + c}{n}\right)^{n-1}\approx ne^{-\frac{\log n + c}{n}(n-1)}\rightarrow ne^{-\log n}e^{-c} = e^{-c} \ \mathrm{as} \ n\rightarrow\infty$$\begin{ex} Show that X_1\xrightarrow{\mathcal{D}}\text{Po}(e^{-c}), though none of the events are pairwise disjoint for distinct vertices. \end{ex} \item[\underline{i=2}:] Isolated edges.\\ \mathbb{E}[X_2] = {n \choose 2}p(1-p)^{2(n-2)}. If p\sim\frac{\log n}{n},$$\mathbb{E}[X_2] \approx \frac{n^2}{2}\frac{\log n}{n}e^{-\frac{\log n}{n}2(n-2)}\rightarrow\frac{n\log n}{2}e^{-2\log n} = O\left(\frac{\log n}{n}\right)\rightarrow 0$$\item[\underline{i=3}:] Triangles and paths of length two on three vertices.\\ \mathbb{E}[X_3] \leq {n \choose 3}3p^2(1-p)^{3(n-3)}. Again, for p\sim\frac{\log n}{n},$$\mathbb{E}[X_3] \approx \frac{n^3}{6}\frac{\log^2 n}{n^2}e^{-\frac{\log n}{n}3(n-3)}\rightarrow\frac{n\log^2 n}{6}e^{-3\log n} = O\left(\frac{\log^2 n}{n^2}\right)\rightarrow 0$$\end{itemize} For an upper bound that a set of k vertices is connected, recall$$\mathbb{E}[\# \ \text{spanning trees}] = k^{k-2}p^{k-1}$$Now for 4\leq k\leq\lceil\frac{n}{2}\rceil$$\mathbb{E}[X_k] \leq \sum_{i=4}^{\lceil\frac{n}{2}\rceil} {n \choose k}k^{k-2}p^{k-1}(1-p)^{k(n-k)}\leq \sum_{i=4}^{\lceil\frac{n}{2}\rceil} \frac{n^k}{k!}k^{k-2}p^{k-1}e^{-pk(n-k)}\leq\sum_{i=4}^{\lceil\frac{n}{2}\rceil} \frac{n^k}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^k}k^{k-2}p^{k-1}e^{-pk(n-k)} = \frac{1}{\sqrt{2\pi}}\sum_{i=4}^{\lceil\frac{n}{2}\rceil} \frac{1}{k^{5/2}}(ne)^kp^{k-1}e^{-pk(n-k)} = \frac{1}{p\sqrt{2\pi}}\sum_{i=4}^{\lceil\frac{n}{2}\rceil} \frac{1}{k^{5/2}}\left(\frac{enp}{e^{p(n-k)}}\right)^k\leq\frac{1}{p\sqrt{2\pi}}\sum_{i=4}^{\lceil\frac{n}{2}\rceil} \left(\frac{enp}{e^{p(n-k)}}\right)^k$$\\ A standard trick is to bound by a geometric series with a\rightarrow 0 and r\rightarrow 0\\ So k\leq\lceil\frac{n}{2}\rceil\Rightarrow e^{p(n-k)}\geq e^{\frac{\log n}{n}\frac{n}{2}} = e^{\frac{\log n}{2}} = \sqrt{n}, and enp\sim e\log n \Rightarrow \frac{enp}{e^{p(n-k)}}\rightarrow 0\\ Look at a, the k=4 term:$$\frac{1}{p\sqrt{2\pi}}\left(\frac{enp}{e^{p(n-4)}}\right)^4 = \frac{1}{\sqrt{2\pi}}\frac{e^4n^4p^3}{e^{4p(n-4)}}\sim\frac{e^4n^4\frac{\log^3 n}{n^3}}{e^{4\frac{\log n}{n}(n-4)}}\rightarrow \frac{e^4n\log^3 n}{n^4} = \frac{e^4\log^3 n}{n^3}\rightarrow 0\Longrightarrow \frac{1}{p\sqrt{2\pi}}\sum_{i=4}^{\lceil\frac{n}{2}\rceil} \left(\frac{enp}{e^{p(n-k)}}\right)^k \rightarrow 0$$\\ Hence \mathbb{E}[\# \ \text{components of order} \ 2\leq k\leq\lceil\frac{n}{2}\rceil]\rightarrow 0\\ Thus if p = \displaystyle\frac{\log n + c}{n}, then a.a.s. G(n,p) consists of a (unique) giant component of order (1-o(1))n isolated vertices. And \mathbb{E}[X_1] = e^{-c}, \ X_1\in\text{Po}(e^{-c}). So$$\text{Pr}[G(n,p) \ \text{connected}]\sim\text{Pr}[G(n,p) \ \text{has no isolated vertices}]\rightarrow e^{-e^{-c}}$$\\ In fact, for p = \displaystyle\frac{\log n + c}{n}, \ X_1 = \# \ \text{components} -1, so we have \tilde{\beta_0}\xrightarrow{\mathcal{D}}\text{Po}(e^{-c}).\\ \begin{ex} What is the threshold for the appearance of cycles? Is it sharp? \end{ex} \clearpage \section{(Monday, September 17)} Today : Expander-like qualities of G(n,p), Stronger notions of connectivity. \begin{defn} {\it{Cheeger number}} of a graph G$$h(G) = \min \frac{\# e(s,\overline{S})}{|S|},$$where minimum is taken over all S \leq V(G) and 1 \leq |S| \leq \frac{|V(G)|}{2}. \end{defn} Remark: This measures how hard it is to disconnect the graph. There's other ways to measure this: Vertex connectivity, edge connectivity. Exercise: Show that p = \frac{\log n + (k-1) \log \log n}{n} is sharp threshold for k-connectivity. Clearly, h(G) \leq min degree (G). Example. G=K_n: complete graph. Let k = |S|. Then e(S, \overline{S}) = k(n-k).$$h(K_n) = \min_{1 \leq k \leq \lfloor \frac{n}{2} \rfloor} \frac{k(n-k)}{k} \sim \frac{n}{2}.$$Our goal is to understand h(G(n,p)) to see that once G(n,p) is connected, it is very connected. Often we want "concentration of measure" results showing \Pr [ \left| X - E[X] \right| > t] is small. In many cases, one can do much better than Chebyshev's inequality / 2nd moment. \begin{thm} Chernoff-Hoeffding bounds. Let X = \sum_{i \in [m]} X_i, where X_i are independent distributed in [0,1]. (For example, i.i.d. indicator random variables.)$$\Pr[X > E[X] +t ] \leq e^{-2t^2/m}\Pr[X < E[X] - t ] \leq e^{-2t^2/m}\Pr[X > (1+ \epsilon) E[X] ] \leq \exp(-\frac{\epsilon^3}{3} E[X])\Pr[X < (1 - \epsilon) E[X] ] \leq \exp(-\frac{\epsilon^3}{2} E[X])$$\end{thm} \begin{thm} If p=w \left( \frac{\log n}{n} \right) and \epsilon >0 fixed, then a.a.s$$ \frac{(1-\epsilon) np }{2} \leq h(G(n,p)) \leq \frac{(1+\epsilon)np)}{2}.$$\end{thm} \begin{proof} Upper bound is clear. (Use Chernoff-Hoeffding boudns. E[\# \textrm{edges}] = \frac{n}{4}p and \frac{n^2/4p}{n/2} = np/2.) For any set S of s vertices, E[\# \textrm{edges}] = ps (n-s). Since s \leq n/2,$$\Pr [\# \textrm{edges} \leq (1-\epsilon) ps(n-2)] \leq \exp (-\frac{\epsilon^2}{2} ps (n-2)) \leq \exp(-\frac{\epsilon^2}{2} ps \frac{n}{2}).$$Set p \geq \frac{C \log n}{n} and C >1 to be determined.$$\Pr [\# \textrm{edges} \leq (1-\epsilon) ps(n-2)] \leq \exp( -\frac{\epsilon^2}{4} C s \log n ).$$Then, for c > \frac{4}{\epsilon^2}, \begin{eqnarray*} \Pr (h(G(n,p))) &\leq& \sum_{s=1}^{\lfloor \frac{n}{2} \rfloor} \exp( -\frac{\epsilon^2}{4} C s \log n) \\ &\ll& \sum \left( \frac{ne}{s} \right)^s \exp( -\frac{\epsilon^2}{4} C s \log n) \\ &=& \sum (\frac{ne}{s n^{\epsilon^2/4 C}})^s = o(1). \end{eqnarray*} \end{proof} \begin{defn} A family of bounded degree graphs G_1, G_2, \cdots with number of vertexes \rightarrow \infty is called expander family if$$\liminf_{n \rightarrow \infty} h(G_n) > 0.$$\end{defn} We will define Normalized Laplacian of a graph, which is a linear operator on functions on vertices$$C^0(G) = \{ f : V(G) \rightarrow \mathbb{R} \}$$Assume that the minimum degree of G satisfies \delta(G) \geq 1. \\ Define the averaging operator by$$A(f)(v) = \frac{1}{\deg v} \sum_{u \sim v} f(u).$$Define the identity operator by$$I(f)(v) = f(v).$$Then the Laplacian is defined by$$\triangle = I - A.$$Remark: Eigenvalues of \triangle are 0 \leq \lambda_1 \leq \lambda_2 \leq \cdots \lambda_n \leq 2. Multiplicity of 0-eignevalues is number of connected components of G. If G is connected, \lambda_2 is {\it{spectral gap}} or {\it{algebraic connectivity}}. \begin{thm}[Hoffman, Kahle, Paquette] There exists C>0 such that if$$p \leq \frac{\log n + C \sqrt{\log n} \log \log n}{n},$$then \Pr(\lambda_2 < 1- \epsilon) \rightarrow 0 as n \rightarrow \infty for any fixed \epsilon >0. \end{thm} \clearpage \section{(Wednesday, September 19)} \subsection{Simplicial Complexes} Today's lecture discussed higher-dimensional analogues of the Erd\"{o}s-R\'{e}nyi Theorem. To do so, we must dicuss the appropriate higher-dimensional extension of a (finite) graph. In this case, the appropriate extension is an (abstract, finite) simplicial complex. \noindent \begin{defn} \begin{itemize} \item Again, let [n] = \lbrace 1, 2, \dotsc, n \rbrace. \item An \textit{abstract finite simplicial complex}, denoted S, is a collection of nonempty subsets of [n] with the following two properties. \begin{enumerate} \item if \sigma \in S and \emptyset \neq \tau \subset \sigma, then \tau \in S. \item for all i \in \mathbb{N}, 1 \leq i \leq n, \lbrace i \rbrace \in S. \end{enumerate} \item Elements of S are termed \textit{faces} or \textit{simplices} of S; similarly, if \emptyset \neq \tau \subset \sigma, then \tau is termed a \textit{face} or \textit{facet} of the face \sigma. The \textit{dimension} of a face is one less than its cardinality: if \sigma \in S, \text{dim } \sigma = \vert \sigma \vert - 1. For example, if \lbrace a, b, c \rbrace \in S, the dimension of that face is 2. \item Define \text{dim } S to be \disp \max_{\sigma \in S} \text{dim } \sigma. \end{itemize} \end{defn} The above definition is designed to run parallel to the topological definition of a simplex. For example, if \lbrace a, b, c \rbrace \in S, a, b, and c are thought of as the vertices of a 2-simplex. In fact, to every face of S we explicitly associate a simplex of the appropriate dimension: singleton sets are vertices, \lbrace a, b \rbrace is a line segment, etc. In particular if \text{dim } S = 1, then S can be associated with the graph on the vertex set [n] with edges corresponding to the 1-cells. It is important to note (though we do not discuss the details here) that S can be considered as a topological simplex (a topological space), where requirement 1) of the definition ensures that the (topological) boundary of any simplex is included in the set of faces, and the second requirement just ensures that we have all vertices. To create a geometric realization'' of the abstract simplex, one starts with \mathbb{R}^{n}, with the standard basis vectors \left\lbrace e_1, \dotsc, e_n \right\rbrace. Then the simplex \disp \left\lbrace i_1, \dotsc, i_k \right\rbrace is realized as the convex hull of the vectors \left\lbrace e_{i_1}, \dotsc, e_{i_k} \right\rbrace. \begin{figure} \includegraphics[scale = 0.65]{19SeptCombPict1a} \includegraphics[scale = 0.5]{19SeptCombPict1b} %Feel free to edit the example below as you see fit \caption{Geometric Realization of some Two-Dimensional Simplices} \label{fig:geomSimplex} \end{figure} For a picture, see Figure~\ref{fig:geomSimplex}. For more details, including the technicality of distinguishing between an abstract simplicial complex and its geometric realization, see \cite{Bjorner}. We will intentionally blur the distinction between abstract complexes and their corresponding topological complexes. \subsection{(Simplicial, \mathbb{Z}/2\mathbb{Z}-)Cohomology} Recall that the Erd\"{o}s-R\'{e}nyi Theorem gave a sharp threshold for the connectivity of a graph. To generalize connectivity to higher-dimensional analogues, we first realize connectivity of a graph as a statement about the graph's (reduced) 0-homology, or equivalently, 0-cohomology.\footnote{The equivalence is governed by the universal coefficient theorem for homology,'' described in \cite[p.195]{Hatcher}.} For higher-dimensional variants, we will define a nice'' (simplicial, \mathbb{Z}/2\mathbb{Z}) cohomology, and start looking at the higher levels of cohomology. \begin{defn} \begin{itemize} \item Let F^i(S), i \geq 1, denote the collection of i-dimensional faces of S. \item Let C^i(S) denote the vector space of maps F^i(S) \to \mathbb{Z}/2\mathbb{Z}. This \mathbb{Z}/2\mathbb{Z} vector space is named the set of \textit{i-(\mathbb{Z}/2\mathbb{Z}-)cochains} of S. \item Define the \mathbb{Z}/2\mathbb{Z}-linear map, the \textit{coboundary operator}, as d^i: C^i(S) \to C^{i+1}(S), as follows: if f \in C^i(S), and \sigma \in F^{i+1}(S), define \disp d^i f(\sigma) = \sum_{\substack{\tau \text{ a face of } \sigma \\ \sigma = \tau \cup \lbrace j \rbrace \text{ for some } j \in \sigma}} f(\tau).\footnote{In general, powers of -1 according to orientations of the various faces enter into this formula. One advantage of working in \mathbb{Z}/2\mathbb{Z} is that (-1) = 1, so no minus signs are necessary.} In other words, we just add up f's values on all codimension-1 faces of \sigma. In practice, the reference to a specific level is suppressed, and we just write d, not d^i, when the level of the cochain vector space is understood. \item Z^{i} is defined to be the kernel of d^i. d^{i - 1} maps into C^i, and the image of d^{i-1} is termed B^i. \end{itemize} \end{defn} An example is in order. \begin{figure} \includegraphics[scale = 0.5]{19SeptCombPict2a} \includegraphics[scale = 0.5]{19SeptCombPict2b} %Feel free to edit the example below as you see fit \caption{Example of the coboundary map} \label{fig:cobound} \end{figure} See Figure~\ref{fig:cobound}. Looking at the upper-right-hand triangle above, note that there are two ways to have a function f on 1-cells in the boundary of a 2-cell such that df maps the 2-cell to 0: to have all the edges go to 0, or to have two of them going to 0 (since 1 + 1 = 2 = 0 in \mathbb{Z}/2\mathbb{Z}. In particular, then, it is likely that the kernel of d^i is a significant subspace of C^i. The key observation that enables our proceeding is the following exercise. \begin{lem} B^i \subset Z^i; that is, d \circ d = 0. \end{lem} \begin{proof} Fix f \in C^i(S), i \geq 1; we wish to show that d^{i+1} \circ d^i f = 0. By definition, the first coboundary gives \disp d^i f(\sigma) = \sum_{\substack{\tau \text{ a face of } \sigma \\ \sigma = \tau \cup \lbrace j \rbrace \text{ for some } j \in \sigma}} f(\tau). Then applying d^{i + 1} gives, for any i + 2-dimensional face \rho, \begin{eqnarray*} d^{i + 1}(d^i(f))(\rho) & = & \sum_{\substack{\sigma \text{ a face of } \rho \\ \rho = \sigma \cup \lbrace k\rbrace \text{ for some } k \in \rho}} d^i f(\sigma)\\ & = & \sum_{\substack{\sigma \text{ a face of } \rho \\ \rho = \sigma \cup \lbrace k \rbrace \text{ for some } k \in \rho}} \, \, \sum_{\substack{\tau \text{ a face of } \sigma \\ \sigma = \tau \cup \lbrace j \rbrace \text{ for some } j \in \sigma}} f(\tau) \end{eqnarray*} Yet note that since \sigma = \rho \setminus \lbrace k \rbrace, we can rewrite \sigma = \tau \cup \lbrace j \rbrace for some j \in \sigma'' as \sigma = \tau \cup \lbrace j \rbrace for some j \in \rho \setminus \lbrace k \rbrace.'' The point is not only that \tau is a codimension-2 face of \rho, but that for any codimension-two face \tau of \rho, say \tau = \rho \setminus \lbrace p, q \rbrace, we can find \tau in the final double-summation in two ways: by eliminating p and then q, or by eliminating q and then p. This happens for every such \tau, so in the end$$d^{i + 1} \circ d^i(f) (\rho) = \sum_{\substack{\tau\text{ a face of } \rho \\ \rho = \sigma \cup \lbrace p, q \rbrace \text{ for some } p, q \in \rho}} 2 f(\tau).$$Yet 2 = 0 in \mathbb{Z}/2\mathbb{Z}, so this becomes 0.\footnote{In the non-\mathbb{Z}/2\mathbb{Z} case, the trick is that the different orders of removing the vertices also shifts the sign of the orientation by one, so that the two copies of f(\tau) have competing signs and cancel in that way.} This works for all \rho \in F^{i + 2}(S), and for all f \in C^{i}(S), so d^{i + 1} \circ d^i = 0. \end{proof} Since B^i is a sub-vector space of Z^i, we can define the \textit{ith cohomology group with \mathbb{Z}/2\mathbb{Z} coefficients}, denoted H^i(S, \mathbb{Z}/2\mathbb{Z}) or simply H^i, as the quotient vector space$$\disp \frac{Z^i}{B^i} = \frac{\ker d^i}{\text{Im } d^{i-1}}.$$We leave it as a fact that the cohomology groups are \textit{topological invariants}; that is, homeomorphic spaces have the same cohomology groups (in fact, homotopy equivalent spaces have the same cohomology groups, but this will only concern us with concrete examples). For details, see Chapter 3 of \cite{Hatcher}. The other major property that will concern us is that the (singular) cohomology map is a contravariant functor; that is, a continuous map X \xrightarrow{f} Y induces a map H^i(Y) \xrightarrow{f^*} H^i(X) by the definition f^*: \phi \to \phi \circ f. Further, with (g \circ f)^* = f^* \circ g^* and (Id_X)^* = Id_{H^i(X)}, where Id_X is the identity on X. For our purposes, we need only concern ourselves with the dimension of the homology group dim H^i(S, \mathbb{Z}/2\mathbb{Z}).\footnote{This is emphatically not the case in most algebraic topology, where various long exact sequences of (co)homology groups become very important.} Let \beta^i(S) = \beta^i := \text{dim }H^i(S, \mathbb{Z}/2\mathbb{Z}) denote the \textit{ith (\mathbb{Z}/2\mathbb{Z}) Betti number} of the simplicial complex S. \begin{rem} A circle, S^1, has \beta^0 = 1 and \beta^1 = 1, and all other Betti numbers are 0. A sphere, S^2, has \beta^0 = 1, \beta^1 = 0, and \beta^2 = 1, and all other Betti numbers are 0. More generally, the d-dimensional sphere S^d \subset \mathbb{R}^{d + 1} has \beta^0 = 1 and \beta^d = 1 as the only nonzero Betti numbers. The sphere is a good intuitive picture of what objects correspond to the simplest nontrivial d-dimensional homology groups; very roughtly speaking, \beta^d counts the number of d-dimensional holes in the topological space modeled by a simplicial complex. \end{rem} We now show that remarks about the connectedness of a graph (e.g., the conclusions of the Erd\"{o}s-R\'{e}nyi theorem) are equivalent to statements about cohomology groups. \begin{lem} \beta^0 counts the number of connected components. Hence, S is connected if and only if \beta^0(S) = 1.\footnote{The proof is optional.} \end{lem} \begin{proof} There is no (-1)-st level in convential cohomology; or, to be more precise, we define it to be the single-point vector space \lbrace 0 \rbrace. Therefore, B^0 = \lbrace 0 \rbrace (since the boundary map is a vector space homomorphism, hence sends 0 \in C^{-1} to 0 \in C^0). Therefore, H^0 is equated with Z^0, the kernel of the map d^0. Yet a map f on vertices, mapping each vertex to 0 or 1, is transformed by the map df \in C^1 such that for all edges e = \lbrace i, j \rbrace in the set,$$df(e) = f(i) + f(j) = \left\lbrace \begin{array}{r l} 0, & \text{ if } f(i) \cong f(j) \mod{2} \\ 1, & \text{ if } f(i) \not\cong f(j) \mod{2} \end{array} \right.$$Therefore, any element f of the kernel Z^0 must have identical inputs on the vertices of every edge. If f is a \textit{nonzero} element of the kernel, it must send at least one vertex \lbrace i \rbrace to 1. Yet for any j adjacent to i, df(\lbrace{i, j}) = 0 (by f \in Z^0), but df(\lbrace{i, j}) = f(i) + f(j) = 1 + f(j), so 1 + f(j) = 0 \mod{2} and hence f(j) = 1. This happens similarly for all k adjacent to j, and so forth, so f must send the entire connected component of i to 1. It can, however, send all other vertices to 0. Therefore, for each connected component \alpha of S, there is a map f_{\alpha} \in Z^0 sending all vertices in \alpha to 1 and all vertices in other components to 0. These are clearly linearly independent functions, having disjoint support, and by the fact that elements of Z^0 are constant on connected components, they span Z^0. Therefore, dim(Z^0) = dim(H^0) = \beta^0 is equal to the number of connected components. \end{proof} \subsection{Reduced Homology Groups} The above work means that we can rephrase the topological property of connectivity in terms of a specific topological invariant, simplicial cohomology, which is multilayered,'' hence admits generalization. It is not intuitively clear, however, where to go from here. In particular, our example of spheres demonstrates that most'' homology groups of a simple space are 0-dimensional, not 1-dimensional. Also, if we are thinking algebraically, the simplest results should be the vanishing of such-and-such an invariant. We would like a situation where connectivity should correspond to \beta^0 being a trivial element of \mathbb{Z}, namely 0. We do not wish, however, to change any of the other Betti numbers.\footnote{The uninterested reader may now skip to the next subsection.} Therefore, we would like to define an altered set of Betti numbers \widetilde{\beta}^i, where$$\widetilde{\beta}^i = \left\lbrace \begin{array}{r l} \beta^i, & \text{ if } i \geq 1\\ \beta^0 - 1 & \text{ if } i = 0 \end{array} \right.$$To accomplish this, in the abstract simplicial complex, we now allow the empty set to be in our collection of subsets of [n], and modify the closure-under-subsets rule to eliminate the \emptyset \neq \tau criterion. Since we have already included all vertices, and the \emptyset \subset \lbrace i \rbrace for any i, the empty set is now a guaranteed member of our revised (which, for reasons that will become clear later, we call reduced'') simplicial complex. We declare dim(\emptyset) = 0, so that the empty set is a new codimension-1 face of every vertex. Pushing this forward to the level of cochains, we may now define F^{-1} = \lbrace \emptyset \rbrace (the set whose sole element is the empty set); thus, C^{-1} is the set of maps \lbrace \emptyset \rbrace \to \mathbb{Z}/2\mathbb{Z}, namely f_1: \emptyset \mapsto 1 and f_0: \emptyset \mapsto 0. Thus, this is a 1-dimensional \mathbb{Z}/2\mathbb{Z}-vector space. Therefore, d^{-1}: C^{-1} \to C^0 maps f_0 to the 0-map, but the map f_1 has, for any i \in [n], d^{-1}f_1(\lbrace i \rbrace) = f_1(\emptyset) = 1, and hence is the constant-1 map.\footnote{More generally, for any coefficient group G, d^{-1}(C^{-1}(X, G)) consists of all the constant maps from vertices to G; see, e.g., \cite[p. 199]{Hatcher}.} Hence, B^{-1} is now 1-dimensional, so the homology group \disp \widehat{H}^0 = \frac{Z^0}{\widehat{B}^{-1}} is reduced in dimension by 1, since we lose one degree of freedom by identifying maps that differ by a constant. Hence, we have defined the \textit{reduced} homology groups, where \widehat{H}^0 is adjusted as above, and nothing happens to the other parts of the cochain complexes, etc. Therefore, we have successfully defined a reduction in homology groups for which connectivity corresponds to the vanishing of some topological invariant. \begin{rem} \widetilde{\beta}^0(S) = 0 if and only if S is connected, for S any simplicial complex. \end{rem} Therefore, we are now in a natural enough setting that we are able to fruitfully generalize the Erd\"{o}s-R\'{e}nyi Theorem by focusing our attention on \beta^1, and asking when it vanishes. \subsection{Random 2-Dimensional Simplicial Complexes} Following Linial and Meshulam \cite{Linial}, we now create a model of random 2-complexes. In order to avoid undue complexity, the simplest models should have a connected graph as their 1-skeleton (the collection of vertices and edges), since otherwise we have to start worrying about the interactions between the 0th and 1st cohomology groups. \begin{defn} Define Y(n, p) to be the 2-dimensional simplicial complex on the vertex set [n], where all vertices and edges (all sets of the form \lbrace i \rbrace or \lbrace i, j \rbrace) are included. For the \disp \nCk{[n]}{3} faces \lbrace i, j, k \rbrace, we add them to the simplex with probability p, jointly independently. \end{defn} The paper \cite{Linial} studies H^1(Y(n, p); \mathbb{Z}/2\mathbb{Z}), and in so doing gives guidance on the behavior of \beta^1. The extreme case p = 0 corresponds to the case of an very large \beta^1, since the lack of two-cells means that \textit{every} edge can create its own cocycle (since C^2 is empty and hence \textit{every} function in C^1 has coboundary map 0), whereas the set of coboundaries is fixed to those functions that give either 0 or 2 1's to the edges of any given triangle (as can be seen by case-by-case enumeration). At the other extreme, p = 1 causes H^1(Y(n, 1), \mathbb{Z}/2\mathbb{Z}) = 0, because f is a cocycle now if and only if the number of 1's f assigns to each edge of a triangle must be even (since the triangle's value in df equals the mod-2 sum of the values of the edges), hence 0 or 2, and hence a coboundary. \begin{lem} The property of having a trivial H^1, i.e., H^1(Y(n, p), \mathbb{Z}/2\mathbb{Z}) = 0, is a monotone-increasing property in p = p(n). \end{lem} \begin{proof} Exercise. \end{proof} We are now in a position to state a major theorem of Linial and Meshulam. \begin{thm}[\cite{Linial}]$$\prob[H^1(Y(n, p); \mathbb{Z}/2\mathbb{Z}) = 0] = \left\lbrace \begin{array}{r l} 1, & p \geq \frac{2 \log(n) + \omega(1)}{n}\\ 0, & p \leq \frac{2 \log(n) - \omega(1)}{n} \end{array} \right.$$\end{thm} Compare this to the Erd\"{o}s-R\'{e}nyi Theorem:$$\prob[\widetilde{H}^0(G(n, p); \mathbb{Z}/2\mathbb{Z}) = 0] = \left\lbrace \begin{array}{r l} 1, & p \geq \frac{1 \log(n) + \omega(1)}{n}\\ 0, & p \leq \frac{1 \log(n) - \omega(1)}{n} \end{array} \right.$$There are similarities with parts of the proof, not just the statement. Recall that the final obstruction to the connectivity of G(n, p) was isolated vertices (because asymptotically almost surely, in the first case, the components of size less than or equal to \disp \left\lfloor \frac{n}{2} \right\rfloor disappeared, so that we had a large component and isolated vertices). Similarly, we want to show in the present case that if there are any isolated edges (i.e., an edge with \textit{no} incident triangles), then H^1 \neq 0 and \beta^1 > 0. We note that any given edge uses two vertices, and hence there are n-2 other vertices that combine with the given edge to give a triangle of edges; the face for that triangle is \textit{not} added with probability (1 - p). There are \binom{n}{2} such edges; hence, by linearity of expectation, \expect ( \# \text{ isolated edges}) = \binom{n}{2}(1 - p)^{n - 2}. Therefore, if \disp p \asymp \frac{2 \log (n) + c}{n}, then we have that \begin{eqnarray*} E(\# isolated edges) & \asymp & \frac{n^2}{2} e^{-\frac{2 \log(n) + c}{n} (n-2)}\\ & \asymp & \frac{n^2}{2} e^{-(2 \log(n) + c)}\\ & \asymp & \frac{n^2}{n^2} * \frac{1}{2}e^{-c}\\ & = & \frac{1}{2}e^{-c}. \end{eqnarray*} Note that each isolated edge indeed generates some 1-cochains that are not 1-coboundaries. More specifically, taking the map f that takes the value 1 on an isolated edge e = \lbrace i, j \rbrace and 0 on all other edges gives a cocycle (since there are no adjacent triangles, so the coboundary of this map is necessarily 0). It is not, however, a 1-coboundary (since dg = f for g \in C^0(Y(n, p), \mathbb{Z}/2\mathbb{Z}) would require that g assign a value of 1 to one of the endpoints of e (say i), and 0 to the other endpoint j. Any other vertex k must be assigned a 1 so that \lbrace i, k \rbrace gets mapped to 0, but simultaneously must be assigned a 0 so that \lbrace j, k \rbrace gets mapped to 0. Therefore, f is not a coboundary. Therefore, H^1(Y(n, p), \mathbb{Z}/2\mathbb{Z}) \neq 0 in such a case. \begin{conj} If p = \frac{2 \log n + c}{n}, then$$\beta^1(Y(n, p), \mathbb{Z}/2\mathbb{Z}) \xrightarrow{D} \text{Po}\left( \frac{1}{2} e^{-c}\right),$$where \xrightarrow{D} denotes convergence in distribution. \end{conj} The above conjecture is in fact true, but is stated as a conjecture because for random d-dimensional simplicial complexes analogous to the above two-dimensional case, the analogous statement for \beta^d is only known for large d. Note, however, that this is an extension of a preliminary result used in proving the Erd\"{o}s-R\'{e}nyi Theorem:$$\widetilde{\beta}^0(G(n, p)) \xrightarrow{D} \text{Po}\left(e^{-c}\right),$$when \disp p = \frac{\log n + c}{n}. \clearpage \section{(Friday, September 21)} First, some thoughts about homology versus cohomology. Sometimes homology is easier to think about. \subsection{H_0(X, \mathbb{Z}/2) measures the number of connected components of a graph.} \begin{defn} \begin{enumerate} \mbox{} \item The zeroth homology group with \Z/2 coefficients H_0(X, \mathbb{Z}/2) is a (\mathbb{Z}/2)-vector space whose dimension is the number of connected components of X. \item The zeroth {\it reduced homology group} \widetilde{H}_0 is a (\mathbb{Z}/2)-vector space whose dimension is the number of connected components of X minus one. \item A 0-chain is a function \phi: V \rightarrow \mathbb{Z}/2. \item A 0-cycle \phi is a function in the kernel the boundary operator, i.e. d \phi=0. In reduced homology, this is equivalent to a function supported on an even number of vertices. Then notice that the vector space of all cycles is generated by functions supported on pairs of vertices. \item By definition, \widetilde{H}_0 = cycles/boundaries. \end{enumerate} \end{defn} So we say \widetilde{H}_0 = 0 if and only if every cycle is a boundary i.e., every pair of vertices is connected by a path. It turns out that \widetilde{H}_0 = 0 \Leftrightarrow \widetilde{H}^0 = 0. But when we proved Erd\H{o}s--R\'enyi theorem, we actually proved the cohomological version \tilde{H^0} = 0, i.e.\ every cocycle is a coboundary. The only coboundary is the coboundary of the empty set, defined to be the constant function \phi: V(H) \to 1. A cocycle is a collection of vertices so that every edge meets an even number of them, or equivalently, a union of connected components generated by connected components. So we see that every cocycle is a coboundary'' really is equivalent to H is connected.'' To prove the Erd\H{o}s--R\'enyi theorem, we show that for \phi= collection of vertices, \Pr (\phi \, \textrm{is nontrivial cocycle}) is small.$$\Pr (\phi \, \textrm{is nontrivial cocycle})\leq k^{k-2}p^{k-1}(1-p)^{k(n-k)},$$k(n-k) is the size of d \phi in complex graph. \subsection{H_1(G), G a connected graph.} \mbox{} \begin{defn}\mbox{} \begin{enumerate} \item Cycles = collection of edges meeting every vertex in an even number of edges. generated by primitive cycles. \item 1-coboundaries = cut spanning complete bipartite graph. \item 1-cocyles=collection of edges meeting every triangle in an even number. \end{enumerate} \end{defn} H_1=0 means every cycle is boundary means no cycles. In a 2-dimensional complex H_1=0 means every cycle is a boundary. It is known that for 2-dimensional simplicial complex Y, H_1(Y, \mathbb{Z}/2) \equiv H^1(Y, \mathbb{Z}/2). Linial--Meshulam considers the case for 2-dim \mathbb{Z}/2 coefficients. Meshulam--Wallach: d-dim, \mathbb{Z}/m coefficients. Let \triangle_n^{(2)} be a 2-skeleton of simplex on n-vertices. i.e., n vertices, {n \choose 2} edges, {n \choose 3} faces. Let \phi \in C^1(\triangle_n^{(2)}), b(\phi) = |\textrm{supp} \, d \phi| = number of triangles with an odd number of edges from \phi. w(\phi) = \min (\textrm{supp} \, \phi + d \tau), \tau \in C^0. \begin{thm}[Meshulam-Wallach] b(\phi) \geq \frac{n}{3} w(\phi). (co-isoperimetric inequality).$$\Pr[ \exists \textrm{ any non-trivial cocyles}] \leq \sum_{k=1}^{{n \choose 2}/2} {{n \choose 2} \choose k} (1- p)^{\frac{n}{3}k}.$$\end{thm} \begin{ex} Show that if$$p \geq \frac{6 \log n + \omega(1)}{n}$$then$$\Pr[ \exists \textrm{ any non-trivial cocyles}] \to 0.$$\end{ex} To get all the way down to the true threshold of$$ p = \frac{2\log n}{n}$$requires careful cocyle counting. See also Hoffman, Kahle, Paquette's recent preprint A sharp threshold for Kazhdan's property (T)'' (arXiv:1201.0425), where spectral analogues of the Linial--Meshulam theorem are discussed, with applications to geometric group theory. \clearpage \section{(Monday, September 24)} This lecture discusses the evolution of G(n,p) as a process with varying p, and in particular the phase transition that occurs around p=\frac{1}{n}. We begin by considering p=O(n^{-1-\epsilon}) for fixed \epsilon>0: \begin{prop} Let k>0 be fixed and p=o(n^{-(k+1)/k}); then w.h.p. all connected components are of order at most k. \end{prop} \begin{proof} For k=1: p=o(n^{-2}) and \expect(e)=p{n\choose 2}=O(pn^2)=o(1), so w.h.p. there are no edges. For k=2: Any component of order 3 contains a path of length 2, and $\expect(\# \textrm{2-paths})=\Theta(n^3p^2)=o(1),$ so w.h.p. any component has order at most 2. For k arbitrary, there are only finitely many connected graphs of order k+1, each of which has at least k edges. Thus the expected number of copies of any particular connected graph with k+1 vertices is O(n^{k+1}p^k)=o(1) by assumption, and summing only finitely many (as k is fixed) is once again o(1). \end{proof} Thus if p is bounded by any power of n less than n^{-1}, G(n,p) has only very small components (i.e. of bounded size). We can also establish how many cycles G(n,p) is likely to have. For fixed k, the threshold for finding a cycle C_k is p=n^{-v/e}=n^{-1}. By the same logic as the proposition above, if p=o(n^{-1-\epsilon}) then w.h.p. G(n,p) is a forest (a collection of trees). We can say more: \begin{prop} If p=o(n^{-1}), then G(n,p) is a forest w.h.p. \end{prop} \begin{proof} Let k\geq 3 be a fixed integer. Then the expected number of C_k subgraphs in G(n,p) is n^kp^k/2k, since the automorphism group of C_k is the dihedral group D_{2k}. Now, write p=cn^{-1}; then $\expect(\#\textrm{ cycles})=\sum_{k=3}^\infty \frac{n^kp^k}{2k}\leq \sum_{k=3}^\infty \frac{c^k}{2k}\leq c^3+c^4+c^5+\cdots$ Since p=o(n^{-1}), we can take c<1 and let c\rightarrow 0. Then the geometric series above converges to \frac{c^3}{1-c}\rightarrow 0. So w.h.p. the expected number of cycles is 0, meaning G(n,p) is a forest. \end{proof} In fact, if p=c/n with c>1, then w.h.p. G(n,p) contains a cycle. Moreover, it can be proved that the probability of finding a cycle approaches a constant for c=1, and the probability that the first cycle is C_k approaches a limiting distribution which is bounded away from zero for all k. Next is the case where p\gg n^{-1}; in particular, we examine p\geq n^{-1/2+\epsilon} for positive \epsilon: \begin{prop} If p\geq n^{-1/2+\epsilon}, then w.h.p. G(n,p) has diameter at most 2. \end{prop} \begin{proof} In fact it is only necessary to assume that \displaystyle{p\geq \left(\frac{C\log n+\omega(1)}{n}\right)^{1/2}} for some fixed C>0 (to be determined). With that assumption, for any two vertices x,y\in [n],$$\expect(\#\textrm{ paths} \{x,v,y\})=(n-2)p^2=(n-2)\left(\frac{C\log n+\omega(1)}{n}\right)\geq C\log nSince there are O(n^2) pairs of points x,y, we need \prob[\textrm{no path} \{x,v,y\}]=o(n^{-2}). The number of paths of length 2 from x to y is a binomial random variable \mbox{Bin}(n-2,p^2). The relevant Chernoff bound is \prob[X\leq (1-\epsilon)\expect[X]]\leq \exp(\expect[X]\epsilon^2/2). Fix \epsilon=1/2; then $\prob[\textrm{no path} \{x,v,y\}]\leq exp(-\frac{1}{8}C\log n)=n^{-C/8}$ so if C>16, this probability is o(n^{-2}), as desired. \end{proof} \begin{ex} Show that if \displaystyle{p\geq \left(\frac{2\log n+\omega(1)}{n}\right)^{1/2}}, then the diameter of G(n,p) is \leq 2 w.h.p. \end{ex} To determine whether G(n,p) has diameter at most k, we apply the same principle as above: fix vertices x and y. Then \expect[\#\textrm{ paths of length} k] is of order n^{k-1}p^k. We would expect that if n^{k-1}p^k\rightarrow\infty at least as fast as \log n, then w.h.p. every pair of vertices in G(n,p) is joined by a path of length at most k: \begin{prop} If \displaystyle{p\geq \left(\frac{C_k\log n}{n}\right)^{k/(k+1)}}, then w.h.p. \mbox{diam}(G(n,p))\leq k+1. \end{prop} Note, however, that for k>1, the paths between x and y are no longer described by a binomial distribution. Instead, the appropriate tools are Jansen inequalities, which stand in for Chernoff bounds. \begin{prop} Let p=\frac{c\log n}{n}. If \frac{1}{2} m_G\cdot t. \end{lem} Let i be the number of vertices in intersection of two such paths. Then either i=1 or i=2. \begin{ex} Show that n^{-k/(k+1)} is (roughly) threshold for diameter \le k+1. \end{ex} \clearpage \section{(Friday, September 28)} \textbf{Example} Let X be the number of triangles in G(n,p) for p = \frac{c}{n} then \mu \to \frac{c^3}{6} and \Delta = o(1) So \prob[X = 0] \le e^{-c^3/6 + o(1)} by Janson. In general \mu = \frac{n^3 p^3}{6} and \Delta = \frac{n^4 p^5}{4}. Once p \gg n^{-1/2} we have \Delta > \mu so for example for p = \frac{1}{2} we have \prob[X = 0] \le e^{-c n^2} by extended Janson. \textbf{Example} Consider paths of length k+1 from x\leftrightarrow y. Set \mu = n^k p^{k+1} = 2 \log(n) + \omega(1). In this case \Delta = o(1). Observe that two distinct paths x \leftrightarrow y that intersect in i vertices intersect in at most i edges. Then the largest contribution to \Delta is n^{2k-1} p^{2k+1} when i=1. Then we conclude if n^k p^{k+1} \geq (2 + \varepsilon)\log(n) for \varepsilon > 0 fixed then with high probability the diameter of G(n,p) is less than or equal to k+1. \textbf{Random Regular Graphs and Expanders} Note once p \gg \frac{\log(n)}{n} then with high probability deg(v) \approx (n-1)p for every vertex v in G(n,p) by Chernoff bounds. However, with high probability G(n,p) is not normal and the average degree (n-1)p \to \infty. We want to have a model to generate regular random graphs. Our idea here is to construct them out of permutations. Begin with a permutation \sigma \in S_n chosen uniformly. Then \sigma:[n]\to[n] bijectively. We can then think of \sigma as a random 2 regular graph. The two problems we encounter are fixed points of \sigma and transpositions. Now \expect[\#\text{of fixed points}] = 1 and \prob[\text{no fixed points}] \to \frac{1}{e}. So it's true that the number of fixed points approaches in distribution to P_0(1). Now \expect[\#\text{of transpositions}] = \binom{n}{2}\frac{1}{n(n-1)} = \frac{1}{2}. So we have a small number of bad events that we will be able to control for. Take \sigma_1, \sigma_2,\ldots, \sigma_l to give a 2l-regular graph on [n]. There are two types of bad events we may encounter in this construction. The first happens when \sigma_i (x) = \sigma_j (x) for i \ne j and the second happens when \sigma_i (x) = \sigma_i^{-1} (x) for i \ne j. Note by the previous discussion the expected number of bad events tends to a constant as n \to \infty. Using Poisson approximation one can show that there is a positive probability of having no bad events. Thus to create our 2l-regular graph we just pick our permutations until we have no bad events. Now for some fixed l large enough we want show that with high probability our random regular graph is an expander. That is we wish to show that the Cheeger number h(G) > c. Recall h(G) = \underset{|S| \le n/2}{min}\frac{\# e(S,\bar{S})}{|S|}. It will suffice to show for all F \subseteq [n] with |F| \le \frac{n}{2} that |N(F)| \geq (1+c')|F| for some c' > 0. This will exclude the possibility that there exists F \subseteq F' \subseteq [n] with |F'| \le (1+c')|F| and with all edges in F' ending up in F. Let r = |F|, r + r' = |F'|, and r' = \lfloor c' r \rfloor + 1. Then for each r there are \frac{n!}{r! r'! (n - r - r')!} \le \frac{n^{r + r'}}{(r + r')!}c^r choices for F and F'. Now \prob[\text{all edges of F' end in F}] = \frac{\binom{r + r'}{r}}{\binom{n}{r}} \le \left(\frac{r + r'}{n}\right)^r. Then we know the total probability of failure for some choice of F and F' is at most \left(\frac{r + r'}{n}\right)^{rl}. So by Sterling's approximation the total failure probability is bounded by \displaystyle\sum\limits_{r=1}^{\lfloor n/2 \rfloor} o(1)^r \left(\frac{r + r'}{n}\right)^{lr - r -r'}. So for small enough c we have that \frac{r+r'}{n} \le 0.6 and so for large enough l the whole sum goes to o(1). \begin{defn} Given a graph G(V,E), S \subseteq V is a \underline{vertex cut set} if G(V\setminus S,E) is not connected. A graph G is \underline{k-connected} if there is no cut set of size k-1. The \underline{connectivity number} of G denoted K(G) = max\{k : \text{G is k-connected}\}. \end{defn} Note that we know the threshold for 1-connectedness in G(n,p) is p = \frac{\log(n)}{n}. We will see that the threshold for k-connectedness is p = \frac{\log(n) + (k-1)\log(\log(n))}{n}. \begin{thm} Let p = \frac{\log(n) + (k-1)\log(\log(n))}{n}. Then \begin{displaymath} \prob[G(n,p) \text{ is k-connected}] \to \left\{ \begin{array}{lr} 0 & \text{if } x_n \to -\infty \\ 1 & \text{if } x_n \to \infty \\ e^{e^{c}/(k+1)!} & \text{if } x_n \to c \end{array} \right. \end{displaymath} \end{thm} Note that the probability of G(n,p) being k-connected is approximately the probability that G(n,p) has no vertex of degree k-1. \clearpage \section{(Monday, October 8)} \subsection{The phase transition in G(n,p)} Very roughly, set p=\frac{c}{n}, where c\in (0,\infty) is constant. \begin{itemize} \item If c<1, then w.h.p. largest component has order O(\log{n}). \item If c=1, then w.h.p. largest component has order O(n^{2/3}). \item If c>1, then w.h.p. largest component has order \geq \lambda n, where \lambda=\lambda(c). (aka \emph{giant component}) \end{itemize} Erdos and Renyi called this a \emph{double jump}. Now let's state the theorem in detail following Alon--Spencer. First some notation: \begin{enumerate} \item A connected component is said to have \emph{complexity} e-v+1. (\emph{eg:} a tree has complexity 0, a unicycle has complexity 1) \item C_i=\#i-th largest component, L_i=\# vertices of C_i. (L_1=size of largest component) \end{enumerate} Now the theorem in five parts: \begin{enumerate} \item Very subcritical (p=\frac{c}{n}, c<1) \begin{itemize} \item All components are trees or unicyclic \item L_1=\Theta(\log{n}) \item L_k \sim L_1 for every fixed k \end{itemize} \item Barely subcritical (p=\frac{1-\epsilon}{n}, \epsilon=\lambda n^{-1/3} and assume \epsilon\to 0, \lambda\to \infty) \begin{itemize} \item All components are trees or unicyclic \item L_1=\Theta(\epsilon^{-2}\log{\lambda}) \item L_k \sim L_1 for every fixed k \end{itemize} \item Critical (p=\frac{1-\epsilon}{n}, \epsilon=\lambda n^{-1/3} where \lambda \in (-\infty,\infty) is constant) \begin{itemize} \item Largest k components (k fixed), all have size L_k=\Theta(n^{2/3}) \item Parametrizing, L_k=c_k n^{2/3} and d_k=complexity(c_k); then there is a nontrivial limiting point distribution for (c_1,c_2,\ldots,c_k,d_1,\ldots,d_k) \end{itemize} \item Barely supercritical (p=\frac{1+\epsilon}{n}, \epsilon=\lambda n^{-1/3} and assume \epsilon\to 0, \lambda\to \infty) \begin{itemize} \item L_1 \sim 2\epsilon n \item complexity(C_1)\to \infty \item All other components are trees or unicyclic \item L_2=\Theta(\epsilon^{-2}\log{\lambda})=\Theta(n^{2/3}\lambda^{-2}\log{\lambda}) (Note \frac{L_1}{L_2} \to \infty) \end{itemize} \item Very supercritical (p=\frac{c}{n}, c>1) \begin{itemize} \item L_1 \sim y n where y=y(c) \item complexity(C_1)\to \infty \item All other components are trees or unicyclic \item L_2=\Theta(\log{n}) \end{itemize} \end{enumerate} \subsection{GALTON-WATSON process} Let X be a distribution on \Z_{\geq 0}. Set Z_0=1. Recursively define Z_n=\text{sum of Z_{n-1} i.i.d. copies of X}, for n\geq 1. (in other words, X-offspring distribution, Z_0-root of a tree, Z_n-size of n-th generation) Examples: \begin{enumerate} \item \mathbb{P}(X=c)=1. Then, Z_n=0 if c=0 and Z_n>0 if c>0. \item \mathbb{P}(X=0)=q, \mathbb{P}(X=m)=p ; p+q=1. \\ Question: Does this process continue forever? \\ Answer: p_X-extinction probability =\lim_{n\to\infty}\mathbb{P}(Z_n=0), and if p_X<1, the process continues forever with positive probability. \end{enumerate} Probability generating function of X: f(x)=f_X(x):=\sum_{i=0}^{\infty} \mathbb{P}(X=i) x^i. (eg: f_X(x)=q+px). \begin{thm} \begin{enumerate} \item If \mathbb{E}X\leq 1, then we have p_X=1 (except the degenerate case \mathbb{P}(X=1)=1) \item If \mathbb{E}X> 1 and \mathbb{P}(X=0)>0, then p_X=x_0 where x_0 is the unique solution of f(X)=X in (0,1). \end{enumerate} \end{thm} Continuing on eg: f_X(x)=q+px^m, \mathbb{E}X=mp; then p_X=1 if mp\leq1 and p_X<1 if mp>1 Two \emph{ancient} references: "Probability problems in nuclear chemistry", Schrodinger 1945, "Survival of family names", Galton, Watson (1874) \clearpage \section{(Wednesday, October 10)} Let v_0\in [n] in G(n,p). Explore as follows: \begin{enumerate} \item[] Let v_1,\ldots,v_m be neighbors of v_0 in G(n,p). Mark v_0 as saturated. \item[] Let v_{11},v_{12},\ldots be neighbors of v_1 in [n]\backslash \{v_0\}. Mark v_1 as saturated. \item[] Let S_i be the set of vertices that are labelled, and i+1 is the smallest non-saturated vertex. Look for neighbors of v_{i+1} to [n]\backslash S_i. \end{enumerate} \emph{Equivalent} Galton-Watson process: Z_0=1, Z_{n+1}=Z_n+X-1, where Z_n\sim \{ seen \} \backslash \{ saturated \} and X is a RV on \Z_{\geq 0}. Exploring G(n,p), X_i=\#new neighbors at step i=Bin(n-|S_{i-1}|,p). Note that if S_i is small compared to n, X_i\sim Bin(n,p). \begin{enumerate} \item[(*)] Also note that, if p=\frac{c}{n},c<1, then in GW branching process with offspring distribution Bin(n,p), p_X=1 (extinction probablity) and hence we expect that all components are small. \item[(*)] If p=\frac{c}{n},c>1, then p_X<1 and we might expect large components to appear. \end{enumerate} \begin{thm} Let p=\frac{c}{n},c<1. Then whp, \begin{enumerate} \item L_1\leq \frac{3}{(1-c)^2}\log{n} \item All components are trees or unicyclic. \end{enumerate} \end{thm} We need one more tool: Chernoff bound revisited; Let X=Bin(N,p) and \mu=Np. Then \mathbb{P}(X\geq \mu+t)\leq \exp{\left( \frac{-t^2}{2(\mu+t/3)} \right)} and \mathbb{P}(X\leq \mu-t)\leq \exp{\left( \frac{-t^2}{2\mu} \right)}. \begin{proof}[Proof of (1)] Let v\in[n]. Explore G(n,p). Let X_i=\#vertices discovered at step i. \begin{align*} \mathbb{P}(v \text{ belongs to a component of size}\geq k=k(n) ) &\leq \mathbb{P}(\sum_{i=1}^{k-1}X_i\geq k-1)\\ \intertext{then bound with X_i\leq X_i^+ \sim Bin(n,p),} &\leq \mathbb{P}(\sum_{i=1}^{k-1}X_i^{+} \geq -1)\\ &\leq \mathbb{P}(Bin(kn,p)\geq k-1) \end{align*} Now set p=\frac{c}{n},c<1 and k\geq \frac{3}{(1-c)^2}\log{n}. Take N=kn.\mathbb{E}[Bin(kn,p)]=knp\geq \frac{3\log{n}}{(1-c)^2}c\begin{align*} \mathbb{P}(Bin(kn,p)\geq k-1) &\leq \exp{\left( \frac{-t^2}{2(k\mu+t/3)} \right)} \text{ where } \mu=ck, t=(1-c)k-1 \\ &\leq \exp{\left( \frac{-((1-c)k-1)^2}{2(ck+\frac{(1-c)k}{3})} \right)} \\ &\leq \exp{\left( \frac{-(1-c)^2}{2}k \right)} = O(n^{-3/2})=o(n^{-1}) \end{align*} Summing over all possible choices for v\mathbb{P}\left( \exists \text{ component of size} \geq \frac{3\log{n}}{(1-c)^2} \right)\leq O(n^{-0.5})\to 0$$\end{proof} \begin{proof}[Proof of (2)] By (1), WLOG we may assume that L_1=O(\log{n}). \begin{ex} Any connected graph with e-v+1\geq 2 contains a subgraph (i) two cycles connected by a path, (ii) shares a vertex, (iii) shares common edge(s). \end{ex} For such a connected graph,$$\mathbb{E}(\# \text{copies in } G(n,p))\leq n^{k+l+m}p^{k+l+m+1} \leq (np)^{k+l+m}p \leq c^{k+l+m}p = O(n^{-1}).$$We may assume k,l,m \leq O(\log{n}), so \#choices=O((\log{n})^3)\\ Whp all components have e-v+1<2, hence either is a tree or unicyclic. \begin{ex} If X=Po(c),c>1, what is p_X? \end{ex} \end{proof} \clearpage \section{(Friday, October 12)} Consider X \in P_0 (c) for c > 1. We seek to calculate \rho_X, the extinction probability for the branching process determined by X. We have f_X (x) = \displaystyle\sum\limits_{i=0}^{\infty} \frac{c^i x^i}{i!}e^{-c} = e^{-x} e^{cx} = e^{c(1-x)}. So \rho_X is the unique solution to x = e^{c(x-1)} in the interval (0,1). Let y = 1-x, then our equation becomes 1-y = e^{c y}. Then \rho_X = 1 - \beta where \beta is the unique solution in (0,1) to \beta + e^{-c \beta} = 1. Note that \beta is the survival probability of our branching process. Also note that as c \to \infty we have \beta \to 1. Now let Y_n \in Bin(n,p) for p = \frac{c}{n} and c>1. Consider a sequence of branching processes determined by Y_n. We seek \rho_{Y_n}. Then we have f_{Y_n} (x) = \displaystyle\sum\limits_{i=0}^n \binom{n}{i}p^i (1-p)^{n-i} x^i = \displaystyle\sum\limits_{i=0}^n \binom{n}{i}(px)^i (1-p)^{n-i} = (1 - p + px)^n. Remember p = \frac{c}{n} and let n \to \infty, then f_{Y_n} (x) \to e^{c(x-1)} for every fixed x so \rho_{Y_n} \to 1 - \beta where \beta = \beta(c) is the unique solution of \beta + e^{-c\beta} = 1 in the interval (0,1). In fact the preceding argument holds if we merely have pn \to c as n \to \infty for c>1 fixed. \begin{thm} If p = \frac{c}{n} for c>1 constant, then with high probability L_1 \approx \beta n where \beta \in (0,1) is the unique solution to \beta + e^{-c \beta} = 1 and L_2 \le \frac{16c}{(1-c)^2}\log(n). \end{thm} To prove this we'll let k_- = \frac{16c}{(1-c)^2}\log(n) and k_+ = n^{2/3}. We want to show that G(n,p) has no components of order k for k_- \le k \le k_+. To do this we consider a searching process beginning at a single vertex. Either this process ends in fewer than k_- steps or at the kth step there are at least \frac{(c-1)k}{2} unsaturated vertices. Let X_i be the number of vertices found at step i, and let X_i^- \in Bin(n - \frac{c+1}{2}k_+, p) each X_i^- i.i.d.. Note in order to check if the process starting at v produces after step k at least \frac{(c-1)k}{2} unsaturated vertices we need only identify k_+ \frac{(c-1)k}{2} = \frac{(c+1)k}{2} vertices of this component. Now \prob\left[\text{after k steps we have fewer than \frac{(c-1)k}{2} unsaturated verticies}\right] \le \prob\left[\displaystyle\sum\limits_{i=1}^k X_i^- \le k - 1 +\frac{(c-1)k}{2}\right] \approx Bin(k n, \frac{c}{n}) where \displaystyle\sum\limits_{i=1}^k X_i^- = Bin\left(k(n - \frac{c+1}{2}k^+), \frac{c}{n}\right). Recall now for X \in Bin(N,p) we have \mu = Np and \prob(X < \mu - t) \le e^{-t^2 / 2\mu}. In our case \mu = kn\frac{c}{n} = kc and t = kc - \frac{(c+1)k}{2} = \frac{k(c-1)}{2}. Then \prob[\text{claim fails}] \le \displaystyle\sum\limits_{k=k_-}^{k_+} e^{-((c-1)k)^2/8kc} = \displaystyle\sum\limits_{k=k_-}^{k_+} e^{-(c-1)^2 k/9c} \le k + e^{-(c-1)^2 k_- /9c}. This simplifies to n^{2/3} n^{-16/9}. However this is only for v a vertex in an intermediate size component. Summing over all vertices we have an upper bound on the number of intermediate size components n n^{2/3} n^{-16/9} = n^{-1/9} \to 0 as n \to \infty. Next we will show that there is at most one component of size at least k_+. Suppose the exploring processes starting with v' and v'' both result in a component of size at least k_+. By the previous argument we will have at least \frac{(c-1)k}{2} unsaturated vertices so \prob[\text{no edges between V' and V''}] \le (1-p)^{(c-1)^2 k^2/4} where V' is the unsaturated vertices for the process starting at v' and the same for V'' and v''. However this probability is (1 - \frac{c}{n}) < e^{-c/n} so this probability is at most e^{-c(c-1)^2 n^{1/3} / 4} = o(n^{-2}) \to 0 so there is at most one large component. Now let \rho = \rho(n,p) be the probability that a vertex v is in a small component. We have \rho(n,p) \le \rho_{X'} where X' \in Bin(n - k_-,p). On the other hand \rho_{X''} + o(1) \le \rho(n,p) where X'' \in Bin(n,p). Both \rho_{X'} and \rho_{X''} tend to 1-\beta where \beta + e^{-c\beta} = 1. So we also have \rho(n,p) \to 1-\beta. Now let Y be the number of vertices in small components. Then \expect[Y] \approx (1-\beta)n. In fact it can be show that \expect[Y^2] = (1+o(1))\expect[Y]^2 and \expect[Y^2] = n^2 \rho(n,p)\rho(n-O(k),p). So by Chebyshev's inequality, with high probability Y \approx \expect[Y]. Then by the second moment method the theorem holds. \clearpage \section{Monday, October 22} There are many other kinds of random graphs. \begin{itemize} \item Bernoulli random subgraphs of non-complete graphs \item Sequence of finite graphs G_i with V(G_i) \to \infty \item Infinite graphs, eg. lattice, branching tree, Cayley graphs of an infinite group \item Random regular graphs \item Uniform spanning trees \end{itemize} We are especially interested in random geometric graphs. \subsection{Random geometric graphs} (Ref: M. Penrose: Random Geometric Graphs) \begin{defn} Fix d\ge 2, take n points iid in \R^d according to your favorite distribution, eg. Gaussian, or uniform on a convex body. These n points are your vertices. There is an edge between two vertices x and y if the distance between them is less than r=r(n), that is d(x,y) 0, let N_{\lambda}\in \text{Po}(\lambda), and P_{\lambda} = \lbrace x_1,\ldots,x_{N_{\lambda}}\rbrace be i.i.d. random points. Then P_{\lambda} is a Poisson point process with intensity \lambda. \end{lem} \noindent{\bf Proof of Lemma.} Let A_1,\ldots,A_k be a Borel-set partition of \mathbb{R}^d. Let n_1,\ldots,n_k be positive integers such that n_1+\ldots+n_k = n. Then$$\text{Pr}[P_{\lambda}(A_i) = n_i \ \forall \ i] = \text{Pr}[N_{\lambda}=n]\cdot\text{Pr}[P_{\lambda}(A_i)=n_i \ \forall \ i \ | \ N_{\lambda}=n]$$\hspace*{4.4cm} =\displaystyle\frac{e^{-\lambda}\lambda^n}{n!}\cdot\frac{n!}{n_1!n_2!\ldots n_k!}\cdot\prod_{i=1}^k\left(\int_{A_i}f(x)\text{d}x\right)^{n_i}\\ \\ \hspace*{4.4cm} =\displaystyle\prod_{i=1}^k\frac{\text{exp}\left(-\lambda\int_{A_i}f(x)\text{d}x\right)\left(\lambda\int_{A_i}f(x)\text{d}x\right)^{n_i}}{n_i!}\\ \\ The first part of the second line is because N_{\lambda}\in\text{Po}(\lambda), and then the n points must be partitioned into the A_i. The extra integral in the last line comes from \displaystyle1=\int_{\mathbb{R}^d}f(x)\text{d}x = \sum_{i=1}^k\int_{A_i}f(x)\text{d}x.\\ So the P_{\lambda}(A_i) are independent random variables in Po(\mu_i) with \displaystyle \mu_i=\lambda\int_{A_i}f(x)\text{d}x. Hence P_{\lambda} is a Poisson point process with intensity =\lambda.\\ \\ \noindent{\bf Upshot}: One can prove something about X_n=\lbrace x_1,\ldots,x_n\rbrace as n\rightarrow\infty by proving something about P_{\lambda} = \lbrace x_1,\ldots,x_{N_{\lambda}}\rbrace, N_{\lambda}\in\text{Po}(\lambda) and letting \lambda\rightarrow\infty. ["Poissonization."]\\ \begin{ex} Let X_n be n points i.i.d. uniformly in [0,1]^d, \ d\geq2. Assume r\rightarrow0. What is \mathbb{E}[\# \ \text{of \ triangle \ subgraphs}] in G(X_n,r)? \end{ex} \noindent Let p=\text{Pr}[x_i,x_j,x_k form a triangle], then \mathbb{E}[\# \ \text{of \ triangles}]= {n\choose3} p by linearity of expectation.\\ \\ \hspace*{1cm} p=\text{Pr}[x_i\sim x_j, x_j\sim x_k, x_k\sim x_i]\\ \hspace*{1.3cm} =\text{Pr}[x_i\sim x_j]\cdot\text{Pr}[x_j\sim x_k]\cdot\text{Pr}[x_k\sim x_i \ | \ x_i\sim x_j\sim x_k]\\ \\ This last term is the probability that two points in a unit ball around a point are also at most unit distance apart, and it depends only on the dimension d. Call this probability c_d'. The first two terms are independent, and hence equal, and will be some fixed constant depending on d multiplied by the volume of the ball around a point. So this is c_dr^d for some constant c_d, which depends only on d and the distribution function f.\\ \\ \hspace*{1cm} p\sim (c_dr^d)^2\cdot c_d' \Longrightarrow \mathbb{E}[\# \ \text{of \ triangles}]\sim cn^3r^{2d}, with c=c(d,f)\\ \\ Suppose n^3r^{2d}=1, \ r=n^{\frac{-3}{2d}}:\\ \hspace*{1cm} If r=o(n^{\frac{-3}{2d}}), whp there are no triangles.\\ \hspace*{1cm} If r=\omega(n^{\frac{-3}{2d}}), whp there are lots of triangles.\\ \\ In fact, if n^3r^{2d}\rightarrow c, Penrose shows that the number of triangles is Poisson distributed in the limit. Similarly, \mathbb{E}[\# \ \text{of} \ C_4\text{'s}]\sim cn^4r^{3d}. More generally, in Ch. 3 of Penrose, he shows the following: \begin{lem} Let \Gamma be a connected graph on k\geq2 vertices.\\ Then \ n^{-k}r^{-d(k-1)}\mathbb{E}[\# \ \Gamma \ \text{subgraphs}]\rightarrow\mu, which only depends on \Gamma,d, and f. \end{lem} \clearpage \section{Wednesday, October 31} \subsection{Cleanup discussion} This lecture, we continue our discussion on the random geometric graphs G(X_n; r).\footnote{As a reminder, these graphs are defined by choosing n points according to i.i.d. random variables with a common density function f, then connecting vertices within r = r(n) of each other; r is usually a function of n.} We discussed that the threshold for connectivity of G(X_n, r) depends on the underlying density. For uniform densities on a convex body, the threshold is \disp R \sim C \left( \frac{\log(n)}{n}\right)^{1/d} (somewhat akin to our results for G(n, p)), whereas for the standard multivariate normal distribution, the threshold is \disp R \sim \frac{(d-1)\log(\log(n))}{\sqrt{2\log(n)}} (a much larger threshold radius than the G(n, p) case). These cases, however distinct their bounds, have in common with the standard G(n, p) case that the threshold for connectivity is the \textit{same} as that for the necessary condition of \delta(G) \geq 1 whp as n \to \infty, where \delta(G) stands for minimum degree of G. We cannot surmise, however, that all the properties of G(n, p) carry over to G(X_n; r); the next exercise is a case in point. \begin{ex} Let f be a uniform distribution on a cube, [0, 1]^d, and assume we have G(X_n; r) with underlying distribution f for X_n and r \to 0 as n \to \infty. Show that G(X_n, r) is not an expander graph: as n \to \infty, whp h(G(X-n; r)) \to 0.\footnote{Recall that here, we define \disp h(G) = \min\limits_{\vert S \vert \leq \lfloor \frac{n}{2} \rfloor} \left\lbrace \frac{\# E[S, S^{\complement}]}{\vert S \vert} \right\rbrace.} This is in contrast to the case of G(n, p), since if p is large enough so that whp G(n, p) is connected, then h(G(n, p)) is bounded away from 0 whp. \end{ex} \begin{ex} For comparison, try finding h(G(X_n; r)) on the torus \mathbb{T}^d, again with uniform distribution, and r the constant so that the probability of any two vertices connecting is \disp\frac{1}{2}. \end{ex} \begin{quest} Compare the fixed-r case of G(X_n; r) hinted at above with \disp G\left(n, \frac{1}{2} \right). Look at clique numbers and independence numbers. Weak bounds are possible even with simple estimates; how well can you do? \end{quest} \subsection{Giant components on Infinite Random Geometric Graphs} Again rehashing the same sorts of questions that we did considering characterizations of G(n, p), the next problem is to characterize when a giant component appears in random geometric graphs. Rather than looking at sequences of finite graphs with n vertices as n \to \infty, we choose to look at an infinite graph, instead. To do so, we recall the process cousin to G(X_n; r), the G(P_{\lambda}; r) process. We still connect vertices with mutual distance less than r, but now the points are chosen by a Poisson point process with intensity \lambda, \lambda \in (0, \infty). Recall the salient properties of such a process. \begin{enumerate} \item For any Borel set A \subset \R^{d}, P_{\lambda}(A) := \expect \left\lbrace \# \text{ points in } A \right\rbrace is a Poisson-distributed random variable with mean \lambda \int_A f(x) dx for some measurable, bounded, \textit{density} function f: \R^d \to \R. \item For disjoint Borel Sets A, B, P_{\lambda}(A) and P_{\lambda}(B) are disjoint. \end{enumerate} For today's purposes, we drop the requirement that f is density, so that we can take f \equiv 1; in other words, replace requirement 1 with \begin{enumerate}[label = (\arabic*')] \item For any Borel set A \subset \R^{d}, P_{\lambda}(A) := \expect \left\lbrace \# \text{ points in } A \right\rbrace is a Poisson-distributed random variable with mean \lambda \cdot vol(A), where vol(A) is the volume (Lebesgue measure) of A. \end{enumerate} Therefore, our process will be called \textit{uniform} on \textit{all} of \R^d. We will give this process the special name H_{\lambda}. Note that this process H_{\lambda} will have infinitely many vertices whp. To discuss giant components, it is easier to discuss a particular giant component's emergence than to discuss its existence in general; therefore, we add \vec{0} \in \R^d into our vertex set so that we can talk about the size of the component containing \vec{0}. Therefore, we consider the process G \sim G(H_{\lambda} \cup \left\lbrace \vec{0} \right\rbrace ; 1). That is, we connect vertices separated by a distance strictly less than 1.\footnote{Note that the Poisson point processes have no n \to \infty mechanism, so we cannot let r \to 0. } \begin{defn} For k \geq 1, let p_k(\lambda) := \prob ( \text{the component of } G \text{ containing } \vec{0} \text{ is of order }k). Also define \begin{eqnarray*} p_{\infty} & := & 1 - \sum_{k = 1}^{\infty} p_k (\lambda)\\ & = & \prob ( \text{the component of } G \text{ containing } \vec{0} \text{ is of infinite order.}) \end{eqnarray*} Note that 0's component contains 0, so there is no need for a p_0. Let \lambda_C := \inf \left\lbrace \lambda > 0: p_{\infty}(\lambda) > 0 \right\rbrace. \end{defn} This setup is akin to a model we will discuss later in the course: an infinite lattice, including vertices with uniform probability, and then connecting adjacent lattice points according to the lattice structure. Such a model is called \textit{site percolation}, whose only real difference from our model is that the vertices can only appear at fixed'' positions. Our model, allowing vertices everywhere, is therefore called \textit{continuum percolation}. Our goal today will be to use the following fact. \begin{thm}[Fundamental Result of (Continuum) Percolation] 0 \lneqq \lambda_C \lneqq \infty. \end{thm} This proof can be found in the aptly named reference, \textit{Continuum Percolation} by Meester and Roy (\cite{Meester}). \subsection{Giant components of Random Geometric Subgraphs on Sub-Cubes} M. Penrose, in turn, addressed the question of how this infinite-graph model relates to the limit of finite random geometric graphs with \vert V \vert \to \infty. He writes up this work in Chapters 9 and 10 of \cite{MPenrose}. We now overview this discussion, and attempt to emphasize in what ways we fulfill our strategy of an analogue of the Erd\"{o}s-R\'{e}nyi phase transition at the critical value for the existence of a giant component. \begin{defn} Let H_{\lambda, s} be the restriction of H_{\lambda} to the cube \disp \left[ -\frac{s}{2}, \frac{s}{2}\right]^d. (The parameterization is chosen such that the side-length is s when the parameter is s.) Recall that L_1(G) is the size of the largest component of G a graph. \end{defn} \begin{thm} If \lambda \neq \lambda_{C}, then as s \to \infty,$$s^{-d} L_1 \left( G(H_{\lambda, s}; 1) \right) \to \lambda p_{\infty}(\lambda).$$\end{thm} We interpret this by noting that by our parameterization, s^d is the volume of the cube of the support of the distribution for H_{\lambda, s}. Therefore, we may rewrite the above as saying that$$\frac{L_1 \left( G(H_{\lambda, s}; 1) \right)}{\text{Vol}\left( \left[ -\frac{s}{2}, \frac{s}{2}\right]^d \right)} \to \lambda p_{\infty}(\lambda).$$Again, we have a sub-critical and super-critical regime, depending on the value of \lambda. \begin{enumerate} \item In the supercritical case, \lambda > \lambda_C = \inf \left\lbrace \lambda > 0: p_{\infty}(\lambda) > 0 \right\rbrace, then p_{\infty}(\lambda) > 0 (since the set whose infimum is taken is clearly upward closed; we will elaborate on this point later) and hence$$\frac{L_1 \left( G(H_{\lambda, s}; 1) \right)}{\text{Vol}\left( \left[ -\frac{s}{2}, \frac{s}{2}\right]^d \right)} \to \lambda p_{\infty}(\lambda) > 0.$$Therefore, the largest component has a positive fraction of \textit{all} points in the given cube. This parallels the very supercritical regime on Erd\"{o}s-R\'{e}nyi graphs: if \disp p = \frac{c}{n} for c > 1, then L_1 \sim yn whp, where y is some constant depending on c, so whp \disp \frac{L_1}{n} is a positive constant; i.e., the number of vertices in the given component over the total number of vertices is (whp) at least some positive constant. \item In the subcritical case, \lambda < \lambda_C, then p_{\infty}(\lambda) = 0, so whp$$\frac{L_1 \left( G(H_{\lambda, s}; 1) \right)}{\text{Vol}\left( \left[ -\frac{s}{2}, \frac{s}{2}\right]^d \right)} \to 0.$$This again agrees with the Erd\"{o}s-R\'{e}nyi case: in the very subcritical case, where \disp p = \frac{c}{n} for c < 1, then L_1 is \Theta(\log(n)), and hence the proportion of vertices in the largest component to all vertices is whp bounded by a constant times \disp \frac{\log(n)}{n}, which tends to 0 as n tends to \infty. \end{enumerate} Things are subtler, however, for \lambda = \lambda_C. In particular, p_{\infty}(\lambda) is not known, and our current state of knowledge suggests the following conjecture. \begin{conj} p_{\infty} (\lambda_C) = 0. \end{conj} This is known for continuum percolation on \R^d when either d = 2 or d \geq 19; the inbetween dimensions are unknown.\footnote{Prof. Kahle suggested that the d = 3 case would be considerable work, possibly even to the level of a Fields Medal.} This work (of S. K. Smirnov and others) relies heavily on the rich geometry of certain lattices. In addition, we have even better bounds on the exact size of the largest component in the sub-critical case, and the second-largest component in the supercritical case (but not so large as to be connected). As an aside, since results on L_1 in the Erd\"{o}s-R\'{e}nyi case sometimes involved expression in n and \log(n), the size'' of the graph, here we would expect expressions in the volume of the cube, namely s^d and \log(s^d). Yet \log(s^d) = d \log(s), so up to a constant, we can just write \log(s). \begin{enumerate} \item In the supercritical case, \lambda > \lambda_C, (but below the threshold for connectivity),$$c_1 \leq \frac{L_2(G)}{\log(s)^{d(d-1)}} \leq c_2.$$\item In the subcritical case, \lambda < \lambda_C,$$L_1 \sim c \log(s).$$\end{enumerate} \begin{quest} Can we determine the size of \disp L_1\left( G \left( H_{\lambda_C, s}; 1 \right) \right)? A possible approach might be getting some better estimates by considering \disp L_1\left( G \left( H_{\lambda(s), s}; 1 \right) \right), where \lambda(s) \to \lambda_C as s \to \infty. Presumably, we would take the cases \lambda(s) \nearrow \lambda_C and \lambda(s) \searrow \lambda_C to get computable and tractable bounds. \end{quest} \begin{quest} In the supercritical case, \lambda < \lambda_C, does \disp \lim\limits_{s \to \infty} \frac{L_2(G)}{\log(s)^{d(d-1)}} exist whp? \end{quest} \subsection{Overview of Methods} We do not choose to try to copy the proofs of the above statements here (they are in \cite{MPenrose}), but we will discuss some tools used in the proofs. The results are mostly about Poisson point processes.\footnote{A common abbreviation for Poisson point Process'' is p.p.p.} The first exercise and theorem allow you to regard a lower-probability situation as a subset of a higher-probability situation, akin to the situation for the Erd\"{o}s-R\'{e}nyi random graphs, where if p < p^{\prime}, we could regard G(n, p) as a subgraph of G(n, p^{\prime}). \noindent \textbf{Exercise.} If \lambda \in \text{Po}(\mu) and \lambda^{\prime} \in \text{Po}(\mu^{\prime}) are independent, then \lambda + \lambda^{\prime} \in \text{po}(\mu + \mu^{\prime}). \begin{thm}[Superposition] Let P and P^{\prime} be independent Poisson point processes on \R^d, with intensities g(\cdot), g^{\prime}(\cdot). Then P \cup P^{\prime} is a Poisson point process with intensity (g + g^{\prime})(\cdot). \end{thm} The next theorem allows you to reduce to any sub-intensity'' of a given intensity while maintaining the Poisson-ness of the point process. \begin{thm}[Thinning] Let P be a Poisson point process with intensity g(\cdot). Let p: \R^d \to [0, 1] be measurable. For each point x in P, declare x to be \textbf{accepted} with probability p(x). The new point process, restricting the old process to the set of accepted points, is again a Poisson point process with intensity p*g(\cdot). \end{thm} The next theorem allows you to move homogenous point processes radially, if you scale by the appropriate constant. If you have a \textit{homogenous} Poisson point process H on a region A \subset \R^d of intensity \lambda, and a > 0 is some positive constant, consider the point process aH on aA = \lbrace a \cdot x: x \in A \rbrace defined by scaling the points in H out by the constant a. \begin{thm}[Scaling] If H is a homogeneous, Poisson point process H on a region A \subset \R^d of intensity \lambda, and a > 0 is some positive constant, then aH is also homogenous and Poisson. \end{thm} Finally, for lack of a better position, we mention this result, emphasizing that the giant component should be much larger than all other components. \begin{thm} If \lambda > \lambda_C, then almost surely, G(H_{\lambda}, 1) has a unique infinite component. \end{thm} \clearpage \section{(November 2):} This lecture covers some basic results of percolation theory, following Bollob\'{a}s \& Riordan. The idea is to consider an infinite connected graph \Lambda, and look at properties of random subgraphs. Often, \Lambda will have some symmetry, sometimes including a vertex-transitive automorphism group, as is the case for the lattices \Z^d for d\geq 2 and the d-regular Cayley tree. There are two main perspectives from which to view percolation on a graph: \begin{itemize} \item \emph{Bond percolation}: Each edge (bond) is included (open) with probability p, where individual bonds are independent random variables; all vertices are included. The probability measure on the space of subgraphs is denoted \P^b_{\Lambda,p}, or simply \P_p if \Lambda and b are clear from context. \item \emph{Site percolation}: Each site is included with probability p; the open bonds are those from the induced subgraph on the included sites. The probability measure is denoted \P^s_{\Lambda,p}, or simply \P_p. \end{itemize} The resulting subgraph is denoted \Lambda_p^b (or \Lambda_p^s), or usually \Lambda_p if the type of percolation is clear from context. Note that site percolation is in some sense more general'' than bond percolation since bond percolation on \Lambda is equivalent to site percolation on L(\Lambda), the line graph of \Lambda (ignoring sites in \Lambda^b_p which have no open bonds). Here L(\Lambda) is the graph with a vertex v_e associated to each edge e of \Lambda, and v_e\tilde v_{e'} if and only if e,e' meet at a vertex in \Lambda. It is often convenient to use the natural coupling'' of measures \P^b_{\Lambda,p} with 0\leq p\leq 1, in which \Lambda^b_{p_1} is viewed as a subgraph of \Lambda^b_{p_2} if p_1\leq p_2. In other words, we can think of choosing a subgraph of \Lambda by labeling each edge e with a random value \alpha(e)\in [0,1], and include e in \Lambda_p if p\geq \alpha(e). A similar idea holds for site percolation. We will use the following notation: \begin{itemize} \item For sites x and y, x\rightarrow y means there exists an open path from x to y; \item For a site x, x\rightarrow\infty means there exists an infinite open path starting at x; \item Denote the connected component including x by C_x; \item Write \Theta_x(p) for \P_p(x\rightarrow\infty), the probability that x\rightarrow\infty in \Lambda_p. \end{itemize} Note that for locally finite graphs \Lambda, K\"{o}nig's infinity lemma implies that |C_x|=\infty if and only if x\rightarrow\infty; for this reason, we will assume from now on that \Lambda is locally finite and has countably many vertices. Let x and y be sites in \Lambda at distance d from one another. Then \Theta_x(p)\geq p^d\Theta_y(p), since the right-hand side is the probability that y\rightarrow\infty and the entire length-d path y\rightarrow x is open. This has the following very strong implication: either \Theta_x(p)=0 for all x\in\Lambda, or \Theta_x(p)>0 for all x\in\Lambda. This is true even if \Lambda does not have a vertex-transitive automorphism group, or indeed any symmetry at all; it relies only on the connectedness of \Lambda. Now, for a given x\in\Lambda, clearly \Theta_x(p) is an increasing function of p. Hence for any \Lambda there exists a critical probability p_H\in [0,1] such that \Theta_x(p)=0 when p0 when p>p_H (independent of x). As with p_\infty(\lambda) previously, this says nothing about the behavior of \Theta_x(p) at the critical probabilitiy p=p_H; in general, it is an open problem whether or not \Theta_x(p)=0 when p=p_H, as one might expect. Note that it is possible that p_H=0 or p_H=1 (as an example of the latter case, take \Lambda=\Z). However, for many interesting choices of \Lambda, including for example \Z^d for d\geq 2, 0p_H, then \P_p(E)=1. \end{prop} \begin{proof} First, assume pp_H. Order the edges of \Lambda so that the jth edge corresponds to the random variable X_j. Then E is independent of (X_1,\ldots,X_n) for any n, since existence of an infinite component is unaffected by the inclusion or exclusion of any finite set of edges. Hence E is a tail event, so by Kolmogorov's zero-one law, \P_p(E)=0 or \P_p(E)=1. But for any x, \P_p(E)\geq \Theta_x(p)>0, so in fact \P_p(E)=1. \end{proof} One says that \emph{percolation occurs} if \Theta_x(p)>0; that is, if \P_p(E)=1. Here is one example where p_H is easy to calculate exactly: let \Lambda be the k-branching tree T_k, consisting of a root vertex x with k descendants x_1,x_2,\ldots x_k, each of which has k descendants, and so on (so T_k is an infinite tree where one vertex has degree k and all other vertices have degree k+1). Then in site percolation, \Theta_x(p)=1-p_X, the complement of the extinction probability p_X for a Galton-Watson process with X=\mbox{Bin}(k,p), where the nth step of the Galton-Watson process corresponds to the nth-level descendants of x (those at distance n from x). We know that the critical value of p for that Galton-Watson process is at p=1/k, so p_H=1/k for \Lambda. We can say more, namely that when p=p_H, \Theta_x(p)=0, since extinction occurs with probability 1 at p=1/k. \clearpage \section{(Nov 5, 2012)} \begin{quest} What is the critical probability for bond percolation on \mathbb{Z}^2? \end{quest} Another interesting critical probability is$$p_T = \inf \{ p : \expect_p[ |C_x|] = \infty \} \left( \text{ or } \sup \{ p : \expect_p[ |C_x| ]< \infty \} \right) $$Compare this definition with the previous critical probability we defined$$p_H =\inf \{ p : \Theta_x(p)>0 \} \left( \text{ or } \sup \{ p : \Theta_x(p)=0 \} \right) $$By their definitions, we have p_T \leq p_H. \begin{prop}$$\frac{1}{3} \leq p_T \leq p_H \leq \frac{2}{3}$$\end{prop} Let \Lambda be the \mathbb{Z}^2 lattice. A useful notion is the dual of \Lambda, denoted \Lambda^*, is also a \mathbb{Z}^2 lattice and that each edge in \Lambda corresponds to a unique edge in \Lambda^*. \begin{rem} Let H be a finite connected subgraph of \Lambda with vertex set C. Then there is a unique infinite component, C_\infty, of \Lambda - C. \end{rem} \begin{defn}$$\delta^\infty C = \text{ set of bonds of } \Lambda^* \text{ dual to bonds joining } C \text{ to } C_\infty$$\end{defn} \begin{prop} \delta^\infty C is a cycle with C in its interior \end{prop} Proof. Let \vec{F} be set of C - C_\infty bonds oriented from C to C_\infty. For \vec{f} \in \vec{F}, let f^* be dual edge (oriented \frac{\pi}{2} rotated counterclockwise). Claim: If f^* = \vec{uv}, then there is a unique bond of \vec{\delta^\infty C} leaving v. Set R = \mathbb{Z}^2 - C - C_\infty. Note: There are no C_\infty - R bonds. Suppose abcd is a 1\times1 square with v in the middle and u below. So a \in C and b \in C_\infty. Case 1. d \in C. Then necessarily c \notin R. So c \in C or c \in C_\infty. If c \in C_\infty, then \vec{dc} \in \vec{F} and you leave through the top. If c \in C, then you leave through the right. Case 2. c \in C_\infty. Then d \in R. If d \in C, then you leave through the top. If d \in C_\infty, then you leave through the left. Case 3. c \notin C_\infty. Since c \notin R, we have c \in C. If d \in R, then you leave through the right. We get a contradiction with d \in C_\infty, since we can not get disjoint ac-bd paths on exterior of cycle abcd, by Kuratowski's theorem. This would result in a topological embedding of K_5 into plane. As a consequence of the proposition, either the origin is in an infinite component or some cycle separates 0 from \infty in \Lambda^*. Let \mu_n be the number of self-avoiding walks in \Lambda starting at 0 of length n. We get the following inequality$$2 \cdot 2^n \leq \mu_n \leq 4 \cdot 3^{n-1} $$Now we can prove the proposition. Suppose p<\frac{1}{3}. Let C_0 be the open cluster containing 0. For x \in C_0, there exists an open path from 0 to x. So |C_0| \leq the number of open paths starting from 0 =: X.$$\expect_p[|C_0|]\leq \expect_p[X] = \sum_{n=0} \mu_n p^n \leq 1 + \frac{4}{3} \sum_{n=1}^{\infty} \left(3 p \right)^{n-1} < \infty$$Hence p_T \geq p. Since p was arbitrarily less than \frac{1}{3}, we have p_T \geq \frac{1}{3}. Suppose p > \frac{2}{3}. Let L_k be the path of length k from (0,0) to (k,0) and S be a dual cycle surrounding L_k of length 2l.This forces S to cross the x-axis somewhere between (k+\frac{1}{2},0) and (l-\frac{3}{2},0). Hence there are fewer than l choices for crossing edge e^*. So there are at most l \mu_{2l-1} choices for S. Let Y_k be the number of open dual cycles surrounding L_k. Then \expect_p[Y_k] \leq \sum{l\geq k+2} l \mu_{2l-1} (1-p)^{2l}. Since 3(1-p)<1, this sum converges. So \expect_p[Y_k] \to 0 as k \to \infty. There exists some k such that \expect_p[Y_k] < 1. Let A_k be event that Y_k = 0. Then \prob_p[A_k]>0. Let B_k be event that all k bonds on L_k are open. \prob_p[B_k] = p^k. Since A_k and B_k look at different bonds, the events are independent. Hence \prob_p[A_k \cap B_k]= p^k \prob_p[A_k] >0. There is an infinite open path on the event A_k \cap B_k. So we have positive probability of an infinite open path from 0. Hence p_H \leq p. \begin{rem} Actually it can be shown that \lim_{n\to\infty} \mu_n^{\frac{1}{n}} = \lambda. This \lambda is called the connective constant of \mathbb{Z}^2. We showed that 2 \leq \lambda \leq 3. This method that we did can show that$$\frac{1}{\lambda} \leq p_T \leq p_H \leq 1 - \frac{1}{\lambda}$$It has been shown that 2.62 \leq \lambda \leq 2.68. \end{rem} \begin{ex} Show that \lambda exists. Hint: Show that \mu_{m+n} \leq \mu_m \cdot \mu_n. \end{ex} \clearpage \section{(November 7)} Our bounds for the previous critical probabilities can be improved upon. \begin{thm} p_H = \frac{1}{2}. \end{thm} In 1960's, Harris showed that if p<\frac{1}{2}, then \prob_p(\exists \text{ infinite component} ) = 0. In 1982, Kesten showed that if p > \frac{1}{2}, \prob_p(\exists \text{ infinite component} ) = 1. In fact, it can be showed that at critically, there are no infinite components. Given a k \times (l-1) rectangle, R, in \Lambda = \mathbb{Z}^2, there exists a (k-1)\times l dual rectangle R^h in \Lambda^*. The h corresponds to the horizontal dual rectangle. Let H(R) be event of horizontal crossing in R (i.e. open path from left to right) and let V(R^h) be the event of vertical crossing in R^h. \begin{lem} Whatever the states of bonds in R, exactly one of H(R) and V(R^h) occurs \end{lem} Proof. Consider R \cup R^h as a part of Archimedian tiling of \mathbb{R}^2 by regular octagons and squares. The octagons are around the vertices of the lattice and dual lattice and the squares correspond to the bonds. Color the lattice octagons blue and the dual lattice vertices orange. We color the squares depending on which bond is open. Draw boundary graph between orange and blue regions. This graph has vertices of degree 1 or 2 and the degree 1 vertices occur on corners. Let x,y be vertices along the top and w,z be the vertices along the bottom. So connected component containing x is a path that ends at one of w,y,z. The path from x can not end at z, since path from x always has orange on its left. If x is connected to w, then vertical crossing occurs to the left of x-w path. This is called the left-most crossing. If x is connected to y, then a horizontal crossing occurs to the right of the path. This is called the top-most crossing. \begin{cor} 1)$$\prob_p[H(R)] + \prob_{1-p}[V(R^h)] = 1 $$for any p \in [0,1] and any rectange R. 2) If R is (n+1) \times n, then$$\prob_{\frac{1}{2}}(H(R)) = \frac{1}{2} $$for any n \in \mathbb{N}. 3) If S is n \times n square, then$$\prob_{\frac{1}{2}}(V(S)) =\prob_{\frac{1}{2}}(H(S))\geq \frac{1}{2} $$\end{cor} We will be using the Russo-Seymour-Welsh method to prove Harris' result. The following proof is by Bollobas and Riordan 2006. Let R = [m] \times [2n], m\geq n and S=[n] \times [n]. Let X(R) be the event that there are open paths P_1 and P_2 such that P_1 is a vertical crossing of S and P_2 lies within R and connectes P_1 to right side of R. \begin{lem}$$\prob_p[X(R)] \geq \prob_p[H(R)] \cdot \prob_p[V(S)] \cdot \frac{1}{2} $$\end{lem} Proof. Suppose V(S) holds. Let LV(S) be the left-most open vertical crossing. For every possible path P_1, the event LV(S) = P_1 does not depend on state of bonds of S to right of P_1. Claim: For every possible P_1, we have \prob_p[X(R) | LV(S) = P_1] \geq \frac{1}{2} \prob_p[H(R)]. We get the proof of the claim by symmetry and reflecting P_1 to above square. Let Y(P_1) be the event that P_1 is joined to right side of R. \prob_p[Y(P_1) |LV(S) = P_1] = \prob_p[Y(P_1)] \geq \frac{1}{2} \cdot \prob_p[H(R)] If Y(P_1) holds and LV(S) = P_1, then X(R) holds. This implies that \prob_p[X(R) | LV(S) = P_1]\geq \frac{1}{2} \cdot \prob_p[H(R)] So$$\prob_p[X(R)] \geq \sum_{P_1} \prob_p[X(R) \cap LV(S) = P_1] = \sum_{P_1} \prob_p[X(R) | LV(S) = P_1] \prob[LV(S) = P_1]$$Hence we have$$\prob_p[X(R)]\geq \sum_{P_1} \frac{1}{2} \cdot \prob_p[H(R)] \prob[LV(S) = P_1]=\frac{1}{2} \cdot \prob_p[H(R)] \prob_p[V(S)]$$Let h_p(m,n) =\prob_p[H(R)], where R is an m \times n rectangle. Let h(m,n) = h_{\frac{1}{2}}(m,n). \begin{cor} For n \in \mathbb{N}, we have$$h(3n,2n) \geq 2^{-7}$$\end{cor} We would guess that \lim_{n \to \infty} h(3n,2n) exists since for all n, we have$$ \frac{1}{2^7} \leq h(3n,2n) \leq \frac{1}{2}$$\begin{conj} Does h(a n, b n) \to f(\frac{a}{b}) as n \to \infty? \end{conj} \clearpage \section{November 9} \noindent{\bf Continuing Harris-Kesten: p_H\geq\frac{1}{2}}\\ \noindent Last time: Let R= m\times n rectangle, h_p(m,n):=\mathbb{P}(H(R)), and h(m,n):=h_{\frac{1}{2}}(m,n). It was shown via duality that \ h(n+1,n)=\frac{1}{2} \ \forall \ n\geq1. Then by monotonicity, \ h(n,n)\geq\frac{1}{2} for n\geq1. The next step is to use the Russo-Seymour-Welsh method to go from squares to rectangles. Recall the following lemma and its corollary: \begin{lem} For R an m\times 2n rectangle, m\geq n, and S an n\times n square, let X(R) be the event that a vertical crossing of S intersects a horizontal crossing of R. Then, by symmetry, \mathbb{P}(X(R))\geq\mathbb{P}(H(R))\cdot\mathbb{P}(V(S))\cdot\frac{1}{2}\geq\mathbb{P}(H(R))\cdot\frac{1}{4}. \end{lem} \begin{cor} h(3n,2n)\geq2^{-7}. \end{cor} \noindent{\bf Proof of Corollary.} Let the bottom middle n\times n square be S, the leftmost 2n\times2n square be R_1, and the rightmost 2n\times2n square be R_2. Then let X_1 be the event X(R_1), \ X_2 be the event X(R_2), and X_3 be the event H(S). Then by the lemma, since R_1,R_2 are in fact squares and thus \mathbb{P}(H(R_i)\geq\frac{1}{2}, we have \mathbb{P}(X_1),\mathbb{P}(X_2)\geq\frac{1}{8}. And \mathbb{P}(X_3)\geq\frac{1}{2}. Then \mathbb{P}(X_1,X_2,X_3)\geq\mathbb{P}(X_1)\cdot\mathbb{P}(X_2)\cdot\mathbb{P}(X_3)\geq\frac{1}{8}\cdot\frac{1}{8}\cdot\frac{1}{2}=2^{-7}. \begin{prop} For k\geq3 and all n\geq1, \ h(kn,2n)\geq2^{17-8k} \end{prop} \noindent{\bf Proof of Prop.} Start with a 2n\times M rectangle, R, with M\geq2n. Write M as M=m_1+m_2-2n, where m_1 is measured from the left of the rectangle, and m_2 from the right, so that R_1:=2n\times m_1 and R_2:=2n\times m_2 intersect on a 2n\times2n square, S. Let X_1=H(R_1), \ X_2=H(R_2), and X_3=V(S), so that \mathbb{P}(H(R))\geq\mathbb{P}(X_1,X_2,X_3)\geq\mathbb{P}(X_1)\cdot\mathbb{P}(X_2)\cdot\mathbb{P}(X_3). So h(m_1+m_2-2n)\geq h(m_1,2n)\cdot h(m_2,2n)\cdot\frac{1}{2}. In particular, for m=m_1\geq2n, 3n=m_2, \ h(m+n,2n)\geq h(m,2n)\cdot h(3n,2n)\cdot\frac{1}{2}\geq2^{-8}\cdot h(m,2n). Hence for m+n=kn, k\geq3,$$h(kn,2n)\geq 2^{-8}\cdot h((k-1)n,2n)\geq\ldots\geq2^{-7-8(k-3)}=2^{17-8k}$$In particular, h(6n,2n)\geq2^{-31}. \begin{ex} Show that for constants a and b, there exists h_{a,b}, a constant depending only on a,b, such that h(an,bn)\geq h_{a,b} > 0. \end{ex} \begin{rem} The conjecture here is that \displaystyle\lim_{n\rightarrow\infty}h(an,bn) exists and is > 0 \ \forall \ a,b. \end{rem} \noindent Another approach to proving the proposition is to use the construction X from the lemma. Here, let M=m_1+m_2-n with m_1,m_2 intersecting on the middle n coordinates, and so S is the bottom n\times n square in this intersection. Let X_i=X(R_i) for i=1,2, and let X_3=H(S). Then \mathbb{P}(X_i)\geq h(m_i,2n)\cdot\frac{1}{4}, \mathbb{P}(X_3)\geq\frac{1}{2}. So h(m_1+m_2-n,2n)\geq h(m_1,2n)\cdot h(m_2,2n)\cdot2^{-5}. Hence$$h(5n,2n)\geq h(3n,2n)^2\cdot2^{-5}\geq2^{-19}h(6n,2n)\geq h(5n,2n)\cdot h(2n,2n)\cdot2^{-5}\geq2^{-19}\cdot\frac{1}{2}\cdot2^{-5}=2^{-25} > 2^{-31}$$\begin{defn} Recall that C_0 is the open cluster containing the origin. Let r(C_0)=\max\lbrace d(x,0) : x\in C_0\rbrace, where d(x,0) is the graph distance, and not the shortest distance through the open cluster. \end{defn} \begin{thm} (Harris) \Theta(\frac{1}{2})=0. In fact, \mathbb{P}_{\frac{1}{2}}(r(C_0)\geq n)\leq n^{-c} for some absolute constant c > 0. \end{thm} \noindent{\bf Proof of Theorem.} When looking at the dual lattice \Lambda^*, the edge e^* is open iff e is closed. Let A_k be the square 6N\times 6N annulus, with N=4^k, centered on the origin. Let E_k be the event that A_k contains an open cycle in \Lambda^*, so that E_k\Rightarrow r(C_0)\leq4^{k+1}. Then A_k is covered by the four 6N\times2N rectangles. Hence \mathbb{P}(E_k)\geq\mathbb{P}(all four 6N\times2N rect's have longways crossing)\geq h(6N,2N)^4\geq 2^{-100}. Let \epsilon=2^{-100} > 0. So \mathbb{P}(r(C_0)\geq4^{l+1})\leq(1-\epsilon)^l. To relate this back to n, let n=4^{l+1} \Rightarrow l=\frac{\log(n)-\log(4)}{\log(4)}\geq\frac{\log(n)}{2}, for large n. Then$$1-\epsilon < 1 \Rightarrow (1-\epsilon)^l\leq(1-\epsilon)^{\frac{\log(n)}{2}} = n^{\frac{\log(1-\epsilon)}{2}}, \ \text{with} \ \frac{\log(1-\epsilon)}{2}=-c$$For small \epsilon, \ \log(1-\epsilon)\sim-\epsilon\Rightarrow c\sim2^{-101}. \begin{rem} \mathbb{P}_{\frac{1}{2}}(H(S))\leq n\cdot\mathbb{P}_{\frac{1}{2}}(r(C_0)\geq n) by union bound, since H(S) implies that some point on the left of S is connected to some point on the right, creating a path of length at least n. Hence \mathbb{P}_{\frac{1}{2}}(r(C_0)\geq n)\geq\frac{1}{2n}. \end{rem} Then \frac{1}{2n}\leq\mathbb{P}_{\frac{1}{2}}(r(C_0)\geq n)\leq n^{-c}\Longrightarrow 2^{-101} < \displaystyle\frac{\log[\mathbb{P}_{\frac{1}{2}}(r(C_0)\geq n)]}{\log(n)}\leq 1.\\ \\ Which leads to the following question:\\ \\ \begin{quest} Does \displaystyle\lim_{n\rightarrow\infty}\frac{\log[\mathbb{P}_{\frac{1}{2}}(r(C_0)\geq n)]}{\log(n)} \ exist? \end{quest} \clearpage \section{(Wednesday, November 14)} \textbf{Goal} Prove Harris-Kesten Theorem$$p_H(\mathbb{Z}^2)=\frac{1}{2}$$(Harris showed that p_H(\mathbb{Z}^2)\geq\frac{1}{2}, and Kesten proved that p_H(\mathbb{Z}^2)\leq\frac{1}{2}, see Chapter 2 of BR book.)\\ \textbf{Probability Preliminaries} \begin{itemize} \item[--]Margulis(1974)-Russo(1981) Formula \item[--]Friegat Kata Theorem 1998) \end{itemize} 1. MR formula\\ Let Q^n=n dimensional cube=boolean lattice (w_1,\cdots,w_n) where each w_i=0 or 1, and let Q_p^n= probability measure on Q^n, where p=(p_1,\cdots,p_n) and each coordinate is 1 with probability p_i and 0 with probability 1-p_i (i.i.d).\\ Let A= increasing event (i.e. x\in A,\,y\geq x, then y \in A)\subseteq Q^n (up-set)\\ Let w\in Q^n, then w_i, ith coordinate variable of w is pivotal for A iff precisely one of w=(w_1,\cdots,w_n) and r_i(w):=(w_1,\cdots,w_{i-1},1-w_i,w_{i+1},\cdots,w_n) is in A.\\ \textbf{Influence of ith variable on A }\\ Let \beta_i(A):=\beta_{p,i}(A)= \mathbb{P}_ p(w_i is pivotal for A), where \mathbb{P}_p(A) is a function of p. (In fact, it is a polynomial, hence smooth.)\\ \begin{lem} (MR)$$\frac{\partial}{\partial p_i}\mathbb{P}_p(A)=\beta_i(A) $$\end{lem} \begin{lem}(FK 1996, Proc. AMS) Every monotone graph property has a sharp threshold'' \end{lem} But, containing K_4 subgroup property is not' sharp. Let A be an increasing subset of Q^n_p with \mathbb{P}_p(A)=t. \\ If \beta_i(A)\leq \delta for every i, then$$\sum^{n} _{i=1}\beta_i(A)\geq Ct(1-t)\log\frac{1}{\delta},$$where c>0 is an absolute constant.\\ Let E be an event (eg. H(r)=\exists horizontal open coring of m\times n rectangle R.) e is a pivotal for E in configuration w iff w^+ is in E and w^- is not in E, where w^+ agrees with everywhere except possible at e_j included and w^- agrees with everywhere except possible at e_j excluded.\\ Let I_p(e,E)=\mathbb{P}_p(e is pivotal for E). \\ If E is increasing, I_p(e,E)=\mathbb{P}_p(w^+ \in E\text{ and } w^- \in E). \begin{lem} Let R=m\times n rectangle in \mathbb{Z}^2 and e be a bond in R. Then,$$I_p(e,H(R))\leq 2\mathbb{P}_{\frac{1}{2}} (r(C_0)\geq\min(m/2-1,\frac{n-1}{2})$$for all 0\frac{1}{2}, and let k\geq 1 be fixed. Then, \exists \gamma =r(p)>0 and n_0=n_0(p,k) such that h_p(kn,n)\geq 1-n^{-r} for all n\geq n_0. \end{lem} \clearpage \section{(Friday, November 16)} \subsection{Kesten's theorem} If p>\frac{1}{2}, then \mathbb{P}_{\vec{p}}(E_{\infty})=1. \begin{lem} Let p>\frac{1}{2} and k\geq 1 be fixed. Then \exists \gamma=\gamma(p)>0, and n_0=n_0(p,k) such that h_p(kn,n)\geq 1-n^{\gamma}. \end{lem} (Recall that h_p(kn,n)\geq h_k > 0 for every n\geq 1.) \begin{proof} By previous results, we have \mathbb{P}_{1/2}(r(C_0)\geq n)\leq n^{-c}. By lemma,$$I_{p'}(e,H(R))\leq n^{-a}=\gamma$$for some absolute constant a, for every bond e of R and p'\in[1/2,p]. Write f(p'):=\mathbb{P}_{p'}(H(R)). By Friedgut-Kalai, we have$$\sum_{e\in R} I_{p'}(e,H(R)) \geq c f(p') (1-f(p')) \log{(1/\delta)},$$for some absolute constant c>0, for all p'\in[1/2,p]. By MR, this sum is the derivative of f(p') with respect to p'. Write g(p'):=\log{\left( \frac{f(p')}{1-f(p')} \right)}. Then$$\frac{d}{dp'}g(p')=\frac{}{f(p')(1-f(p'))} \frac{d}{dp'}(f(p')) \geq c \log{(1/\delta)}=ac\log{n}.$$Taking n large enough, we have g(p)\geq ac(p-\frac{1}{2})\log{n}+g(\frac{1}{2}), where the second term is bounded below by some constant. Hence g(p)\geq \frac{ac(p-\frac{1}{2})\log{n}}{2}. Now$$g(p)=\log{\left( \frac{f(p)}{1-f(p)} \right)} \geq \frac{ac(p-\frac{1}{2})\log{n}}{2},$$so$$\frac{f(p)}{1-f(p)}\geq e^{\frac{ac(p-\frac{1}{2})\log{n}}{2}} \Rightarrow f(p)\geq \frac{n^{ac(p-\frac{1}{2})/2}}{1+n^{ac(p-\frac{1}{2})/2}}\geq 1-n^{ac(p-\frac{1}{2})/2}.$$\end{proof} \begin{thm}[Kesten] If p>1/2, then \mathbb{P}_p(E_{\infty})=1. (E_{\infty}: event that there exists an infinite open cluster) \end{thm} \begin{proof} Fix p>1/2. Let \gamma=\gamma(p)=ac(p-\frac{1}{2})\frac{1}{2} and n_0=n_0(p,k) be as before. Assume n\geq n_0. Let k=0,1,2,\ldots and R_k be the rectangle where bottom-left corner at 0, and 2^kn \times 2^{k+1}n is k is even, and 2^{k+1}n\times 2^kn if k is odd. Let E_k be the event that R_k is crossed the long way by an open path. Any two E_k, E_{k+1} meet. So if all E_k's hold, so does E_{\infty}. Apply union bound:$$\sum_{k\geq 0} \mathbb{P}_p (E_k \text{ fails})\leq \sum_{k\geq 0} (2^kn)^{-\gamma} = \frac{n^{-\gamma}}{1-2^{-\gamma}} < 1,$$for large enough n. So \mathbb{P}_p(E_{\infty})>0. By Kolmogorov 0-1 law, \mathbb{P}_p(E_{\infty})=1. \end{proof} \begin{ex} Show that 0<\mathbb{P}_H(\mathbb{Z}^d)<1 for every d\geq 3. \end{ex} \clearpage \section{(November 19)} \begin{quest} What is the notion of higher dimensional percolation \end{quest} This lecture is based on the paper \textit{On a sharp threshold transition from area law to perimeter law''} by Aizenman, Chayes, Chayes, Fr\"{o}hloh, Russo 1983. Take the complete lattice \mathbb{Z}^3 sites and bonds alike. Square plaquettes appear i.i.d. with probability p. Consider (M \times N) rectangular loops \gamma in lattice plane. Let W_\gamma be the event that \gamma is a boundary of some subset of plaquettes. If X is a collection of 2-dimensional plaquettes, then \delta X is collection of all bonds in an odd number of squares in X. So W_\gamma is an monotone increasing event as p increases. We get the following bounds on the probability of W_\gamma.$$p^{M \cdot N} \leq \prob_p[W_\gamma] \leq \left( 1 - \left(1-p\right)^4\right)^{2(M-1) + 2(N-1)} \leq \left(4 p\right)^{2(M-1) + 2(N-1)}$$We get the lower bound since if all plaquettes are present within the loop, then W_\gamma holds. We get the upper bound from needing at least one of the four possible plaquettes needs to be turned on for each bond in \gamma. We disregard the corners because we want independent events. Another way to write the previous inequality is$$p^{\text{Area}(\gamma)} \leq \prob_p[W_\gamma] \leq \left(4p\right)^{\text{Perimeter}(\gamma)-4}$$This implies that there are some absolute constants c_1, c_2 >0 such that for any \gamma, we have$$\exp\left(-c_1 \text{Area} \right) \leq \prob_p[W_\gamma] \leq \exp \left( -c_2 \text{Perimeter} \right) $$This plaquette model is dual to bond percolation on the \mathbb{Z}^3 lattice. If p_c is the critical probability for bond percolation in \mathbb{Z}^3, then we would expect some sort of transition to occur at 1-p_c in the plaquette model. \begin{thm}$$\prob_p[W_\gamma] \sim \left\{ \begin{array}{lr} \exp\left(-\alpha(p) A(\gamma)\right) & : p>1-p_c\\ \exp\left(-c(p) P(\gamma) \right)& : p<1-p_c \end{array} \right .$$where \alpha, c are positive constants depending only on p \end{thm} The previous \sim means that \frac{\log\left(\prob[W_\gamma]\right)}{A(\gamma)} \to - \alpha as A(\gamma) \to \infty. \begin{quest}$$\lim_{p\to 1-p_c^+} \alpha(p) = 0?$$\end{quest} This is known as the surface tension at critically. \begin{quest} What is the right notion of plaquette percolation? What corresponds to an infinite object when p>1-p_c but not when p<1-p_c? \end{quest} \begin{quest} Also what happends when p=\frac{1}{2} in \mathbb{Z}^4 for 2-dimensional paquettes? \end{quest} This system is self-dual, so we would expect transition occurs at p=\frac{1}{2} Let D(0,y) be the chemical distance in the random graph in lattice and let |y| denote the graph distance from 0 to y. Antal,Piszhora (1996) in \textit{On chemical distances in supercritical Bernoulli percolation} show that if 0 and y are in the same component, then$$\frac{D(0,y)}{|y|} \leq \rho(p,d) with probability tending to 1 as |y| \to \infty \clearpage \section{Monday, November 26} \textbf{Goal:} Proving the uniqueness of infinite open cluster. In Aizenmann-Kesten-Newman Theorem this holds under mild conditions. \begin{lem} Let \Lambda be a connected, locally finite, finite type ( V(\Lambda) has finitely many orbits under aut(\Lambda)), infinite graph. Let E \subset \{0,1\}^{V(\Lambda)} be an automorphism invariant event. Then \prob^s_{\Lambda,p}[E]=\prob[E]\in \{0,1\}. \end{lem} \begin{proof} Fix \epsilon >0. Since E is measurable, there exists an event E_F which only depends on the states of finitely many sites F, and such that \prob(E \Delta E_F) \le \epsilon. (Exercise!). Let x_0\in V(\Lambda), and let $M=\max\{d(x_0,y): y\in F\} .$ Since \Lambda is locally finite $B_{2M}(x_0)=\{z: d(x_0,x) \le 2M\}$ is finite. Let x be a site equivalent to x_0 (x and x_0 are the same type) such that d(x,x_0)>2M. Let \varphi(x_0)=x. For y \in F, we have \begin{align*} d(x_0,\varphi(y)) & \ge d(x_0,\varphi(x_0))- d(\varphi(x_0),\varphi(y))\\ & = d(x_0,x)-d(x_0,y)\\ & >2M-M=M, \end{align*} so \varphi(y) \not \in F. Since F\cap \varphi(F)=\emptyset, the events E_F and E_{\varphi(E_F)} are independent. Then, $\prob[E_F \cap \varphi(E_F)] = \prob[E_F]\prob[\varphi(e_f)] = \prob[E_F]^2.$ Since \prob[A]-\prob[B]\le \prob[A\Delta B] we have \begin{align*} \left |\prob[E]-\prob[E_F]^2\right | &= \left| \prob[E\cap E]-\prob[E_F\cap\varphi(E_F)] \right|\\ &\le \prob[(E\cap E)\Delta (E_F\cap \varphi(E_F))] \end{align*} For any sets A,B,C,D $(A\cap B) \Delta (C \cap D) \subset (A \Delta C) \cup (B\Delta D).$ So, \begin{align*} |\prob[E]-\prob[E_F]^2| & \le \prob[E\Delta E_F]+ \prob[E\Delta\varphi(E_F)] \\ &= \prob[E\Delta E_F]+ \prob[\varphi(E)\Delta\varphi(E_F)] \text{ (E is automorphism invariant)}\\ &= 2\prob[E \Delta E_F] \le 2\epsilon \end{align*} Since |\prob[E_F]-\prob[E]| \le \prob[E\Delta E_F] \le \epsilon we have $\prob[E]-\prob[E]^2 \le \left|\prob[E]-\prob[E]^2\right| \le \left|\prob[E]-\prob[E_F]^2\right| +\left|\prob[E_F]^2-\prob[E]^2\right|\le 2\epsilon+2\epsilon=4\epsilon .$ Since \epsilon is arbitrary, we have \prob[E]-\prob[E]^2 =0, so \prob[E]\in \{0,1\}. \end{proof} \begin{lem} Let \Lambda be a connected, infinite, locally finite,finite type graph. Let p\in (0,1). Then either \begin{itemize} \item \prob[I_0]=1, or \item \prob[I_1]=1, or \item \prob[I_{\infty}]=1, \end{itemize} where I_k is the event that there are exactly k infinite ope clusters. \end{lem} \begin{proof} Fix x_0\in V(\Lambda). Let 2\le k< \infty. Assume \prob[I_k]>0. Let $T_{n,k}:= I_k \cap \{\text{ every infinite cluster intersects the ball } B_n(x_0) \}.$ Note that I_k=\cup_{n\ge 1} T_{n,k} since \cup_{n\ge 1} B_n(x_0)=V(\Lambda). If we assume \prob[I_k]>0, then \prob[T_{n,k}]>0 for some n. Also T_{n,k} is the union of disjoint events $T_{n,k,\vec{s}} = T_{n,k}\cap \{S=\vec{s}\}$ where S denotes the state of sites in B_n(x_0). So, there is an \vec{s} such that \prob[T_{n,k,\vec{s}}] is positive. If w\in T_{n,k,\vec{s}}, let w' be the configuration obtained by changing the closed sites in \vec{s} to open. Then w'\in I_1, so \begin{align*} \prob[I_1] &\ge \prob[\{w': w \in T_{n,k,\vec{s}}\}]\\ &\ge \left(\frac{p}{1-p}\right)^c\prob[T_{n,k,\vec{s}}]>0, \end{align*} where c denotes the number of closed sites in \vec{s}. By previous lemma, if \prob[I_k]>0 for some 2 \le k <\infty then $\prob[I_1]=\prob[I_k]=1,$ so I_1\cap I_k =\emptyset. \end{proof} \begin{lem} let G be a finite graph with k components. Let $L \subset V(G), \ C=\{c_1,\dots,c_s\} \subset V(G), \text{ and } L\cap C =\emptyset$ such that at least one c_i is in each component of G and deleting C_i disconnects its component into smaller components, at least m_i\ge 2 of which contain vertices of L. Then, $|L| \ge 2k+\sum_{i=1}^s (m_i-2).$ \end{lem} \begin{proof} Suffices to assume G is connected, i.e., k=1. Removing an edge only increases the number of components of G-c_i, so assume G is minimal wrt G being connected and containing C\cup L. G is a tree, all leaves are in L. But for a tree $\text{number of leaves}= 2+\sum_{v}d(v)-2$ where the sum is taken over all internal vertices. \end{proof} \clearpage \section{(Wednesday, Nov. 28)} \subsection{Amenability.} Today, we will discuss the Aizenman-Kesten-Newman Theorem. We begin by making a variation on a very standard definition. \begin{defn} \begin{enumerate} \item As usual, if X is some metric space, and x \in X, let B_n(x) denote the open balls of radius n centered at x. \item Similarly, let S_n(x) denote the sphere of radius n; i.e., those points exactly n units from x. \item Say that an infinite, locally finite graph is \textit{amenable} if for all x \in X, \frac{\vert S_n(x) \vert}{\vert B_n(x) \vert} \to 0 \quad \text{ as } n \to \infty.$$\end{enumerate} \end{defn} Compare this definition to the definition of an amenable group. Recall (see, e.g., \cite{Folland}, Section 11.1) that every locally compact (Hausdorff) group G has a left-invariant measure, called a Haar measure, that is unique up to constant multiplication. We will use \lambda to refer to one such measure. Recall a piece of notation: for S a subset of a group G and x \in G, xS := \left\lbrace x \cdot s: s \in S \right\rbrace. \begin{defn} A locally compact group G is \textit{amenable} provided that for every compact K \subset G and for all \epsilon > 0 one can find a set U \subset G with 0 < \lambda(U) < \infty with the property that for all x \in K,\footnote{Recall that \Delta denotes the symmetric difference of sets.}$$\frac{\lambda(U \Delta xU) }{\lambda(U)} < \epsilon.$$\end{defn} In other words, no matter how large a compact set of shifts is, there is a finite-measure set that is moved very little by it. For example, we can take G = (\mathbb{Z}, +) with the usual discrete topology and counting measure, and for any K \subset [-n, n] and for any \epsilon > 0, let N = \left\lceil \frac{n}{\epsilon} \right\rceil + 1 and U = [-N, N].\footnote{Recall that \lceil x \rceil is the ceiling function, the least integer greater than or equal ot x.} Then for all x \in K, \vert x \vert < n, so$$\frac{\lambda(U \Delta (x + U))}{\lambda(U)} \leq \frac{2n}{2N + 1} < \frac{n}{N} \lneqq \epsilon.$$In short, the set does not get moved because it does not have a large boundary. In fact, this correspondence with the isoperimetric inequality'' formulation of amenability of graphs is not accidental. \begin{thm} A locally compact (Hausdorff) group G is amenable if and only if every Cayley graph is amenable as a graph. \end{thm} Sadly, the only place online where I can find a reference is the statement on a conference website, \cite{NagniSapiOne} (with a slightly more restrictive definition of amenable graph). \subsection{Theorem} Recall that I_k denotes the event that there are exactly k infinite clusters in a random graph, where 0 \leq k \leq \infty. For convenience, we declare I_{\geq k} to denote the event that there are at least k infinite clusters. Also recall that for \Lambda a (countably?) infinite graph, \prob^s_{\Lambda, p} denotes the site-percolation on \Lambda where vertices are included with probability p. We now come to the main theorem. Rather than the original proof, we follow the proof of Burton and Kane (1989), as discussed in \cite{BollabRior}. \begin{thm}[AKN, 1987] Let \Lambda be a connected, locally finite, finite type, infinite, amenable graph. Let 0 < p < 1. Then \begin{equation} \text{either } \prob^s_{\Lambda, p}(I_0) = 1 \text{ or }\prob^s_{\Lambda, p}(I_1) = 1. \end{equation} \end{thm} Recall from last time that using all the assumptions except amenability, we get the weaker statement \begin{equation} \prob^s_{\Lambda, p}(I_0) = 1, \prob^s_{\Lambda, p}(I_1) = 1, \text{ or } \prob^s_{\Lambda, p}(I_{\infty}) = 1. \end{equation} Therefore, we must rule out the possibility of infinitely many infinite-size components.\footnote{This can happen, for example, when \Lambda = F_2, the free group/graph on two generators.} To do so, we must use a technical lemma on cut-sets of vertices and the sets they separate. \begin{lem} Let G be a finite graph with k components. Suppose that there exists L \subseteq V(G), and C = \left\lbrace c_1, c_2, \dotsc, c_s \right\rbrace \subseteq V(G), with the following properties: \begin{enumerate} \item L \cap C = \emptyset \item at least one c_i is in each component of G, \item for each i, 1 \leq i \leq k, c_i is a cut--vertex, and the graph induced from G with vertex-set V(G) \setminus \left\lbrace c_i \right\rbrace disconnects its component into smaller components, m_i \geq 2 of which contain vertices of L. \end{enumerate} Then \disp \vert L \vert \geq 2k + \sum_{i = 1}^s (m_i - 2). \end{lem} \subsection{Proof of the AKN Theorem} We will demonstrate that \prob^s_{\Lambda, p}(I_{\infty}) = 0 in the amenable case by showing that \prob^s_{\Lambda, p}(\cup_{k \geq 3} I_k) = 0. By the above, \prob^s_{\Lambda, p}(I_2) = 0 already, so this suffices. Our proof is by contradiction; suppose that \prob^s_{\Lambda, p}(\cup_{k \geq 3} I_k) \gneqq 0. Fix x_0 \in V(\Lambda). Let X_0 \subset V(\Lambda) be the set of vertices equivalent to x_0 under automorphisms.\footnote{i.e., y \in X_0 if and only if there exists \phi \in \mathrm{Aut}(\Lambda) with \phi(x_0) = y.} Recall by the locally-finite assumption that there are only finitely many such equivalence classes. Since \Lambda is connected, we have that V(\Lambda) = \cup_{r \geq 1} B_r(x_0); that is, the vertex-set is covered by various metric balls centered at x_0. Since \prob^s_{\Lambda, p}(\cup_{k \geq 3} I_k) \gneqq 0 by assumption, there is a large enough r such that with positive probability, B_r(x_0) contains sites from at least 3 infinite open clusters (since if this did not hold, with high probability no ball would contain vertices of three open clusters, and by the covering property, the graph would not have as many as three infinite open clusters). Fix one such r, and let T_r(x) be the event that both of the following occur: \begin{enumerate} \item Every site in B_r(x) is open. \item There exists an infinite cluster, O, such that when all the sites in B_r(x) are clused, O is disconnected into at least three infinite open clusters. \end{enumerate} \begin{figure} \centerline{\includegraphics[scale=.50]{ThreeInfty}} \caption{Illustration of T_r(x)} \label{fig:Threeinfty} \end{figure} An illustration is given in Figure~\ref{fig:Threeinfty}. \begin{prop} \prob (T_r(x_0)) =: a > 0. In fact, for all sites x \in X_0, we have \prob(T_r(x)) = a for some a > 0. \end{prop} \begin{proof} First, note that since every x \in X_0 is moved by graph automorphisms to x_0, we have \prob(T_r(x)) = \prob(T_r(x_0)) for all x \in X_0. Thus, we immediately reduce to the situation at x_0. B_r(x_0) contains sites from at least 3 infinite open clusters with nonzero probability by assumption. Further, every configuration in \cup_{k \geq 3} I_k creates a new configuration in T_r(x_0) by changing all the sites in B_r(x_0) to open.\footnote{Since every site is forced open, we create a single open cluster O from the infinite open clusters we had before. If then every site in the ball were converted to closed, the remaining parts of the three (or more) infinite open clusters would remain open and infinite; thus, O would be disconnected into three or more pieces.} Unfortunately, the map is not injective, and also not necessarily measure-preserving. We must, therefore, determine how the map works with respect to the measure. To be precise, let f be the map of configurations of \Lambda, that switches every site in B_r(x_0) to open. This map is clearly 2^{\vert B_r(x_0) \vert} : 1. By the above, f maps \cup_{k \geq 3}I_k inside T_r(x_0), so we wish to show that f maps positive-measure sets to positive-measure sets. Further, for all of the configurations 2^{\vert B_r(x_0) \vert} of B_r(x_0), switching all closed vertices to open changes the probability by a multiplicative factor of \disp \left( \frac{p}{1-p} \right)^{m} , where 0 \leq m \leq \vert B_r(x_0) \vert denotes the number of closed vertices. Therefore, if p \geq \frac{1}{2}, then for all subsets E of the configurations of \Lambda, \prob(f(E)) \geq \prob(E). If p < \frac{1}{2}, then \prob(f(E)) \geq \disp \left( \frac{p}{1-p} \right)^{\vert B_r(x_0) \vert} \prob(E), since at worst \vert B_r(x_0) \vert many switches from closed to open occur for any element of E. \end{proof} To continue the main proof, for any n \geq r, let W = W(n) be a subset of X_0 \cap B_{n-r}(x_0) maximal with respect to the property that the balls \left\lbrace B_{2r}(w): w \in W \right\rbrace are disjoint. Therefore, by maximality, if w^{\prime} \in X_0 \cap B_{n-r}(x_0), and w^{\prime} \not\in W, there exists w_1 \in W with d(w, w^{\prime}) < 4r.\footnote{Otherwise, we could adjoin w^{\prime} to W, and the open, radius-2r balls around each point would be disjoint, since the minimum distance between w^{\prime} and any other w is 4r; this is just a standard triangle-inequality argument. Yet this would violate maximality of W.} Now, as \Lambda is connected and of finite type, there exists a constant \ell such that every site is within a distance \ell of a site in X_0; else, the sequence of points farther and farther from sites in X_0 would of necessity be in different equivalence classes under automorphism, violating the finite-type assumption. Therefore, if we now set n \geq r + \ell, every y \in B_{n - r - \ell}(x_0) is within \ell units of some w^{\prime} \in X_0 \cap B_{n - r}(x_0).\footnote{The membership in X_0 follows from the previous sentence; the membership in B_{n -r}(x_0) follows from the triangle inequality.} Therefore, since w^{\prime} is either a member of W or within 4r of a member of W, y is strictly less than 4r + \ell units away from some w \in W. Therefore, for n \geq r + \ell, the balls \cup_{w \in W} \left\lbrace B_{4r + \ell}(w) \right\rbrace cover B_{n - r - \ell}(x_0). By a simple counting argument, then (and noting that all elements in W are elements of X_0, hence have the same type as x_0, so that the cardinality of given-radius balls around any w \in W \subset X_0 have the same cardinality as a same-sized ball around x_0),$$| W | \geq \frac{\vert B_{n - r - \ell}(x_0) \vert}{\vert B_{4r + \ell}(x_0) \vert}.$$Yet we also have, by \Lambda locally finite and of finite type, that \disp \Delta = \max\limits_{v \in V(\Lambda)} \lbrace \mathrm{deg}(v) \rbrace < \infty. Therefore, we also have by a naive counting argument that$$\vert B_{n + 1}(x_0) \vert \leq \vert B_{n - r - \ell} \cdot \left( 1 + \Delta + \Delta^2 + \dotsb + \Delta^{r + \ell + 1}\right)$$Putting the inequalities together, we have that there exists some c \geq 0 such that for all n \geq r + \ell, \vert W \vert \geq c \cdot \vert B_{n + 1}(x_0) \vert . For such n, then,$$\vert W \vert \geq c \cdot \frac{\vert B_n(x_0) \vert}{\vert S_n(x_0) \vert} \vert S_{n + 1}(x_0) \vert .$$Finally using the amenability hypothesis, we know that as n \to \infty, \disp \frac{\vert S_n(x_0) \vert}{\vert B_n(x_0) \vert} \to 0, and hence \disp \frac{\vert B_n(x_0) \vert}{\vert S_n(x_0) \vert} \to \infty. Therefore, there exists N_0 \geq r + \ell such that for all n \geq N_0, \disp \frac{\vert B_n(x_0) \vert}{\vert S_n(x_0) \vert} \geq (ac)^{-1}, where c is as above, and recalling that a = \prob(T_r(x_0)) > 0. Therefore,$$ \vert W \vert \geq a^{-1} \vert S_{n + 1}(x_0) \vert, \text{ if } n \geq N_0 $$To continue, declare, for any x \in V(\lambda) to be a \textit{cut--3--ball}, or more succintly a \textit{cut--ball}, if T_r(x) holds.\footnote{That is, B_r(x) is open and part of an infinite open component, but when the vertices in it are set to closed, it splits into at least 3 pieces.} Recall that for all w \in W \subset X_0, T_r(w) = T_r(x_0) = a > 0 by assumption and the common type of vertices in x_0. Therefore, by the linearity of expectation, for n \geq N_0,$$\expect( \# \text{ cut-balls in } W)= \sum_{w \in W} \prob(T_r(w)) = a \vert W \vert \geq \vert S_{n + 1}(x_0) \vert$$Note that this reduces, for any fixed n \geq N_0, to the configurations on the finite set W: for some configuration \omega of W,\footnote{and since W is a finite set, all configurations of it occur with positive probability} for any fixed n \geq N_0, with positive probability, we have that \begin{equation} s(\omega) := ( \# \text{ cut-balls in } W) \geq \vert S_{n + 1}(x_0) \vert \label{eqn:star}\end{equation} This is one of the inequalties to get a contradiction. To get an inequality going the other direction, note that the turn towards the emphasis on cut-balls makes it possible to consider reducing the graph to a finite variant to which we can apply the lemma we mentioned at the beginning. For any configuration \chi of \Lambda agreeing with \omega on W (for n = N_0, say), let \mathcal{O}(\chi) denote the union of all open clusters intersecting B_n(x_0). Define \chi^{\prime} to agree with \chi, but changing all sites in the cut-balls centered at points in W from open to closed. Then the infinite open clusters in \mathcal{O}(\chi) are disconnected into several open clusters. Let L_1, \dotsc, \L_t denote the infinite clusters in \chi^{\prime} (at most 3 per cut-ball, at least 3 total with positive probability by assumption), and let F_1, \dotsc, F_u denote the finite clusters in \chi^{\prime}. Each L^{i} contains a site in S_{n + 1}(x_0) (by connectivity arguments, since all the cut-balls of radius r centered at elements of W \subset B_{n - r}(x_0) are contained in B_n(x) by the triangle inequality), and distinct clusters must pass through distinct points of the boundary S_{n + 1}(x_0), so \begin{equation} t \leq \vert S_{n + 1}(x_0) \vert \label{eqn:twostar} \end{equation} Name the cut-balls C_1, \dotsc, C_s--note that they are disjoint, since W was defined so that the 2r-balls around each w \in W were disjiont. Define a finite graph H depending on \chi's and \chi^{\prime}'s configurations on B_n(x_0) as follows: contract each C_i to a single vertex c_i, each F_j to a single vertex f_j, and each L_k to a single vertex \ell_k. Connect each c_i to the f_j's and/or \ell_k's depending on whether or not C_i, F_j, and L_k were adjacent in the configuration \chi (note that there are no edges between the f_j's and \ell_k's, since they are separated components in \chi^{\prime} by hypothesis). Certainly, L = \cup_{k=1}^t \lbrace l_k \rbrace and C = \cup_{i=1}^s \lbrace c_i \rbrace are disjoint by definition. The infinite components of \mathcal{O}_{\chi} correspond to components of H containing at least one vertex in L. By each C_i a cut-ball, deleting C_i from the configuration \chi of \Lambda disconnected its component into at least 3 infinite open clusters, so deleting c_i from H disconnects its component into at least m_i \geq 3 components containing vertices of L. Therefore, the hypotheses of the lemma are satisfied, so we may apply the lemma, and conclude that \begin{equation} t = \vert L \vert \geq 2 + \sum_{i = 1}^s (m_i - 2) \geq 2 + \sum_{i = 1}^s 1 = 2 + s. \label{eqn:threestar} \end{equation} Note that although t and s depend on \chi, by hypothesis, with positive probability, s is at least 1 and t is at least 3, since T_r(x_0) = a > 0 by assumption, so that any vertex in W is a cut-ball with positive probability. Combining Equations~\ref{eqn:star}, \ref{eqn:twostar}, and \ref{eqn:threestar}, we have \begin{eqnarray*} \vert S_{n + 1}(x_0) \vert & \geq & t \geq s + 2 \geq \vert S_{n + 1}(x_0) \vert + 2 \\ 0 & \geq & 2 \end{eqnarray*} This is a contradiction. Therefore, \prob^s_{\Lambda, p}(\cup_{k \geq 3} I_k) = 0. \rightline{\square} Note that the above techniques can be used to show that \theta_x (p), the probability that x is in an infinite open cluster under (site-)percolation with probability p, is continuous in p, except possibly at the critical probability p = p_c. \subsection{For More Information} For more information about the very, very many equivalent formulations of amenability, a taste is given by \cite{Tao}. The conference hinted at in \cite{NagniSapiOne} has a fuller writeup in \cite{NagniSapiFull}. In particular, the work of Mark Sapir, and his student Iva Koz\'{a}kov\'{a}, is mentioned with regard to percolation theory. \clearpage \section{(Monday, December 3)} \textbf{Future directions for random graphs} \subsection{More flexible model of random graphs - especially for application} \begin{itemize} \item[--] theoretical cognitive neurosciences \\(see Kologrov, Barzdin, 1967) \item[--] epidemiology \item[--] computer science\\ (model \textit{www}, social network) \item[--] Topological data analysis\\ (see Carlson's survey article  Topology and data'') in Bulletin of AMS. persistent homology) \end{itemize} \subsection{Probability Method} Randomness is a nice way to prove existence. \begin{itemize} \item Higher-dimensional expanders \item[--] Buser-Cheeger inequalities\\ \lambda_2=smallest positive eigenvalue of \mathcal{L}(G)\\ h=Cheeger numer, expansion constant\\ Lplacian of k-forms, \delta d+d \delta, for analysis of h (see Dotterrer, Kahle) \item[--] Application of higher dimensional expanders \item[--] Random examples in DK have, for example,$$f_1={n \choose 2} , \,f_2=n^2\log n.$\item[--] Can we find random expanders with$f_2=O(f_2)$? \item Topological Turan theory (extream in graph theory) \item[--] Extreme in graph theory$ex(n;H):= \max \#$of edges with$n$vertices and no$H$-subgroups. \item[--] Turan theorem characterizes for$H=K_m$. \item[--] Erd\"{o}s -Stone for non bipartite group. \item[--] Easier questions$ex(n;\text{cycles})=n-1$\item 2-dimensional simplicial complxes \item[--] Let$S=2-$complex on n-vertices. How may two dimensional faces$f(n)$can you put in with no embedded copies of$S^2$. \item[--] Sos, Erd\"{o}s, Brown, ` On the existence of triangulated spheres in 3 groups...''\\$f(n)=n^{5/2}$\item[--] (Linial) What about torus?\\ You can get$\sim n^{5/2}$faces with no torus with modified random constructions. Is that optimal exponent? \item Random groups \item[--]$ < \underbrace{g_1,g_2,\cdots,g_n }_{\text{generators}}|\underbrace{ r_1,r_2,\cdots,r_m}_{\text{random relations}}>$\item[--] Triangular model$r_i$are all of length 3. \item[--] Total number of possible words of length 3$\sim n^3$. \item[--] Let$m=(n^3)^{\lambda}$, where$\lambda\in(0,1)$is the density. \item[--] Known : \item[-] If$\lambda > \frac{1}{2}$, then w.h.p group is trivial. (exercise) \item[-] (\.{Z}uk) If$\lambda < \frac{1}{2}$, then w.h.p (word) hyperbolic group$\exists c >o$such that$A(r) \leq CL(\gamma)$for all contractible$\gamma$\item[-] If$ \frac{1}{3}<\lambda < \frac{1}{2}\$, the group has Kazhdan's property w.h.p. \item[--] Is every hyperbolic group residually finite? \item[-] Intersections of all finite index subgroup is trivial. \item[-] Conjectured answer is NO. What about random groups? \end{itemize} \bibliographystyle{plain} \bibliography{gtrefs2}{} \end{document}