\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}

%\newcommand\vanish[1]{,} \newcommand\vanishdot[1]{.}
\newcommand\vanish[1]{ #1}\newcommand\vanishdot[1]{ #1}\usepackage{fullpage}

% for bibliography
%\newcommand\vanishbiblio[1]{}
\newcommand\vanishbiblio[1]{#1}


\begin{document}
\begin{center}
\textbf{\LARGE Oral Qualifying Exam Syllabus}
\\Philip Matchett Wood
\\Committee: Profs. Van Vu (chair), J\'{o}zsef Beck, Endre Szemer\'{e}di, and
Doron Zeilberger.  
\end{center}

\begin{center}\Large\bf I. Combinatorics, Graph Theory,\\ and the Probabilistic
Method
\end{center}

\noindent
{\large \textbf{1 Combinatorics}} \\ 

\noindent
\textbf{Basic Enumeration:}
counting arguments\vanish{(\cite[Chapter 1]{K}, \cite[Chapter 13, p. 119ff]{vLW}),\\}
Stirling's rule\vanish{(\cite[\S2.1]{K}, \cite[p. 52--54]{F}),\\}
binomial coefficients\vanish{(\cite[Chapter 1, Chapter 2]{K}),\\}
inclusion-exclusion principle\vanish{(\cite[Chapter 4]{K}, \cite[Chapter 10, p.  89]{vLW}), \\}
recurrence relations and generating functions\vanish{(\cite[Chapter 3]{K}, \cite[Chapter 14, p.  129ff]{vLW}),\\}
\\
\textbf{Set Systems:} 
Erd\H{o}s-Ko-Rado\vanish{(\cite[p.56]{vLW}, \cite[Thm 2.1.9]{ExC}, \cite[p.
45, \S7]{Bol}),\\} 
Sperner's theorem and LYM inequality\vanish{(\cite[p.  10]{Bol}, \cite[p.
54]{vLW}, \cite[Appendix]{ExC}, \cite[Chapter 5, also p. 124]{K}),\\}
Kruskal-Katona\vanish{(\cite[Thm 3, p. 30]{Bol}, \cite[Apdx. \S 2.1.5]{ExC}),
\\}
Fisher's and generalized Fisher's inequalities\vanish{(\cite[Lem 1.2.1]{ExC},
\cite[p. 222]{vLW}), \\} 
Ray-Chaudhuri--Wilson and Frankl-Wilson\vanish{(\cite[Thm 1.2.3 \&
1.2.4]{ExC}, \cite{FW}, \cite[Thm 19.8, p. 222]{vLW}), \\}
Borsuk Conjecture and Kahn-Kalai counterexample\vanishdot{(\cite[Cor
1.3.2]{ExC}, \cite{KK}), \\}
%Leave this one out:
%Harper with Frankl-Furdi proof\vanish{(\cite[Thm 1.7.4]{ExC}, \cite[p.  125--127]{Bol}), \\}
\\
\textbf{Lattices and Posets:} 
distributive lattices and geometric lattices\vanish{(\cite[p. 145]{Bol},
\cite[Chapter 5, Chapter 9]{K}, \cite[\S 1.8]{ExC}, \cite[p. 305ff]{vLW}), \\} 
Birkhoff representation theorem\vanish{(\cite[bottom of p. 83]{AS}, 
\cite[p. 146]{Bol}%
%which is a reference to p. 59 of the book Birkhoff, G. (1967) \emph{Lattice Theory} 3rd Edn., American Math. Soc. Coll. Publ. vol XXV, Amer. Math. Soc., Providence, R.I., vi + 418pp.
), \\}
Dilworth\vanish{(\cite[Thm 6.1]{vLW}, \cite[Thm 5.2.1]{K}), \\}
M\"obius inversion\vanish{(\cite[Chapter 25]{vLW}),\\}
Weisner\vanish{(\cite[Thm 25.3]{vLW}), \\}
Dowling-Wilson\vanishdot{(\cite[Thm 25.5]{vLW}).\\}
\\
\textbf{Correlation Inequalities:}
Harris-Kleitman\vanish{(\cite[p. 143]{Bol}, \cite[\S1.8, Thm 1.8.1]{ExC}),
\\}
Fortuin-Kasteleyn-Ginibre (FKG inequality)\vanish{(\cite[p. 147]{Bol},
\cite[Thm 1.8.4]{ExC}, \cite[p.  84]{AS}, \cite[p. 34]{TV}), \\}
Ahlswede-Daykin four functions theorem\vanish{(\cite[Chapter 19]{Bol}, \cite[Thm
1.8.2]{ExC}, \cite[p.82]{AS}), \\}
application to Shepp's $xyz$ inequality\vanishdot{(\cite{Shepp}, \cite[\S6.4,
p.  88]{AS}).\\}
\\
\textbf{Ramsey Theory:} 
Ramsey's theorem\vanish{(\cite[p. 28]{vLW}, \cite[Apdx.]{ExC}, \cite{GRS}),
\\}
infinite Ramsey\vanish{(\cite[Chapter 20]{Bol}, \cite{GRS}), \\}
probabilistic lower bounds\vanish{(\cite[p. 16, p. 25, p. 67]{AS}, \cite[p.
30]{vLW}),\\}
%% Leave off below:
%stepping-up lemma\vanish{(\cite[p. 106--108]{GRS}), \\}
Hales-Jewett, van der Waerden, Gallai's theorem\vanish{(\cite[Chapter 2]{GRS}, \cite[Chapter 1]{AddC}), \\}
statement of Szemer\'edi's theorem\vanishdot{(\cite{TV}, \cite{AddC}).\\}
%% Leave off sub-topic below:
%\\
%\textbf{Discrepancy:} Beck-Fiala\vanish{(\cite[p. 209]{AS}), \\}
%Roth's $\frac{1}{4}$-theorem on discrepancy of arithmetic
%progressions\vanishdot{(\cite{Chaz}, {\Huge $\blacktriangleleft$}). \\ }
%% --maybe switch to 6 standard deviations suffice, THOUGH this makes
%% sense too, so maybe leave it as is. 
\\ \\*
{\large \textbf{2 Graph Theory}} 
\\ \\
\textbf{Matching:} K\"onig\vanish{(\cite[Thm 2.1.1]{D}, \cite{K}), \\}
Hall\vanish{(\cite[Thm 2.1.2]{D}, \cite[p. 5--6]{Bol}, \cite{K}, \cite[Chapter
5]{vLW}), \\}
Tutte's 1-factor theorem\vanishdot{(\cite[Thm 2.2.1]{D}, \cite{K}).\\}
%% Leave below out
%matching polytope\vanishdot{(\cite[\S5.4.1]{K}, \cite{MIT}).\\}
% Bipartite matching algorithm\vanishdot{(\cite{from Dr. Z's class...}).\\}
\\
\textbf{Connectivity:} 
structure of 2-connected graphs\vanish{(\cite[\S3.1]{D}),\\}
Menger\vanish{(\cite[\S3.3]{D}), \\}
Max-Flow-Min-Cut\vanish{(\cite[p. 64]{vLW}, \cite[p. 143]{D}), \\}
Kruskal's algorithm\vanishdot{(any standard algorithms book). \\}
% find a CS book with this in it, or use Wikipdia :-)
\\
\textbf{Planarity:} 
Euler's formula\vanish{(\cite[Thm 4.2.9]{D}),\\}
Kuratowski's theorem\vanish{(\cite[\S4.4]{D}), \\}
Wagner's theorem\vanishdot{(\cite[Thm 4.4.6]{D}).\\}
\\
\textbf{Coloring:} 
chromatic number and edge chromatic number\vanish{(\cite{D}),\\}
5 color theorem\vanish{(\cite[Prop 5.1.2]{D}), \\}
Brooks\vanish{(\cite[Chapter 3]{vLW}, \cite[Thm 5.2.4]{D}),\\}
K\"onig edge coloring theorem\vanish{(\cite[p. 119, Prop 5.3.1]{D}),\\}
Vizing's Theorem\vanish{(\cite[Thm 5.3.2]{D}), \\}
perfect graphs\vanish{(\cite{D}),\\}
Lov\'asz's proof of weak perfect graph conjecture\vanishdot{(\cite[Thm
5.5.4]{D}).\\}
\\
\textbf{Extremal Problems:} 
Tur\'an\vanish{(\cite[p. 165]{D}, \cite[p. 91]{AS}), \\}
statement of regularity lemma\vanish{(\cite[p. 176]{D}), \\}
Erd\H{o}s-Stone\vanishdot{(\cite[Thm 7.1.2, cf p. 186--187]{D}). \\}
\\ \\*
{\large \textbf{3 Probabilistic Methods}} 
\\ \\
\textbf{Basics:}
probability spaces and random variables\vanish{(\cite{W}), \\}
linearity of expectation\vanish{(\cite[Chapter 2.1]{AS}), \\}
Bonferroni inequalities\vanish{(\cite{K}),\\}
Normal, Binomial, and Poisson distributions\vanish{(\cite{W}, \cite{K2}), \\}
conditional probability and law of total probability\vanish{(\cite{W}), \\}
Chernoff bound\vanishdot{(\cite[Apdx. A]{AS}, \cite[p. 24, \S1.3]{TV},
\cite{K2}).\\}
\\
\textbf{Second Moment Method:} 
general procedure\vanish{(\cite[\S3.1]{JLR}, \cite[Chapter 4]{AS}, \cite[\S1.2]{TV}), \\}
Chebyschev's inequality\vanish{(\cite[p. 41]{AS}, \cite[p. 19, \S1.2]{TV}),\\}
application to threshold function for having a certain graph as a
subgraph\vanishdot{(\cite[Chapter 3, p. 55ff]{JLR}, \cite[Chapter 4]{AS},
\cite{K2}). \\} \\
\textbf{Lov\'asz Local Lemma:}
symmetric and general versions\vanish{(\cite[p. 64--65]{AS}, \cite[\S1.5]{TV},
\cite{K2}), \\}
% Leave the one below out.
%applications to linear aboricity\vanish{(\cite[\S5.5]{AS},\cite[10/19/2005--10/24/2005]{K2}),\\} 
applications to Latin transversals\vanishdot{(\cite[\S5.6]{AS},\cite{K2}).\\}
\\
\textbf{Poisson Paradigm:} Janson inequalities\vanish{(\cite[\S8.1]{AS},
\cite[\S1.6]{TV}), \\}
application to number of triangles in $G_{n,p}$\vanish{(\cite[\S10.1]{AS}),
\\}
Brun's sieve\vanish{(\cite[\S8.3]{AS}, \cite{K2}, \cite[Coro 6.8]{JLR}), \\}
application to number of isolated vertices in
$G_{n,p}$\vanishdot{(\cite{K2}, \cite[Coro 3.31]{JLR} ).\\}
\\
\textbf{Random Graphs:} $G_{n,p}$ versus $G_{n,M}$ \vanish{(\cite[p.
2]{JLR}),\\}
monotone properties\vanish{(\cite[Chapter 10, \S4.4]{AS}, \cite[p. 12]{JLR}),\\ }
existence of threshold functions\vanish{(\cite[Thm 1.24, \S1.5]{JLR}, \cite[p.
156--157]{AS}), \\}
connectedness (Erd\H{o}s-Renyi)\vanish{(\cite{K2}),\\}
probabilistic refutation of Haj\'os' conjecture\vanishdot{(\cite{K2}, \cite{Cat}).\\}
\\
\textbf{Martingales and Tight Concentration:} 
Azuma's inequality\vanish{(\cite[\S7.2]{AS}, \cite[p. 37ff]{JLR}, \cite{K2}),\\}
edge and vertex exposure\vanish{(\cite[\S7.1]{AS}, \cite{K2}, \cite[p.
39]{JLR}), \\}
application to concentration of chromatic number\vanish{(\cite[\S7.3]{AS}),
\\}
%\textbf{Tight Concentration:}
Talagrand's inequality\vanish{(\cite[p. 39ff]{JLR}, \cite[\S7.5,\S7.6]{AS}, \cite{VV}),\\}
comparing Talagrand's and Azuma's inequalities\vanish{(\cite[p.
41--43]{JLR}, \cite[\S7.7]{AS}, \cite{VV}),\\}
application to independence number of $G_{n,1/2}$\vanishdot{(\cite[p.
43]{JLR}).\\}

\begin{center}\Large\bf II. Additive and Combinatorial Number Theory \end{center}

\noindent
\textbf{Structure of sumsets and applications:} 
basic definitions and results\vanish{(\cite{VV}, \cite{AddC},
\cite[p. 6--9,\S2.1,\S2.2]{TV}),\\}
Ruzsa distance and additive energy\vanish{(\cite{VV}, \cite[\S2.3]{TV}),\\}
theorem showing $\left| r_1 A - r_2 A + r_3 B - r_4 B\right|$ is ``small''
when $|A+B|$ is ``small''\vanish{(\cite{VV}),\\}
statement of Balog-Szemer\'edi-Gowers Theorem\vanishdot{(\cite[\S6.4]{AddC},
\cite[\S2.5]{TV}%, proof at \cite[\S6.4]{TV}
).\\}
%% Leave the below out.
%statement of Pl\"{u}necke's Theorem\vanish{(\cite{AddC}, proof at \cite[\S6.5]{TV}?),\\}
%Pl\"unecke graphs and applications\vanishdot{(\cite{AddC}).\\}
\\
\textbf{Geometry of Numbers:}
basic results for a lattices and convex bodies in $\mathbb
R^d$\vanish{(\cite{VV}, \cite{AddC}, \cite[Chapter 3]{TV}),\\}
John's Theorem\vanish{(\cite[Thm 3.13]{TV}),\\}
Ruzsa's Covering Lemma\vanish{(\cite[Lem 3.14]{TV}),\\}
Volume Packing Lemma\vanish{(\cite[Lem 3.24]{TV}),\\}
Blichfeldt's lemma\vanish{(\cite{AddC}, \cite[p. 153]{TV}),\\}
Minkowski's first theorem\vanish{(\cite{VV}, \cite{AddC}, \cite[p. 153]{TV}),\\}
Minkowski's second theorem\vanish{(\cite{VV}, \cite{AddC}, \cite[p.
153]{TV}),\\}
Discrete John's Theorem\vanishdot{(\cite[Lem 3.36]{TV}).\\}
%
%% Leave below off
%\\
%\textbf{Weyl's inequality}:
%\vanishdot{(\cite{AddC}).\\}
\\
\textbf{Generalized Arithmetic Progressions (GAPs):}
definitions of proper and non-proper GAPs \vanish{(\cite{VV}, \cite{AddC},
\cite[\S3.2, and p. 12]{TV}),\\}
containing lemmas \vanishdot{(\cite{VV}, \cite[\S3.6, Thm 3.38 \& Thm 3.40]{TV}).\\}
\\
\textbf{Freiman's Theorem:}
Freiman homomorphism\vanish{(\cite{AddC}, \cite{TV2357} (which is
\cite[\S5.3]{TV}), \cite{Gran}),\\}
Freiman's Cube Lemma\vanish{(\cite[p.129, Coro 3.19]{TV2357} (which is
\cite[\S5.2]{TV}), \cite{VV2}),\\}
Ruzsa's lemma\vanish{(\cite{AddC}, \cite[Lem 3.26]{TV2357}),\\}
Freiman's Theorem\vanishdot{(\cite{AddC},\cite[Thm 3.32]{TV2357}).\\} 
\\
\textbf{Discrete Fourier Analysis and the Littlewood-Offord problem:}
Definition $X_{\mathbf{v}}^{(\mu)}$ and basic properties of its Fourier
representation\vanish{(\cite{VV}, \cite[\S4.2, page 168ff]{TV2357} (which is
\cite[\S7.2]{TV})),\\}
%% Leave below off
%properties of the discrete Fourier transform
%\cite[p. 19--23]{AddC}%
% Bohr neighborhoods\vanish{(\cite{AddC}, \cite[\S4.4]{TV}?),\\}
Hal\'asz-type concentration inequality\vanish{(\cite{VV}, \cite[\S4.2,
page 172ff]{TV2357} (which is \cite[\S7.2]{TV})),\\}
basic Littlewood-Offord results\vanish{(\cite{VV}, \cite[\S4.1]{TV2357} (which is \cite[\S7.1]{TV}), \cite[p. 19]{Bol}),\\}
% Littlewood-Offord with Erd\H{o}s's proof\vanish{ (\cite{VV}, \cite[\S4.1]{TV2357} (which is \cite[\S7.1]{TV})),} and with Kleitman's proof\vanish{ (\cite[p. 19]{Bol}, \cite[\S4.1]{TV2357} (which is \cite[\S7.1]{TV})),\\}
stronger Littlewood-Offord result with Fourier analysis
\vanishdot{(\cite{VV}, \cite[\S4.2]{TV2357} (which is \cite[\S7.2]{TV})).\\}
%% Leave below off
%Roth's theorem for arithmetic progressions of length 3 \vanishdot{(\cite[\S2.5]{AddC}).\\} 
\\

\vanishbiblio{
\noindent\textbf{Note:} Some of the references are to typed notes
(\cite{AddC}, \cite{K}, \cite{ExC}, and \cite{VV} (partially)), or
handwritten notes (\cite{Gran}, \cite{VV} (partially), \cite{VV2}, \cite{K2}).
Also note that \cite{TV} and \cite{TV2357} reference \emph{preliminary} drafts
of a book, so page and section numbers may differ from the published version
(which is due out in 2006).

\begin{thebibliography}{12}

\bibitem[AS]{AS} 
Alon, Noga; Spencer, Joel H. \emph{The probabilistic method.} Second edition.
Wiley-Interscience Series in Discrete Mathematics and Optimization.
Wiley-Interscience [John Wiley \& Sons], New York, 2000. xviii+301 pp.

\bibitem[Bol]{Bol} Bollob\'as, B\'ela.  \emph{Combinatorics: Set systems,
hypergraphs, families of vectors and combinatorial probability.} Cambridge
University Press, Cambridge, 1986.  xii+177 pp.

\bibitem[Cat]{Cat} Catlin, Paul A.  Haj\'os' graph-coloring conjecture:
variations and counterexamples.  \emph{J. Combin. Theory Ser. B} \textbf{26}
(1979), no.  2, 268--274. % can probably get it from the library.

%% Reference removed
%\bibitem[Chaz]{Chaz} Chazelle, \emph{Discrepancy Theory}.

\bibitem[D]{D} Diestel, Reinhard. \emph{Graph theory}. Third edition. Graduate
Texts in Mathematics, 173. Springer-Verlag, Berlin, 2005. xvi+411 pp.

\bibitem[F]{F} Feller, W. \emph{Introduction to Probability Theory and its
Applications, volume 1}, 3rd edition, John Wiley \& Sons, Inc., New York,
1968.

\bibitem[FW]{FW} Frankl, P., Wilson, R.M..
Intersection theorems with geometric consequences, 
\emph{Combinatorica}, v. \textbf{1} (1981), p. 357--368.

\bibitem[Gow]{AddC} Gowers, Timothy. notes from \emph{Additive and
Combinatorial Number Theory}, University of Cambridge, Part III Maths, 2003
Lent Term (notes taken by Philip Matchett Wood).

\bibitem[GRS]{GRS} 
Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. \emph{Ramsey theory}.
Wiley-Interscience Series in Discrete Mathematics. A Wiley-Interscience
Publication. John Wiley \& Sons, Inc., New York, 1980. ix+174 pp.

\bibitem[Gran]{Gran} Granville, Andrew. notes from Workshop on Additive
Combinatorics, Centre de recherche math\'ematiques Universit\'e de Montr\'eal,
April 2006.

\bibitem[JLR]{JLR} Janson, Svante; \L uczak, Tomasz; Rucinski, Andrzej.
\emph{Random graphs}.  Wiley-Interscience Series in Discrete Mathematics and
Optimization.  Wiley-Interscience, New York, 2000. xii+333 pp. 

\bibitem[K04]{K} Kahn, Jeff. notes from \emph{Combinatorics I}, Rutgers
University, Fall 2004 (notes taken by Philip Matchett Wood).

\bibitem[K05]{K2} Kahn, Jeff. notes from \emph{Probability and Combinatorics},
Rutgers University, Fall 2006 (notes taken by Mike Nieman).

\bibitem[KK]{KK} Kahn, J., Kalai, G..  A counterexample to Borsuk's Conjecture
\emph{Bulletin, new series, of the American Mathematical
Society}, Volume 29, Number 1, July 1993, Pages 60-62.

\bibitem[vLW]{vLW} van Lint, J. H.; Wilson, R. M. \emph{A course in
combinatorics}. Second edition.  Cambridge University Press, Cambridge, 2001.
xiv+602 pp.

%% Reference removed.
%\bibitem[MIT-OC]{MIT} Selected course lecture notes available online through MIT's Open Courseware program.  These lectures were found by typing ``matching polytope MIT" at the Google prompt.

\bibitem[S]{Shepp} Shepp, L. A.  The $XYZ$ conjecture and the FKG inequality.
\emph{Ann. Probab.} \textbf{10} (1982), no. 3, 824--827.

\bibitem[TV]{TV} Tao, Terence, Vu, Van.
Additive Combinatorics (Cambridge Studies in Advanced Mathematics).
Chapters 1--3 (from sample posted on Tao's website).

\bibitem[TV2357]{TV2357} Tao, Terence, Vu, Van.  Additive Combinatorics
(Cambridge Studies in Advanced Mathematics).  Chapters 2,3,5,7 (Preliminary
draft from the authors).

\bibitem[Thom]{ExC} Thomason, Andrew. notes from \emph{Extremal
Combinatorics},  University of Cambridge, Part III Maths, Lent Term, 2003
(notes taken by Philip Matchett Wood).

\bibitem[V05]{VV} Vu, Van.  notes from \emph{Random Structures}, Rutgers
University, Spring 2005 (notes taken by Philip Matchett Wood).

\bibitem[V06]{VV2} Vu, Van. notes from Workshop on Additive
Combinatorics, Centre de recherche math\'ematiques Universit\'e de Montr\'eal,
April 2006.

\bibitem[W]{W} Williams, David.  \emph{Probability with martingales}.
Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge, 1991.
xvi+251 pp. 

\end{thebibliography}
}
\end{document}
