Course: MCS 591, Extremal Combinatorics
Call no: 16600
Time: MWF 200-250pm
Place: TBD

Professor: Dhruv Mubayi
Office: 610 SEO
Tel: 6-6168
E-mail: mubayi@math.uic.edu
Course Web Page: http://www.math.uic.edu/~mubayi/591Spring06.html
Office Hours: TBD

Grading Policies:
You grade will be based on occasional homework assignments, class presentations, and discussions.

Disability Policy: Students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services (ODS). Please contact ODS a 312/413/-2183 (voice) or 312/413-0123 (TTY).

Prerequisite: Prerequisites: Ideal preparation is MCS 401, 421, 423, and 425, but almost all topics will be developed from scratch, and the only real prerequisite is ``mathematical maturity"

This course will cover the major results of extremal combinatorics, a subject which is about 100 years old. Throughout the course, we will present applications to problems in computer science. Proposed Topics and highlights include: Classical Results: 2-coloring hypergraphs -- Property B, sunflowers and delta systems, the Theorems of Erd\H os-Ko-Rado, Kruskal-Katona, Sperner, Dilworth, Ramsey, Van-der-Waerden, Hales-Jewett, Tur\' an. Linear Algebra methods in combinatorics: Fishers inequality, Ray-Chaudhuri--Wilson Theorem, explicit constructions of Ramsey graphs, disproof of Borsuk's conjecture. Probabilistic methods in combinatorics: First and Second moment method, deletion method, Local Lemma, entropy, randomized algorithms Applications in computer science: Lower bounds for boolean formulas and for threshold functions, hashing functions, universal sets and codes, separators, derandomization Text: Extremal Combinatorics with Applications in Computer Science, by Stasys Jukna, (Springer-Verlag 2001)