Combinatorics

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