Fundamental combinatorial structures including hypergraphs, transversal sets, colorings, Sperner families, intersecting families, packings and coverings, perfect graphs, and Ramsey theory. Algebraic and topological methods, applications.
MATH 4022 or consent of the School
- Ramsey Theory - Ramsey's theorem (finite and infinite), Ramsey numbers, lower and upper bounds, graph Ramsey theory, Erd\"os-Szekeres' theorem, van der Waerden's theorem, Hales-Jewett's theorem
- Hypergraphs - Sperner families, the Littlewood-Offord problem, Kruskal-Katona's theorem, intersecting hypergraphs (Erd\"os-Ko-Rado's theorem), saturated hypergraphs
- Packing and Covering - The Chinese postman problem, Seymour's theorem and application to multicommodity flows, Lucchesi-Younger's theorem, introduction to polyhedral combinatorics
- Colorings - Rado's selection lemma (compactness principle), graphs with large girth and chromatic number, algebraic approach to coloring, choosability, edge-colorings, perfect graphs
- Topological Methods - The necklace problem, the chromatic number of Kneser graphs, Gyori's theorem
- Matroid Theory - Axiom systems of a matroid, examples, Rado's theorem, matroid intersection, regular matroids and totally unimodular matrices