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)

• 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.

• First homework posted Homework 1. (pdf)

Second homework posted Homework 2. (pdf)

Third homework posted Homework 3. (pdf)