\documentclass[11pt,a4paper]{article}
\author{Padmini}
\title{Oral Syllabus}
\begin{document}

\begin{center}{\LARGE{\bf Oral Syllabus}}
\\
Committee:  Profs. J\'{o}zsef Beck (chair), Jeff Kahn, William Steiger, Endre Szemer\'{e}di
\end{center}

\section{Combinatorics, Graph Theory and the Probabilistic Method}

\subsection{Combinatorics}

Basic Enumeration: Basic Counting, representations of permutations, Recurrence relations, Generating functions, Principle of Inclusion-Exclusion, Reflection principle (Ferrer's)

Set Systems, Posets: Dilworth's thm, Erd\H{o}s-Ko-Rado, Sperner's theorem, LYM inequality, Raychaudhuri-Wilson, Frankl-Wilson, Littlewood-Offord, Kruskal-Katona, Fisher's and Generalized Fisher's inequality, Baranyai's theorem, Borsuk conjecture and Kahn-Kalai counter example, Harper's theorem

Combinatorial Nullstellensatz, application to Cauchy-Davenport and Chevalley-Warning 

Ramsey theory: Infinite Ramsey, finite Ramsey, Van der Waerden, Szemer\'edi's thm, probabilistic lower bounds, Roth's theorem, Hales-Jewett
\linebreak

Ref: Van/Lint-Wilson, Bollobas

\subsection{Graph Theory}

Matching theory: Hall/K\"onig and applications, stable matching, Tutte's 1-factor theorem, Gallai and Millgram thm, path covers and Dilworth's thm

Connectivity: 2-connected graphs, 3-connected graphs, Mader's theorem, edge-disjoint spanning trees, paths between given pair of points, Menger's theorem

Algorithms: Kruskal's, Dijkstra's, Max Flow Min Cut

Planar graphs: Euler, Kuratowski, Wagner, plane duality, abstract duality

Graph colouring: Vertex colouring(Brook's), edge colouring - Vizing's thm, K\"onig's theorem, Hadwiger's conjecture, perfect graphs, Thomassen's 5-list colouring of planar graphs, statement of weak/strong perfect graph theorem, 5-colour theorem

Extremal: Turan's, Erd\H{o}s-Stone, Ramsey type results, Szemer\'edi's Regularity lemma, Chv\'atal-R\"odl-Szemer\'edi-Trotter \\

Ref: Diestel

\subsection{Probabilistic method}

Basics: Linearity of Expectation, Bonferroni ineq, Binomial and Poisson distributions, Conditional Probability, Law of Total Probability, Chernoff bound, Coupling and stochastic domination, Alterations

Second moment method: Chebyshev's ineq, general procedure, threshold function for containing a given subgraph

Lov\'asz's Local Lemma: symmetric and general versions, applications to Ramsey lower bounds

Poisson paradigm: Janson ineq, application to number of triangles in $G_{n,p}$, Brun's sieve, application to number of isolated points in $G_{n,p}$.

Random graphs: $G_{n,p}$ vs $G_{n,k}$, threshold functions, probabilistic refutation of Haj\'os conjecture, connectedness\\

Ref: Alon-Spencer

\section{Discrete and Computational Geometry}

\subsection{Discrete Geometry}

Convexity: Radon's, Helly, statement of Centerpoint and Ham-sandwich, Erd\H{o}s-Szekeres, Horton sets 

Incidence problems: Szemer\'edi-Trotter, lower bounds of incidences and unit distances, incidences and distinct distances via crossing numbers, Cutting lemma

Levels: Clarkson's thm, Zone theorem

Lower envelopes: complexity, Davenport-Schintzel sequences

Intersection patterns of Convex sets: Fractional Helly, Colorful Caratheodory, Tverberg's

Selectional lemmas, Transversals, Epsilon nets, VC-dimension, k-sets, halving sets: bounds (using Clarkson's, better bounds in the plane)\\

Ref: Matousek

\subsection{Computational Geometry}

Convex Hulls: 2D, 3D. convex hull through duality, Kirpatrick-Seidel optimal algorithm, lower bounds.

Incremental and Randomized algorithms - applications to halfplane intersection, convex hulls, linear programming. Backward analysis, trapezoidation (Monte-Carlo and Las-Vegas construction).

lower bounds: comparison model, elemental uniqueness, linear decision trees, Dobkin-Lipton theorem, algebraic decision trees, Ben-Or's theorem

Intersections: plane sweep

fixed radius neighbors: bucketing method

Triangulation and Partitioning: art gallery problem

Low-dimensional Linear Programming: Megiddo's $O(n)$ algorithm.

Line arrangements and Duality

Ham-sandwich cuts: Megiddo's optimum algorithm in the seperated case, Edelsbrunner-Waupotitsch, Willard's equipartitioning, Matousek-Lo-Steiger's optimum algorithm in the general case 

Voronoi Diagrams and Delaunay Triangulations: Guibas-Knuth-Sharir\\

Ref: Berg-Kreveld-Overmars-Schwarzkopf

\vfil\eject

\end{document}

