- You are here:
- Home

Department:

MATH

Course Number:

7016

Hours - Lecture:

3

Hours - Lab:

0

Hours - Recitation:

0

Hours - Total Credit:

3

Typical Scheduling:

Not currently offered

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.

Prerequisites:

MATH 4022 or consent of the School

Course Text:

No text

Topic Outline:

- 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