• (4/11,4/13) Week 13 topic: Finish expander graphs. Begin Chung-Lu random graph model.
• (4/4,4/6) Week 12 topic: Introduction to expander graphs.
• (3/28,3/30) Week 11 topic: Mean plus variance gives regularity.
• (3/21,3/23) Week 10 topic: Continuing Tripartite version of Corrádi-Hajnal.
• Upcoming topics: In week 10, we will continue with the proof of the tripartite version of Corrádi and Hajnal. In week 11, we will continue that proof and begin the proof that degree sequence plus the codegree sequence is enough to determine ε-regularity (look for the Froebenius norm!). Week 12 will see the end of that proof and we will show the beautiful Hoffman-Singleton theorem. In weeks 13-15, we have some remaining options for a topic: (1) Quasi-random graphs, (2) Expander graphs, (3) Linear programming methods in graph theory. Think about what you most want to see for the last 5 lectures.
• Special lectures: On Wednesday, Mar. 8 at 9am and Wednesday, Mar. 22 at 9am, each in Carver 196, I will be giving two hour-long lectures on smoothed analysis in graphs. This is the process of adding random edges and seeing the results. This is a lecture that may generate some independent interest in the probability community. The first lecture will introduce the topic and provide a survey of results. The second will prove a result on diameter. Room Carver 196.
• (3/7,3/9) Week 9 topic: A packing result using the Regularity Lemma.
• (2/28,3/2) Week 8 topic: Blow-up Lemma, packing results of the Regularity Lemma, Alon-Yuster theorem.
• (2/21,2/23) Week 7 topic: Degree Form of the Regularity Lemma, the Key Lemma, number of copies of H, covering copies of H, super-regular pairs, early Regularity Lemma results.
• Request: Can you email me your schedules? I would like to find a time to do a makeup class or two.
• (2/14,2/16) Week 6 topic: Finishing the proof of the Regularity Lemma. Applications of the Regularity Lemma.
• Archive Page: The archive page holds the lecture notes as well as the homework assignments.
• Office Hours: M 3:10-4:00 and T 2:10-3:00 The probability seminar is doing a series on the preferential attachment model of random graphs at 2:10 on Thursdays. So, I will have office hours now M 3:10-4:00 and T 2:10-3:00. I will usually be available on Friday 2:10-3:00
• (2/7,2/9) Week 5 topic: The proof of the Regularity Lemma.
• (1/31,2/2) Week 4 topic: Random bipartite graphs, ε-regular pairs, properties of ε-regular pairs.
• (M 1/30) Makeup class postponed! The "mandatory" makeup for class in the discrete math seminar is now tentatively scheduled for March 20th. Richard Kramer will be speaking at the seminar at that time on Definability in Geometry and the Product Rule for Derivations, Pts. I & II.
• (M 1/30) Makeup class: Discrete math seminar, Monday, January 30, 2006 in 202 Carver. If you cannot attend, the slides are found by clicking here. This talk can be thought of as a preview of things to come.
• (1/26) Week 3 topic: More on random graphs and properties of random bipartite graphs.
• (1/17,1/19) Week 2 topic: Random graphs: First moment method, Second moment method, independent sets, small subgraphs.
• Class cancelled 1/24: There will be no class on Tuesday, January 24. To make up for this, there will be extra homework. No, I am kidding. (Or, am I?) One "makeup" time will be "mandatory" attendance of the Discrete Math Seminar on January 30, 2006, where I will talk about an application of the Regularity lemma.
• Office Hours: M 3:10-4:00, Θ 2:10-3:00.
• Office Hours: I haven't had time to settle office hours. For Tuesday, January 17, I will be in my office (428 Carver) from 10-12. Please remind me to announce office hours then.
• Corrections: The "Hall" in König-Hall is Philip Hall. Marshall Hall was a contemporary -- no relation. For the first homework problem, it is true as stated but not best possible. The degree condition should be (1-2^1-k)N instead of just -k in the exponent. It is corrected in the lecture notes and in the homework problem list on the archive page.
• (1/10,1/12) Week 1 topic: Turán, Dirac, Hajnal-Szemerédi, Ramsey, anti-Ramsey. Guest lecturer on Thursday, Jan. 12: Maria Axenovich.

Click here for the syllabus.
Click here for the archive page.
Click here for the course announcement.