|
|
Grades: Grades will be determined by four equally-weighted items:
You will have at least two weeks for each homework assignment and at least a month to prepare for the in-class presentation. The problem assignments will focus on filling the gaps in the lectures.
Weekly schedule: On the first day of class, we will attempt to convert the inconvenient schedule of 3 fifty-minute class periods per week to the ever-more pleasurable 2 seventy-five-minute class periods per week.
Texts: For my lectures, I will be referencing a variety of papers -- the backbone of the course will be the survey:
J. Komlós and M. Simonovits, Szemerédi's Regularity Lemma and its applications in graph theory. DIMACS Technical Report 96-10.
Schedule: This schedule is subject to both minor and major changes.
Note that it is a 14-week schedule, which ignores in-class
presentations. Topics for student in-class presentations are best chosen
from the topics covered from "weeks" 8-14.
| Dates | Topic |
|---|---|
| Week 1 | Basics of extremal graph theory, Dirac's theorem, Turán's theorem |
| Week 2 | Random graphs and epsilon-regularity |
| Week 3 | The Regularity Lemma -- forms and proofs |
| Week 4 | The Regularity Lemma -- connections to number theory |
| Week 5 | The Regularity Lemma -- Turán-type applications |
| Week 6 | The Regularity Lemma -- Other applications |
| Week 7 | Super-regularity and the Blow-up Lemma |
| October 14 | Scheduled due date for Homework #1 |
| Weeks 8-10 | Bounded-degree spanning subgraphs -- using the Regularity and Blow-up Lemmas in tandem |
| Week 11 | The Hajnal-Szemerédi theorem |
| Week 12 | Algorithmic aspects of the Regularity Lemma |
| Week 13 | Algorithmic aspects of the Blow-up Lemma |
| December 2 | Scheduled due date for Homework #2 |
| Week 14 | Generalizations of the Regularity Lemma |
