Click here for the course announcement.

Lecture date | Scribe | Topics | .tex | .ps | Other files | Posted | |
---|---|---|---|---|---|---|---|

M 8/26 & W 8/28 | Dave Kravitz | König-Hall, deficiency version of K-H, Euler's theorem | lect0828.tex | lect0828.ps | lect0828.pdf | 8/29 | |

W 9/4 | Amitabh Sinha | Dirac's theorem, Turán's theorem, random graphs | lect0904.tex | lect0904.ps | lect0904.pdf | 9/5 | |

M 9/9 | Nikhil Bansal | random bipartite graphs, definition of regularity, basic regularity facts, intersection property | lect0909.tex | lect0909.ps | lect0909.pdf | 9/13 | |

W 9/11 | Shuchi Chawla | union property, slicing lemma, random subpairs are regular | lect0911.tex | lect0911.ps | lect0911.pdf | 9/16 | |

M 9/16 | Venkatesh Natarajan | proof of random subpairs are regular, only need to check sets of smallest size to verify regularity | lect0916.tex | lect0916.ps | lect0916.pdf | 10/7 | |

W 9/18 | Abie Flaxman | the regularity lemma, proof using the main lemma | lect0918.tex | lect0918.ps | lect0918.pdf | 9/23 | |

M 9/23 | Giacomo Zambelli | proof of the main lemma | lect0923.tex | lect0923.ps | lect0923.pdf | 9/27 | |

W 9/25 | Shuchi Chawla | alternate form of the regularity lemma | lect0925.tex | lect0925.ps | lect0925.pdf | 10/2 | |

M 9/30 | Dave Kravitz | copies of
K, old Szemerédi lemma, original application
(van der Waerden), degree form_{q} | lect0930.tex | lect0930.ps | lect0930.pdf | 10/2 | |

W 10/2 | Nikhil Bansal | blow-up graphs, key
lemma, covering copies of H,
Erdõs-Stone/Erdõs-Simonovits | lect1002.tex | lect1002.ps | lect1002.pdf | fig1002.fig fig1002.eps | 10/7 |

M 10/7 | Amitabh Sinha | proof of key lemma, statement of (6,3)-theorem | lect1007.tex | lect1007.ps | lect1007.pdf | 10/7 | |

W 10/9 | Giacomo Zambelli | applications:
Ramsey-Turán for K, closeness to bipartite
graph, the _{4}(γ,δ,σ) property, 2-diameter
critical graphs, linear sized sparse graphs in dense graphs or their
complements, Erdõs-Sós | lect1009.tex | lect1009.ps | lect1009.pdf | 10/7 | |

M 10/14 | Nikhil Bansal | applications: Loebl's conjecture, Alon-Yuster; Blow-up Lemma, simple application of Blow-up Lemma | lect1014.tex | lect1014.ps | lect1014.pdf | 10/16 | |

W 10/16 | Venkatesh Natarajan | H-factors
in graphs, beginning of Alon-Yuster conjecture proof (by
Komlós, Sárközy, Szemerédi) | lect1016.tex | lect1016.ps | lect1016.pdf | 10/28 | |

M 10/21 | Abie Flaxman | proof of Alon-Yuster: getting clique-cover in
G_{r} | lect1021.tex | lect1021.ps | lect1021.pdf | fig1021a.eps fig1021b.eps fig1021c.eps fig1021d.eps | 11/4 |

W 10/23 | Amitabh Sinha | proof of Alon-Yuster:
show each pair of leftovers come from the same
K_{i} | lect1023.tex | lect1023.ps | lect1023.pdf | 10/25 | |

M 10/28 | Shuchi Chawla | proof of Alon-Yuster:
inserting vertices from V_{0} | lect1028.tex | lect1028.ps | lect1028.pdf | 10/29 | |

W 10/30 | Nikhil Bansal | proof of Alon-Yuster:
conclusion, the set Q | lect1030.tex | lect1030.ps | lect1030.pdf | 11/6 | |

M 11/4 | Abie Flaxman | Introduction of random graph model, small diameter results | lect1104.tex | lect1104.ps | lect1104.pdf | fig1104.eps | 11/13 |

W 11/6 | Dave Kravitz | Project: On a
Ramsey-Turán type problem | dkraproj.tex | dkraproj.ps | dkraproj.pdf | 11/6 | |

M 11/11 | Nikhil Bansal | Project: A
statistical theorem for set-addition | nbanproj.tex | nbanproj.ps | nbanproj.pdf | 11/13 | |

W 11/13 | Abie Flaxman | Project: Lower
bounds of tower type for Szemerédi's uniformity lemma |
aflaproj.tex | aflaproj.ps | aflaproj.pdf | 11/15 | |

W 11/20 | Amitabh Sinha | Project: The
maximum number of edges in a minimal graph of diameter 2 | asinproj.tex | asinproj.ps | asinproj.pdf | 11/22 | |

M 11/25 | Shuchi Chawla | Project: On sets
of integers containing no k elements in arithmetic
progression | In PowerPoint format: schaproj.ppt | 12/02 | |||

M 12/2 | Giacomo Zambelli | Project: The
algorithmic aspects of the Regularity Lemma | gzamproj.tex | gzamproj.ps | gzamproj.pdf | 12/13 | |

Final version of Homework 2 | hw2.tex | hw2.ps | hw2.pdf | 10/14 | |||

Solutions to Homework 2 | hw2ans.tex | hw2ans.ps | hw2ans.pdf | 12/16 | |||

Final version of Homework 1 | hw1.tex | hw1.ps | hw1.pdf | 10/7 | |||

Solutions to Homework 1 | hw1ans.tex | hw1ans.ps | hw1ans.pdf | 10/29 | |||

Project Ideas | projects.tex | projects.ps | projects.pdf | projects.bib The Alon - Duke - Lefmann - Rödl - Yuster paper (From Noga Alon's website) The Erdõs - Makai - Pach paper (From Janós Pach's website) The Gowers paper (From Tim Gowers' website) The Håstad - Wigderson paper which gives a construction showing the "induced matchings" result from the (6,3)-theorem is tight. Page 21 is relevant. From Johan Håstad's website. | 10/7 |