February 17. Introduction (Sections 1.1-1.5).
February 24. Homomorphisms, injective and induced; homomorphism densities; distance of graphs ``the cheap way''; definition of convergence (Sections 5.2.2, 5.2.3, first half of 11.1).
March 3. No class.
March 10. Regularity Lemma (for graphs and matrices); Counting Lemma (Sections 8.1.2, 9.1.1, 9.1.2, 10.5). The proofs are formulated for kernels in the book, see Section 9.2.2.
March 17. Existence of the limit graphon. We use the Regularity Lemma for graphons (Section 9.2), the Counting Lemma for graphons (Section 10.5), and the Martingale Convergence Theorem (Section A.3.6).
March 24. Examples of convergent graph sequences.
March 31. Distance of graphons. The metric space of graphons. A survey of results needed to complete the theory.
April 7. More on graph limits. Every graphon is a limit.
April 14. Spring break.
April 21. More on graph limits. Compactness of the graphon space.
April 28. Class cancelled. Make-up on May 12.
May 5. Applications of graph limits to parameter estimation.
May 12. Applications of graph limits to extremal graph theory: triangle density vs. edge density, the Cauchy-Schwarz method, graphons farthest from a hereditary property.
May 19. Other limit theories: hypergraphs (just two examples of random hypergraphs, showing the difficulties), and bounded degree graphs. Convergence, graphings, the Aldous-Lyons Conjecture.
Location:South Building 0.311.
Time: Friday 14:05-15:35
Topic of this semester: Limits of graphs
Lecture notes: Large networks and graph limits Book (pdf)
First homework posted Homework 1. (pdf)
Second homework posted Homework 2. (pdf)
Third homework posted Homework 3. (pdf)