% This file was created by EXP Version 5.0.

\documentclass[12pt]{article}
\usepackage[letterpaper,text={6in,8.5in}]{geometry}
\usepackage{indentfirst}%,indent}

\begin{document}
\title{Oral Qualifying Exam Syllabus}
\author{Stephen Hartke}
\date{December 13, 2001}
\maketitle
\begin{center}
Committee: Profs. J. Beck, F. Roberts, E. Boros
\end{center}

\section*{Graph Theory and Combinatorics}

\subsubsection*{Graph Theory}

%\begin{indentation}{1.5em}{0em} \parindent=-1.5em 
Basics of graphs.

K\"onigsberg bridge problem, Eulerian circuits, application to De Bruijn
cycles.

Spanning trees, Prim's and Kruskal's algorithms, connection to matroids,
Matrix Tree Theorem.

Planarity, Euler's formula, Kuratowski's theorem.

Digraphs, tournaments, strong connectivity, orientability, Robbins' theorem,
arc-vulnerability, vertex-vulnerability, transitive orientability,
Ghouila-Houri theorem.

Adjacency and incidence matrices, eigenvalues, Harary's theorem.

Vertex and edge connectivity, block decomposition, Menger's theorem, line
graphs and edge Menger's theorem, K\"onig's theorem, Hall's theorem,
matchings and coverings, 1-factors, Tutte's theorem, Dilworth's theorem,
flows in graphs, max flow-min cut, integrality.

Intersection graphs, Marczewski's theorem, interval graphs, circular arc
graphs, line graphs, clique graphs, food webs, competition graphs.

Forbidden subgraph problems, Mantel's theorem, counting triangles in $G$ and
$\overline{G}$, Moser-Moon theorem, Tur\a'an's theorem, Erd\H{o}s-Stone
theorem, Erd\H{o}s-Simonovits theorem.

Hamiltonian cycles and paths, Dirac's theorem, Ore's theorem, cycle lengths
in 2-connected graphs, Erd\H{o}s-Gallai theorem, Bondy's theorem on pancyclic
graphs, Erd\H{o}s-T. S\a'os conjecture.

Coloring problems: chromatic number, Brook's theorem, edge chromatic number,
Vizing's theorem, bipartite case, Szekeres-Wilf theorem, five color theorem,
four color theorem, chromatic number not a local property, perfect graphs,
perfect graph theorem, construction of triangle free graphs with arbitrarily
high chromatic number, list coloring and $H$-coloring.

Subdivisions and minors, topological subgraphs, Hajos' conjecture, the
topological clique number and chromatic number of a.a. graphs, Hadwiger's
conjecture.

%\end{indentation}
\bigskip

\noindent\emph{References}:

R. Diestel, \emph{Graph Theory}, Graduate Texts in Mathematics no. 173, 2000.

D.B. West, \emph{Introduction to Graph Theory}, Prentice Hall, 1996.

F. Roberts, \emph{Discrete Mathematical Models with Applications to Social,
Biological, and Environmental Problems}, Prentice Hall, 1976.

\subsubsection*{Combinatorics}

%\begin{indentation}{1.5em}{0em} \parindent=-1.5em 

Basics of counting,
generating functions, binomial coefficients, recursive sequences, Stirling's
formula.

Sperner's theorem, LYM inequality, Littlewood-Offord problem.

Intersecting families, Erd\H{o}s-Ko-Rado theorem.

Frankl and Wilson's Ramsey construction, Hadwiger's problem on coloring the
plane and Frankl's theorem, Borsuk conjecture and Kahn-Kalai counterexample.

2 coloring hypergraphs: uniform hypergraphs, bounded degree hypergraphs,
almost disjoint hypergraphs, Erd\H{o}s-Selfridge theorem, Beck-Fiala theorem.

Ramsey's theorem, K\"onig's lemma, compactness arguments, Van der Waerden's
theorem, Hales-Jewett theorem, Ramsey numbers, stepping up lemma, general
upper bounds, probabilistic lower bounds, Ajtai-Koml\a'os-Szemer\a'edi upper
bound for $R(3,n)$, matching lower bound.

%\end{indentation}
\bigskip

\noindent\emph{Reference}:

J. van Lint and R. Wilson, \emph{A Course in Combinatorics}. Cambridge
University Press, 1992.

\subsubsection*{The Probabilistic Method}

%\begin{indentation}{1.5em}{0em} \parindent=-1.5em 
Basics of probability,
linearity of expectation, inclusion-exclusion, Bonferroni inequalities,
Binomial and Poisson distributions are approximately normal, central limit
theorem and law of large numbers, conditional probabilities, law of total
probability.

Random graphs, monotone properties, threshold functions, relationship between
being connected and having no isolated vertices.

The second moment method, threshold function for having a certain graph as a
subgraph.

The local lemma, hypergraph discrepancy, Ramsey numbers, application to
coloring problems.

%\end{indentation}
\bigskip

\noindent\emph{Reference}: 

N. Alon and J. Spencer, \emph{The Probabilistic Method}, Wiley, 2000.

\section*{Discrete Optimization}

%\begin{indentation}{1.5em}{0em} \parindent=-1.5em 
Linear programming duality
theorem, Farkas' lemma, linear and integer programs, the parameters $\nu$,
$\nu_\kappa$, $\nu^\ast$, $\tau$, $\tau_\kappa$, and $\tau^\ast$ of a
hypergraph and their l.p. significance.

Minimax theorems: Menger's, K\"onig's, max-flow min-cut, Hoffman-Gale
circulation theorem, Dilworth's; proofs via Hoffman-Kruskal theorem.

Perfect graphs and associated hypergraphs, perfect graph theorem and
conjecture, properties of minimal non-perfect graphs, classes of perfect
graphs, Lov\a'asz' $\theta$ function, Shannon capacity of a graph, connection
to semidefinite programming.

Tutte's $1$-factor theorem, Edmonds' matching polyhedron, Gallai structure
theorem, use in Lov\a'asz' perfect matching algorithm, edge-coloring and
fractional edge-coloring, Chinese postman problem, $T$-joins and $T$-cuts,
Lucchesi-Younger theorem.

Four color problem, nowhere zero flows.

Total unimodularity, Ghouila-Houri theorem, other characterizations.

Approximability of hard problems: stability, max-cut, chromatic number;
polynomial algorithms for max-cut on planar graphs and weakly bipartite
graphs.

Stable marriage problem, algorithms, integrality of polyhedra.

%\end{indentation}
\bigskip

\noindent\emph{References}:

L. Lov\a'asz and M.D. Plummer, \emph{Matching Theory}, North-Holland, 1986.

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver,
\emph{Combinatorial Optimization}, J. Wiley, 1998.

A. Schrijver, \emph{Theory of Linear and Integer Programming}, J. Wiley, 1986.

\end{document}
