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

Lecture date	Scribe	Topics	.tex	.ps	.pdf	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 Kq, old Szemerédi lemma, original application (van der Waerden), degree form	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 K4, closeness to bipartite graph, the (γ,δ,σ) 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 Gr	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 Ki	lect1023.tex	lect1023.ps	lect1023.pdf		10/25
M 10/28	Shuchi Chawla	proof of Alon-Yuster: inserting vertices from V0	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