\documentstyle{article}
\begin{document}
\title{Oral Exam}
\author{Bill Cuckler}
\parindent0pt
\maketitle
Committee: Profs J. Beck, J. Kahn, J. Koml\'os, M. Saks

\section{Combinatorics and Graph Theory}
\subsection{Combinatorics}

\textbf{Basic Enumeration:}
counting arguments, generating functions, recurrence relations, reflection 
principle, inclusion-exclusion principle

%\textbf{~}\\
\textbf{Extremal Set Theory:}
Ray-Chaudhuri Wilson, Frankl Wilson, Sperner's theorem, Erd\H 
os-Ko-Rado, 
Borsuk conjecture and Kahn Kalai counterexample, Harper, Kruskal Katona

%\textbf{~}\\
\textbf{Lattices:}
Geometric and distributive lattices, Birkhoff covering property, 
Jordan-Dedekind chain condition, M\" obius inversion, Weisner's theorem, 
Dowling-Wilson theorem

%~\\
\textbf{Correlation Inequalities:}
Harris-Kleitman, FKG, four functions, application to xyz inequality, 
BK inequality, stochastic domination

%~\\
\textbf{Discrepancy:}
Erd\H os-Selfridge theorem, Beck-Fiala, discrepancy in arithmetic 
progression, linear and hereditary discrepancy, 6 standard 
deviations 
suffice, Koml\'os conjecture

%~\\
\textbf{Ramsey Theory:}
Ramsey's theorem, infinite Ramsey, probabilistic lower bounds, stepping-up 
lemma, van der Waerden, $R(3,n)$ upper and lower bounds

\subsection{Graph Theory}

\textbf{Matching:}
Hall's theorem, bipartite matching algorithm, K\"onig's theorem, Tutte's 
1-factor theorem, matching polytope

%~\\
\textbf{Connectivity:}
Menger, Max-Flow-Min-Cut theorem, Dilworth's theorem, Kruskal's algorithm

%~\\
\textbf{Planarity:}
Euler's formula, Kuratowski's theorem, Wagner's theorem

%~\\
\textbf{Coloring:}
chromatic and edge chromatic numbers, Brook's theorem, Vizing's theorem, 5 
color theorem, perfect graphs, weak perfect graph theorem

%~\\
\textbf{Extremal Problems:}
Tur\' an's theorem, statement of Regularity lemma and 
application to Erd\H os-Stone theorem 

\subsection{Probabilistic Methods}

\textbf{Basics:} Stirling's formula, linearity of expectation, Bonferroni 
inequalities, coupling, Chebyshev's inequality, Chernoff bound

%~\\
\textbf{Alterations:} application to lower bound on property B 

%~\\
\textbf{Second Moment Method:} general procedure, application to threshold 
function for having a certain graph as a subgraph, $2^{nd}$ moment method 
for nonnegative random variables

%~\\
\textbf{Lov\' asz Local Lemma:} symmetric and general versions, 
applications to linear arboricity conjecture and Latin transversals

%~\\
\textbf{Martingales:} Azuma's inequality, edge and vertex exposure, 
applications to chromatic number

%~\\
\textbf{Poisson Paradigm:} Janson inequalities, application to number of 
triangles in $G_{n,p}$, Brun's sieve, application to number of isolated 
points

%~\\
\textbf{Random graphs:} monotone properties, $G_{n,p}$ versus 
$G_{n,M}$, existence of threshold functions, relationship 
between connectedness and having no isolated vertices, probabilistic 
refutation of Haj\'os conjecture

\section{Probability Theory}
\parindent=0in

Probability Spaces

Random Variables

Borel-Cantelli Lemma

Laws of large numbers

Law of iterated logarithm

Central Limit Theorem

Conditional Expectation

Random Walks and Polya's theorem

Arc-Sine Laws

Maximal ergodic theorem and Birkhoff Ergodic Theorem

Application of ergodic theorem to equidistribution 

Kolmogorov's Zero One Law



\textbf{Percolation Theory:}

Bond percolation

Continuity properties of $\theta (p)$

Uniqueness of infinite cluster in $L^{d}$

\end{document}
