\documentclass[11pt]{article}
\usepackage{amsmath, amsfonts, amssymb}

\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\T}{{\mathbb T}}
\newcommand{\F}{{\mathcal F}}
\newcommand{\eps}{\epsilon}





\begin{document}


\begin{center}
\Large{Oral Exam Syllabus}
\end{center}

Committee:  Profs E. Szemer\'edi (chair), J. Beck, E. Boros, J. Kahn
\begin{center}
\Large
\bf{I.  Combinatorics, Graph Theory, and the Probabilistic Method}
\end{center}

\vspace{10pt}
\begin{center}
\large \underline{Combinatorics}
\end{center}
\begin{enumerate}

\item[\small \bf Basic Enumeration:]{  counting arguments, generating functions, recurrence relations,
	reflection principle, inclusion-exclusion.
	}
\item[\small \bf Set Systems:]{
	Erd\"os--Ko--Rado, Ray-Chaudhuri--Wilson, Frankl--Wilson, Sperner's Theorem, Littlewood--Offord,
	Kruskal-Katona, Harper's Theorem, Fisher's and Generalized Fisher's Inequality, Steiner systems, 
	Baranyai's Theorem, Kahn-Kalai.
	}

\item[\small \bf Lattices:]{	
	Geometric and distributive lattices, Birkhoff covering property, Jordan-Dedekind chain condition,
	Incidence Algebra, M\"obius inversion, Weisner's Theorem, Dowling-Wilson Theorem.
	}
\item[\small \bf Correlation Inequalities:]{
	Harris, Holley, FKG, four funcitons, Shepp's theorem, stochastic domination, [1/3, 2/3]-conjecture,
	Strassen's theorem.
	}	
\item[\small \bf Ramsey Theory:]{	
	Ramsey's Theorems, probabilistic lower bounds, Van der Waerden's Theorem, stepping-up lemma.
	}
\item[\small \bf Discrepancy:]{	
	Erd\"os-Selfridge Theorem, Beck-Fiala,  Roth's theorem on 2D discrepancy, 
	discrepancy in arithmetic progressions, linear and hereditary discrepancy, 6 standard deviations
	suffice, Koml\'os conjecture.
	}

\end{enumerate}

References: van Lint and Wilson, \emph{A Course in Combinatorics}

\begin{center}
\large \underline{Graph Theory}
\end{center}

\begin{enumerate}

\item[\small \bf Algorithms:]{
	Minimum Weight Spanning Tree, Dijkstra, Hungarian Method, Edmonds Matching Algorithm, Kruskal.
	}
\item[\small \bf Matching Theory:]{
	Hall, Stable Marriage, Tutte's 1-factor Theorem, Augmenting Paths.
	}	
\item[\small \bf Connectivity:]{
	Mincut-Maxflow, Menger's Theorem.
	}
\item[\small \bf Coloring:]{
	Brooks' Theorem, Vizing's Theorem, K\"onig's (edge-coloring) Theorem, Hadwiger's conjecture,
	perfect graphs, weak perfect graph theorem, proof of the Dinitz Conjecture, 5-color theorem.
	}
\item[\small \bf Extremal:]{
	Tur\'an's Theorem, Erd\"os-Stone Theorem, Ramsey-type results (R(k, k) bounds), Regularity Lemma.
	}
\item[\small \bf Planarity:]{
	Euler's formula, Kuratowski, Wagner.
	}

\end{enumerate}
References:  Diestel, \emph{Graph Theory}
\begin{center}
\large \underline{Probabilistic Method}
\end{center}

\begin{enumerate}

\item[\small \bf Basics:]{
	linearity of expectation, Bonferroni inequalities, binomial and Poisson distributions, 
	conditional probabilities, law of total probability, Chebyshev's inequality, Chernoff 
	bound, coupling and stochastic domination.
	}
\item[\small \bf Second Moment Method:]{
	General procedure, threshold function for containg a given subgraph.
	}
\item[\small \bf Lov\'asz Local Lemma:]{	
	summmetric and general versions, applications to linear arboricity conjecture and Latin
	transversals.}
\item[\small \bf Martingales:]{
	Azuma's inequality, edge and vertex exposure, application to chromatic number.
	}
\item[\small \bf Poisson paradigm:]{
	Janson inequalitites, application to number of triangles in $G_{n, p}$, Brun's sieve, 
	application to number of isolated points in $G_{n, p}$.
	}
\item[\small \bf Random graphs:]{
	monotone properties, $G_{n,p}$ vs. $G_{n,k}$, threshold functions, probabilistic refutation 
	of Haj\'os conjecture, connectedness.
	}
\end{enumerate}
References:  Alon and Spencer, \emph{The Probabilistic Method}
\begin{center}
\Large
\bf{II.  Discrete Optimization}
\end{center}

\begin{enumerate}
\item[\small \bf Basics:]{
	Linear Programming, Simplex and Dual Simplex methods, Duality Theorems, Farkas' lemma, Integer programming.
	}
\item[\small \bf Min-Max theorems:]{Covering and packing problems, Fekete's lemma, Menger, Dilworth, K\"onig}

\item[\small \bf Algorithms:]{P, NP, co-NP and good characterizataions, approximation results, knapsack problem.
	}
\item[\small \bf Geometry:]{
	Convexity, cones, polyhedra and polytopes, polarity, blocking and anti-blocking polyhedra, integer polyhedra.
	}
\item[\small \bf Integer programming:]{
	Totally Unimodular matrices, total dual integrality, Hilbert basis, integer hull, cutting planes.
	}
\end{enumerate}

References:  Schrijver, \emph{Combinatorial Optimization -- Polyhedra and Efficiency}
\end{document}
