Course: MCS 591, Advanced Topics in Combinatorial Theory: Extremal combinatorics CRN: 37067
Time: MWF 12:00-12:50pm Place: 2SES 136
Professor: Dhruv Mubayi Office: 620 SEO E-mail: mubayi@uic.edu Course Web Page:
http://www.math.uic.edu/~mubayi/591/Spring2016/Extremal.html
Office Hours: MWF11-12 (or any time that I am in my office)
Grading Policies:
You grade will be based on occasional homework assignments, class presentations, and discussions.
Disability Policy: Students with disabilities who require accommodations for\
ac
cess and participation in this course must be registered with the Office of Dis\
ability Services (ODS).
Please contact ODS a 312/413/-2183 (voice) or 312/413-0123 (TTY).
Prerequisite:
An undergraduate course in combinatorics/graph theory or probability, and the mathematical maturity of a (relatively advanced) graduate student.
Course Description: Extremal combinatorics studies the extreme value of a parameter over a class of discrete objects. The subject has been growing for the past century and by now it encompasses some of the most important contributions to combinatorics and has applications to many other disciplines including discrete geometry, number theory, coding theory, computer science. This course will study the modern developments in the subject focusing on graph and hypergraph theory. Throughout the course open problems will be presented that are suitable for thesis research.
A sampling of topics:
- Ramsey numbers of graphs and hypergraphs including recent work on asymmetric Ramsey numbers for hypergraphs, the Erdos-Rogers problem, and multicolor Ramsey numbers.
- Methods in extremal graph and set theory, including classical extremal graph theory (Zarankiewicz problem, Erdos-Simonovits-Stone theorem) and more recent probabilistic tools (dependent random choice) and algebraic constructions (Projective Norm graphs); extensions of classical results in extremal set theory (Erdos-Ko-Rado type theorems), the delta system method, the random walk method, and more recent approaches using sampling and shadows. Along the way, we will introduce and use linear algebra methods.
- Graph and Hypergraph Regularity Lemmas (of Gowers, Frankl-Rodl, and Tao) and accompanying removal lemmas; applications to Roth's theorems on arithmetic progressions and the multidimensional Szemeredi theorem.
- Quasirandom structures focusing on recent developments on hypergraph quasirandomness.
For the linear algebra part, we will use the text
Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science by Babai and Frankl. Do not try to get the book yourself.
I will explain how to get the book after class has begun. We will use class notes and papers available on the internet for all the other topics.
HW 1 Due Friday September 2
HW 2 Due Friday September 16
HW 3 Due Friday September 30
HW 4 Due Friday October 14
HW 5 Due Friday October 28
HW 6 Due Friday November 11
HW 7 Due Monday November 28