Very large graphs and their limits
LARGE SPARSE GRAPHS, GRAPH CONVERGENCE AND GROUPS SYLLABUS
Course Status: Elective
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.