Very large graphs and their limits

Course Description: 


Level:  Doctoral
Course Status:  Elective

Full description: 

Brief introduction to the course:

A family of finite graphs is sparse, if the number of edges of a graph in the family is proportional to the number of its vertices. Such families of graphs come up frequently in graph theory, probability theory, group theory, topology and real life applications as well. The emerging theory of graph convergence, that is under very active research in Hungary, handles large sparse graphs through their limit objects (examples are unimodular random graphs and graphings). The topic is related to group theory, more precisely, the theory of residually finite and amenable groups and their actions in various ways. A general tool used throughout the course is spectral theory of graphs and groups.

The goals of the course:

The course gives an introduction to the emerging theory of graph convergence, together with its connections to group theory and ergodic theory. The course also serves as a theoretical background for network science.

The learning outcomes of the course:

By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course, and how to use these methods to solve specific problems. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general.

More detailed display of contents:

Week 1. Space of rooted graphs, neighborhood sampling, invariant processes on vertex transitive graphs  

Week 3. Basic spectral theory of graphs, expander graphs and random walks

Week 4. Spectral measure and the eigenvalue distribution

Week 5. Random rooted graphs, Benjamini-Schramm convergence, property testing

Week 6. The tree entropy is testable  

Week 7. Residually finite, amenable and sofic groups  

Week 8. Kesten’s theorem

Week 9. Ergodic theory of group actions and graphings

Week 10. Hyperfiniteness

Week 11. Coloring entropy, root measures and the matching ratio 

Week 12. Invariant random subgroups


L. Lovasz: Large networks and graph limits, AMS, 2012.