\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}[2]{\left( \! \! \! \begin{array}{c} #1 \\ #2 \end{array} \! \! \! \right)} \newcommand{\disp}[0]{\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')<\alpha
0 \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{$i$th 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{$i$th ($\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 $0$th and $1$st 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 n$$
Since 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} \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}