Spring 2020

Location:South Building 1-820.

Time: Friday 14:15-15:45. (After March 27: Consultation by Skype or email.)

Topic of this semester: Large networks and graph limits

In the last decades it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks: separable elements, with connections (or interactions) between certain pairs of them (the internet, social networks, ecological networks, the brain, chips etc.).

These huge networks pose exciting challenges for the mathematician. Graph Theory (the mathematical theory of networks) has been one of the fastest developing areas of mathematics in the last decades. In traditional graph theoretical problems the whole graph is exactly given, and we are looking for relationships between its parameters or efficient algorithms for computing its parameters. On the other hand, very large networks (like the Internet) are never completely known, in most cases they are not even well defined. Data about them can be collected only by indirect means like random local sampling. Dense networks (in which a node is adjacent to a positive percent of others nodes) and sparse networks (in which a node has a bounded number of neighbors) show a very diverse behavior.

One mathematical tool in their study is the theory of graph limits: structures that represent the limit of a sequence of graphs that are larger and larger and at the same time more and more similar to each other. This theory connects graph theory with analysis, and it will be the main topic of this course.

Familiarity with basic graph theory, linear algebra and probability is a prerequisite. More involved methods from these areas will be explained.

Book manuscript: Large networks and graph limits

Final published version: American Mathematical Society, Providence, RI, 2012

Homeworks: Homework No. 1.

Lecture topics:

• February 14. Large networks everywhere. What questions to ask? How are large networks given?

• February 21. Notion, versions and numbers of homomorphism. Relations between different kinds of homomorphism numbers. Examples of quantities expressible by homomorphisms. First definition of convergence of a graph sequence, examples.

• February 28. More examples of convergent sequences: random graphs G(n,p), sparse graphs. Definition of limit objects (graphons), and subgraph density in them, elementary properties. Definition of cut distance of labeled and unlabeled graphs (for a while, we need the easier labeled version).

• March 6. No class

• March 13. University is closed because of the corona virus.

• March 20. Spring break. We start reading course mode. Read Intro to the book and material about homomorphism numbers. Details in Homework No. 1.

• March 27. Main tool: Regularity Lemma. Reading on cut distance and the weak regularity lemma (for matrices). Details in Homework No. 2.

• April 4. Sampling lemmas (concentrate on the statements) and counting lemmas. Convergence of graph sequences and existence of limit objects. Details in Homework No. 3.

• April 18. Applications in extremal graph theory. Quasirandom graphs and Removal Lemma. Inequalities between subgraph densities, densities of complete graphs, and (without proofs) undecidability results on subgraph densities. Details in Homework No. 3.

• April 25. Applications in algorithms for property testing. Estimating graph parameters, distingushing graph properties, testing of graph properties.