\documentstyle{article}[11pt]

\begin{document}

\setlength{\textwidth}{7in}
\setlength{\textheight}{8in}

\title{Oral Exam Syllabus}

\author{Vince Vatter}
\date{}%\date{March 8, 2004}
\maketitle

{\bf Committee:} Professors J. Beck, J. Kahn, M. Saks, D. Zeilberger (chair)

\section{Combinatorics}

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

\textbf{~}\\
\textbf{Permutations \& Tableau:}
Robinson-Schensted Correspondence, Knuth relations, Greene's Theorem, the Hook Length Formula, the Marcus-Tardos Theorem (Stanley-Wilf Conjecture), generating trees, WQO for permutations

\textbf{~}\\
\textbf{Hypergeometric functions \& identities:}
definition and representation, notion of q-analog and examples, Sister Celine's Algorithm, Gosper's Algorithm, Zeilberger's Algorithm

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

\textbf{~}\\
\textbf{Lattices \& Posets:}
Dilworth's Theorem, Fundamental Theorem of Finite 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{Ramsey Theory:}
Ramsey's Theorem, infinite Ramsey theory, probabilistic lower bounds, stepping-up
lemma, van der Waerden, $R(3,n)$ upper and lower bounds

~\\
\textbf{Discrepancy:}
Erd\H os-Selfridge Theorem, Beck-Fiala Theorem, discrepancy in arithmetic progressions, linear and hereditary discrepancy, 6 standard deviations suffice, Koml\'os Conjecture

~\\
\textbf{Algebraic Methods:}
Combinatorial Nullstellensatz, Chevalley-Warning Theorem, Cauchy-Davenport Theorem, Frankl-Wilson Theorem, bounds on the Shannon capacity using dimension arguments

\section{Graph Theory}

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

~\\
\textbf{Connectivity:}
Menger's Theorem, Max-Flow-Min-Cut Theorem, Kruskal's Algorithm

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

~\\
\textbf{Coloring:}
Brooks' 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



\section{Probabilistic Methods}

\textbf{Basics:} Stirling's formula, Bonferroni inequalities, 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's Conjecture



\section{Probability}

Probability Spaces\\
Random Variables\\
Borel-Cantelli Lemma\\
Laws of large numbers\\
Law of iterated logarithm\\
Central Limit Theorem\\
Conditional Expectation\\
Random Walks \& Polya's Theorem\\
Arc-Sine Laws\\
Kolmogorov's Zero-One Law\\
Are you paying attention? \\
\textbf{Percolation Theory:}\\
\qquad Bond percolation\\
\qquad Continuity properties of $\theta(p)$\\
\qquad Uniqueness of infinite cluster in $L^d$.

\end{document}
