Regularity Lemma/Extremal Graph Theory
The Regularity Lemma/Extremal Graph Theory Archive

Click here for the main page.
Click here for the course announcement.

Lecture filesPosted
M 8/26 & W 8/28Dave KravitzKönig-Hall, deficiency version of K-H, Euler's theoremlect0828.texlect0828.pslect0828.pdf8/29
W 9/4Amitabh SinhaDirac's theorem, Turán's theorem, random graphslect0904.texlect0904.pslect0904.pdf9/5
M 9/9Nikhil Bansalrandom bipartite graphs, definition of regularity, basic regularity facts, intersection propertylect0909.texlect0909.pslect0909.pdf9/13
W 9/11Shuchi Chawlaunion property, slicing lemma, random subpairs are regularlect0911.texlect0911.pslect0911.pdf9/16
M 9/16Venkatesh Natarajanproof of random subpairs are regular, only need to check sets of smallest size to verify regularitylect0916.texlect0916.pslect0916.pdf10/7
W 9/18Abie Flaxmanthe regularity lemma, proof using the main lemmalect0918.texlect0918.pslect0918.pdf9/23
M 9/23Giacomo Zambelliproof of the main lemmalect0923.texlect0923.pslect0923.pdf9/27
W 9/25Shuchi Chawlaalternate form of the regularity lemmalect0925.texlect0925.pslect0925.pdf10/2
M 9/30Dave Kravitzcopies of Kq, old Szemerédi lemma, original application (van der Waerden), degree formlect0930.texlect0930.pslect0930.pdf10/2
W 10/2Nikhil Bansalblow-up graphs, key lemma, covering copies of H, Erdõs-Stone/Erdõs-Simonovitslect1002.texlect1002.pslect1002.pdffig1002.fig
M 10/7Amitabh Sinhaproof of key lemma, statement of (6,3)-theoremlect1007.texlect1007.pslect1007.pdf10/7
W 10/9Giacomo Zambelli applications: Ramsey-Turán for K4, closeness to bipartite graph, the (γ,δ,σ) property, 2-diameter critical graphs, linear sized sparse graphs in dense graphs or their complements, Erdõs-Sóslect1009.texlect1009.pslect1009.pdf10/7
M 10/14Nikhil Bansal applications: Loebl's conjecture, Alon-Yuster; Blow-up Lemma, simple application of Blow-up Lemmalect1014.texlect1014.pslect1014.pdf10/16
W 10/16Venkatesh Natarajan H-factors in graphs, beginning of Alon-Yuster conjecture proof (by Komlós, Sárközy, Szemerédi)lect1016.texlect1016.pslect1016.pdf10/28
M 10/21Abie Flaxman proof of Alon-Yuster: getting clique-cover in Gr lect1021.texlect1021.pslect1021.pdffig1021a.eps
W 10/23Amitabh Sinha proof of Alon-Yuster: show each pair of leftovers come from the same Ki lect1023.texlect1023.pslect1023.pdf10/25
M 10/28Shuchi Chawla proof of Alon-Yuster: inserting vertices from V0 lect1028.texlect1028.pslect1028.pdf10/29
W 10/30Nikhil Bansal proof of Alon-Yuster: conclusion, the set Q lect1030.texlect1030.pslect1030.pdf11/6
M 11/4Abie Flaxman Introduction of random graph model, small diameter results lect1104.texlect1104.pslect1104.pdffig1104.eps11/13
W 11/6Dave Kravitz Project: On a Ramsey-Turán type problem dkraproj.texdkraproj.psdkraproj.pdf11/6
M 11/11Nikhil Bansal Project: A statistical theorem for set-addition nbanproj.texnbanproj.psnbanproj.pdf11/13
W 11/13Abie Flaxman Project: Lower bounds of tower type for Szemerédi's uniformity lemma aflaproj.texaflaproj.psaflaproj.pdf11/15
W 11/20Amitabh Sinha Project: The maximum number of edges in a minimal graph of diameter 2 asinproj.texasinproj.psasinproj.pdf11/22
M 11/25Shuchi Chawla Project: On sets of integers containing no k elements in arithmetic progression In PowerPoint format: schaproj.ppt12/02
M 12/2Giacomo Zambelli Project: The algorithmic aspects of the Regularity Lemma gzamproj.texgzamproj.psgzamproj.pdf12/13
Final version of Homework 2 hw2.texhw2.pshw2.pdf10/14
Solutions to Homework 2 hw2ans.texhw2ans.pshw2ans.pdf12/16
Final version of Homework 1 hw1.texhw1.pshw1.pdf10/7
Solutions to Homework 1 hw1ans.texhw1ans.pshw1ans.pdf10/29
Project Ideas projects.texprojects.psprojects.pdfprojects.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.

Ryan Martin's CMU MATH 801 Archive Page / Revised 8/19/04.