MATH 7750-120: Advanced Topics in Graph Theory (Probabilistic Methods)

Lecture

228 Parker Hall

TR 12:30–1:45pm

Office hours

112 Parker Hall

TR 1:45–2:45pm

Textbook

There is no official textbook for the course, but a good reference book is The Probabilistic Method by Alon and Spencer

The probabilistic method is a powerful technique (or collection of techniques) in combinatorics and theoretical computer sciences, and this course will provide a graduate-level introduction to these fundamental ideas. The basic questions we will ask (and hopefully answer) have the form “Does an object with particular properties exist?”; for example, does there exist a graph with chromatic number at least 1,000,000,000 which has no cycles of length smaller than 1,000,000,000,000? Instead of trying to build such an object directly, we will instead learn how to construct random processes which have a chance of succeeding—the kicker being that if there is a positive probability of success, then there must be a way to succeed! The following is a list of topics discussed in the course (time permitting):

• Linearity of expectation and first-moment methods
• Alteration tricks
• Concentration inequalities and second-moment methods
• The Lovász Local Lemma
• Correlation inequalities
• Martingales
• The Poisson paradigm
• Entropy methods

Schedule and Assignments

Homework assignments must be written in \(\LaTeX\) and can be submitted either in-person or by email. If you email me your assignment, the subject line should read MATH 7750 <LAST NAME> HW<HOMEWORK NUMBER> and the email should include a .pdf version of your work titled <LAST NAME>_<HOMEWORK NUMBER>.pdf. If you wish to include a picture as part of a solution, the picture need not be typeset; a legible photograph of a hand-drawn picture is acceptable.

Homework assignments are due at the beginning of lecture (12:30pm) on the date by which they are posted in the following table. If you cannot attend class when an assignment is due, you are responsible for emailing me your assignment. For each minute the assignment is late, your assignment grade will be reduced by 1%. For example, an assignment which would score 85% but was submitted at 12:35pm would instead receive an 80%.

Useful inequalities and approximations

• Exponential approximations: \[ e^{-{x\over 1-x}}\leq 1-x\leq e^{-x} \]
• Binomial approximations: \[ \biggl({n\over k}\biggr)^k\leq {n\choose k}\leq {n^k\over k!}\leq \biggl({en\over k}\biggr)^k \]
• Stirling’s approximation: \[ n! = \bigl(1+o(1)\bigr)\sqrt{2\pi n}\biggl({n\over e}\biggr)^n. \] Applied to binomial coefficients: \[ {n\choose n/2}=\bigl(1+o(1)\bigr){2^n\over\sqrt{\pi n/2}}. \] For fixed \(0<\alpha<1\), \[ {n\choose \alpha n}=2^{(1+o(1))h_2(\alpha)n},\qquad\text{where } h_2(x)=-x\log_2 x-(1-x)\log_2(1-x) \]
• Cauchy–Schwarz inequality: \[ \langle x,y\rangle^2\leq\langle x,x\rangle\langle y,y\rangle \] In particular, \[ \bigl(\operatorname{\mathbb{E}}XY\bigr)^2\leq \operatorname{\mathbb{E}}X^2\cdot\operatorname{\mathbb{E}}Y^2 \]
• Hölder’s inequality: If \(X,Y\) are non-negative random variables and \(\lambda\in[0,1]\), then \[ \operatorname{\mathbb{E}}\bigl[X^\lambda Y^{1-\lambda}\bigr]\leq \bigl(\operatorname{\mathbb{E}} X\bigr)^\lambda\bigl(\operatorname{\mathbb{E}} Y\bigr)^{1-\lambda} \]
• Jensen’s inequality: If \(\phi\) is convex then \[ \operatorname{\mathbb{E}}\phi(X)\geq\phi\bigl(\operatorname{\mathbb{E}} X\bigr) \] If \(\phi\) is concave, then \[ \operatorname{\mathbb{E}}\phi(X)\leq\phi\bigl(\operatorname{\mathbb{E}} X\bigr) \]
• Arithmetic–Geometric mean inequality (AM–GM inequality): If \(a_1,\dots,a_n\geq 0\), then \[ \biggl(\prod_{i=1}^n a_i\biggr)^{1/n}\leq {1\over n}\sum_{i=1}^n a_i \]
• Markov’s inequality: If \(X\) is a non-negative random variable, then \[ \Pr[X\geq \lambda]\leq{\operatorname{\mathbb{E}} X\over \lambda}\qquad\text{for all }\lambda>0. \]
• Chebyshev’s inequality: If \(X\) is a random variable, then \[ \Pr\bigl[|X-\operatorname{\mathbb{E}}X|\geq\lambda\bigr]\leq{\operatorname{\mathbf{Var}}X\over\lambda^2}\qquad\text{for all }\lambda>0. \] In particular, if \(X\) is non-negative, then \[ \Pr[X=0]\leq{\operatorname{\mathbf{Var}}X\over (\operatorname{\mathbb{E}} X)^2}. \] Not exactly Chebyshev (this can be derived solely from Cauchy–Schwarz), but the following stronger bound holds here: \[ \Pr[X=0]\leq{\operatorname{\mathbf{Var}}X\over \operatorname{\mathbb{E}}(X^2)}. \]
• Chernoff’s bound: If \(X_1,\dots,X_n\) are independent random variables such that \(-1\leq X_i\leq 1\) and \(\operatorname{\mathbb{E}} X_i=0\) for all \(i\), then \[ \Pr\bigl[\lvert X_1+\dots+X_n\rvert\geq\lambda\bigr]\leq 2e^{-\lambda^2/(2n)}\qquad\text{for all }\lambda>0. \] As a consequence: Suppose that \(X_1,\dots,X_n\) are independent random variables such that \(0\leq X_i\leq 1\) for all \(i\). If \(S=X_1+\dots+X_n\), then \[ \Pr\bigl[\lvert S-\operatorname{\mathbb{E}} S\rvert\geq \lambda\bigr]\leq 2e^{-\lambda^2/(2n)}\qquad\text{for all }\lambda>0. \] One can do a bit better in this latter situation if the \(X_i\)’s have small means: Suppose that \(X_1,\dots,X_n\) are independent random variables such that \(0\leq X_i\leq 1\) for all \(i\). Set \(S=X_1+\dots+X_n\) and \(\mu=\operatorname{\mathbb{E}}S\), then \[ \Pr\bigl[ S\geq(1+\delta)\mu\bigr]\leq e^{-{\delta^2\over 2+\delta}\mu}\qquad\text{for all }\delta>0, \] \[ \Pr\bigl[ S\leq(1-\delta)\mu\bigr]\leq e^{-{\delta^2\over 2}\mu}\qquad\text{for all }0<\delta<1. \]
• Lovász Local Lemma (symmetric version): Let \(G\) be a dependency (di)graph for events \(B_1,\dots,B_n\) with maximum (out)degree \(d\). If \(\Pr[B_i]\leq p\) for all \(i\in[n]\) and \(ep(d+1)\leq 1\), then \(\Pr\bigl[\bigcap_{i=1}^n\overline{B_i}\bigr]>0\).
• Lovász Local Lemma: Let \(G\) be a dependency (di)graph for events \(B_1,\dots,B_n\). If there exist numbers \(x_1,\dots,x_n\in[0,1)\) such that \[ \Pr[B_i]\leq x_i\prod_{j\in N^+(i)}(1-x_j)\qquad\text{for all }i\in[n], \] then \(\Pr\bigl[\bigcap_{i=1}^n\overline{B_i}\bigr]\geq\prod_{i=1}^n(1-x_i)>0\).
• Hoeffding’s lemma: Let \(\mathcal{G}\) be a \(\sigma\)-algebra and suppose that \(L,U\) are \(\mathcal{G}\)-measurable random variables. If \(X\) is any random variable satisfying \(\operatorname{\mathbb{E}}[X|\mathcal{G}]=0\) and \(L\leq X\leq U\), then \[ \operatorname{\mathbb{E}}[e^X|\mathcal{G}]\leq e^{(U-L)^2/8}. \]
• Azuma–Hoeffding inequality (symmetric version): If \(Z_0,Z_1,\dots,Z_n\) is a martingale satisfying \(\lvert Z_i-Z_{i-1}\rvert\leq c_i\) for each \(i\in[n]\), then \[ \Pr[Z_n-Z_0\geq\lambda]\leq\exp\biggl({-\lambda^2\over 2(c_1^2+\dots+c_n^2)}\biggr)\qquad\text{for all }\lambda>0. \]
• Azuma–Hoeffding inequality (asymmetric version): Suppose that \(Z_0,Z_1,\dots,Z_n\) is a martingale with respect to the filtration \(\mathcal{F}_0\subseteq\mathcal{F}_1\subseteq\cdots\subseteq\mathcal{F}_n\). Suppose for each \(i\in[n]\), that \(L_i,U_i\) are \(\mathcal{F}_{i-1}\)-measurable random variables satisfying \(L_i\leq Z_i-Z_{i-1}\leq U_i\). If \(U_i-L_i\leq c_i\) for each \(i\in[n]\), then \[ \Pr[Z_n-Z_0\geq\lambda]\leq\exp\biggl({-2\lambda^2\over c_1^2+\dots+c_n^2}\biggr)\qquad\text{for all }\lambda>0. \]
• McDiarmid’s inequality: Suppose that \(f\colon\Omega_1\times\dots\times\Omega_n\to\R\) is a function satisfying \(\lvert f(\vec x)-f(\vec x')\rvert\leq c_i\) whenever \(\vec x\) and \(\vec x'\) differ only in the \(i\)th coordinate. If \(x_1,\dots,x_n\) are independent samples with \(x_i\in\Omega_i\), then the random variable \(Z=f(x_1,\dots,x_n)\) satisfies \[ \Pr[Z-\operatorname{\mathbb{E}}Z\geq\lambda]\leq\exp\biggl({-2\lambda^2\over c_1^2+\dots+c_n^2}\biggr)\qquad\text{for all }\lambda>0. \]
• Talagrand’s inequality: Fix \(\Omega=\Omega_1\times\dots\times\Omega_n\) and \(A\subseteq\Omega\). Define the metric \[ \rho(\vec x,A):=\sup_{\vec\alpha\in\mathbb{R}^n}\ \inf_{\vec y\in A}\ {1\over\lVert\vec\alpha\rVert}\sum_{i:\ x_i\neq y_i}\alpha_i. \] If \(x_1,\dots,x_n\) are independent samples with \(x_i\in\Omega_i\) (not necessarily uniform) and \(\vec x=(x_1,\dots,x_n)\), then \[ \Pr[\vec x\in A]\cdot\Pr[\rho(\vec x,A)\geq \lambda]\leq e^{-\lambda^2/4}\qquad\text{for all }\lambda>0. \]
• Talagrand’s inequality for the working mathematician: Fix \(\Omega=\Omega_1\times\dots\times\Omega_n\) and a function \(f\colon\Omega\to\mathbb{R}\). Suppose that for every \(\vec x\in\Omega\), there is a vector \(\vec\alpha(\vec x)=\bigl(\alpha_1(\vec x),\dots,\alpha_n(\vec x)\bigr)\in\R^n\) such that \[ f(\vec x)\leq f(\vec y)+\sum_{i:\ y_i\neq x_i}\alpha_i(\vec x)\qquad\text{for all }\vec y\in\Omega. \] If \(x_1,\dots,x_n\) are independent samples with \(x_i\in\Omega_i\) (not necessarily uniform), then the random variable \(Z=f(x_1,\dots,x_n)\) satisfies \[ \Pr\bigl[\lvert Z- \operatorname{\mathbb{M}}Z\rvert\geq\lambda\bigr]\leq 4\exp\biggl({-\lambda^2\over 4\sup_{\vec x\in\Omega}\lVert\vec\alpha(\vec x)\rVert^2}\biggr)\qquad\text{for all }\lambda>0. \]
• Talagrand’s inequality for functions with small certificates: Fix \(\Omega=\Omega_1\times\dots\times\Omega_n\) and a function \(f\colon\Omega\to\mathbb{R}\) which is \(1\)-Lipschitz with respect to the Hamming metric on \(\Omega\). Suppose also that the set \(\{f\geq r\}\) is \(s\)-certifiable. If \(x_1,\dots,x_n\) are independent samples with \(x_i\in\Omega_i\) (not necessarily uniform), then the random variable \(Z=f(x_1,\dots,x_n)\) satisfies \[ \Pr[Z\leq r-\lambda]\cdot\Pr[Z\geq r]\leq e^{-\lambda^2/4s}\qquad\text{for all }\lambda>0. \] In particular, if additionally \(\{f\geq r\}\) is \(r\)-certifiable for every \(r\), then \[ \Pr[Z\leq \operatorname{\mathbb{M}}Z-\lambda]\leq 2\exp\biggl({-\lambda^2\over 4\operatorname{\mathbb{M}}Z}\biggr)\qquad\text{for all }\lambda>0, \] and \[ \Pr[Z\geq \operatorname{\mathbb{M}}Z+\lambda]\leq 2\exp\biggl({-\lambda^2\over 4(\operatorname{\mathbb{M}}Z+\lambda)}\biggr)\qquad\text{for all }\lambda>0. \]