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%.
| Date | Description | Homework |
|---|---|---|
| Jan 14 | Basic ideas, union bound, lower bound on Ramsey numbers | |
| Jan 16 | \(2\)-colorability (property B), linearity of expectation, large bipartite subgraphs | |
| Jan 21 | Counting arguments using linearity of expectation, Sperner/LYM inequality + Littlewood–Offord problem, Bollobás’s inequality + saturation of cliques | |
| Jan 23 | More linearity of expectation, Jensen’s inequality, Turán’s theorem, sampling ideas | |
| Jan 28 | Group worksheet | HW1 (.tex) |
| Jan 30 | More sampling ideas, crossing numbers | |
| Feb 4 | ||
| Feb 6 | ||
| Feb 11 | HW2 (.tex) | |
| Feb 13 | ||
| Feb 18 | ||
| Feb 20 | ||
| Feb 25 | ||
| Feb 27 | ||
| Mar 4 | ||
| Mar 6 | ||
| Mar 11 | Spring break | |
| Mar 13 | Spring break | |
| Mar 18 | ||
| Mar 20 | ||
| Mar 25 | ||
| Mar 27 | ||
| Apr 1 | ||
| Apr 3 | ||
| Apr 8 | ||
| Apr 10 | ||
| Apr 15 | ||
| Apr 17 | ||
| Apr 22 | ||
| Apr 24 | ||
| Apr 29 |
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 \]
- Jensen’s inequality: If \(\phi\) is convex then \[ \operatorname{\mathbb{E}}\phi(X)\geq\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 and \(t>0\), then \[ \Pr[X\geq t]\leq{\operatorname{\mathbb{E}} X\over t}. \]
- Chebyshev’s inequality: If \(X\) is a random variable and \(\lambda>0\), then \[ \Pr\bigl[|X-\operatorname{\mathbb{E}}X|\geq\lambda\bigr]\leq{\operatorname{\mathbf{Var}}X\over\lambda^2}. \]