Skip to main content
x

Summer School: Graphs, Groups, Stochastic Processes

2022.06.06. - 2022.06.10.
Erdős Center

Description

The School focuses on discrete structures and their limits. This is an active area of research that connects discrete mathematics with ergodic theory, stochastic processes, spectral theory, measured group theory and various branches of analysis and topology. There will be six minicourses given by distinguished researchers of the field. 


Lecturers:

  • Peter Csikvari (Rényi Institute)
  • Mikolaj Fraczyk (University of Chicago)
  • Yair Hartman (Ben-Gurion University)
  • Tom Hutchcroft (Caltech)
  • Dan Kral (Masaryk University)
  • Balint Virag (University of Toronto)

Mini-courses:

  • Peter Csikvari: Tutte polynomíal, random cluster model and graph limits

Abstract: Tutte polynomial is a 2-variable function that unifies a lot of counting problems about a graph  ranging from counting the number of proper colorings to counting the number of spanning trees or acyclic orientations. It is essentially the partition function of the so-called random cluster model in statistical physics. In this mini course we introduce the Tutte polynomial and study its basic properties. Then we study the limit of the normalized value of the Tutte polynomial along a sequence of d-regular graphs converging to the infinite d-regular tree. While investigating this problem we introduce a lot of important concepts like Bethe approximation, gauge transformation and empirical root measures.

  • Mikolaj Fraczyk: Growth in unimodular random graphs

Abstract: Let G be a bounded degree connected graph. We define the growth of G as the limit \(lim_{R\to\infty} |B(o,R)|^{1/R}\) where \(B(o,R)\) is the ball or radius R centered at a vertex \(o\). Transitive and quasi-transitive graphs always have growth. In general, the limit might not exist and we can only talk about the lower and the upper growths, defined respectively by lim-inf and lim-sup. The unimodular random graphs are often though of as the stochastic generalization of transitive or quasi-transitive graphs, so it is reasonable to ask whether the growth exists in such a random graph. Perhaps surprisingly, the answer is no. There is an example of a unimodular random tree with no growth, constructed by Adam Timar in 2012. This seemed to settle the question on the existence of growth for general unimodular random graphs. However, in a recent work with Miklos Abert and Ben Hayes we discovered a curious dichotomy. Once the upper growth in a unimodular random tree is high enough compared to the maximal degree, then the growth must exist. Along the way, we developed a new tool called “2-3-method”, which can used to prove existence of “growth-like” invariants in the unimodular random setting. On top of the existence of growth it shows that, for example:

  1. the number of length n walks in any unimodular random graph has growth,
  2. the sequence of return probabilities of a lazy random walk to an infinite connected component in any (!) translation invariant percolation on a Cayley graph has growth.

In my lectures I will explain the Timar’s construction, the 2-3 method, I will show how it applies to to growth and finally I will state some conjectures about the relation between the hyperfiniteness and the existence of growth.

  • Yair Hartman: An invitation to Furstenberg-Poisson boundary.

Abstract: The Furstenberg-Poisson boundary is an object associated with a random walk of an infinite group. While this object is of interest from a probabilistic point of view, it turned out to be very important in the study of groups (even for questions that involve no random walks at all!). In the lectures, we will discuss the motivation, define this object, and learn its basics.

  • Tom Hutchcroft: Uniqueness and nonuniqueness in percolation

Abstract: I will give a survey of uniqueness and non-uniqueness theorems for percolation on groups, including both classical and more recent results. Time permitting, I will also review connections to the theory of cost and to the theory of mean-field critical behaviour.

  • Dan Kral: Combinatorial limits and flag algebra method

Abstract: The theory of combinatorial limits provide analytic tools to represent and analyze large discrete objects. Such tools have found important applications in various areas of computer science and mathematics. One of the most prominent areas of such applications is extremal combinatorics, where the closely related flag algebra method led to solving several long-standing open problems. During this minicourse, we will introduce the flag algebra method and demonstrate the method in various settings in extremal combinatorics. We will also discuss how the method is applied with computer assistance.

  • Balint Virag: Random plane geometry

Abstract: Consider \(Z^2\), and assign a random length of 1 or 2 to each edge based on independent fair coin tosses. The resulting random geometry is conjectured to have a scaling limit. Most random plane geometric models (including hidden geometries) should have the same scaling limit. I will explain the basics of the limiting geometry, the "directed landscape", the central object in the class of models named after Kardar, Parisi and Zhang.


If you are interested in participating, please send an email to large.networks@renyi.hu with the subject line "Summer School: Graphs, Groups, Stochastic Processes". The email should include your full name and affiliation. We will send you information on when application and registration opens, on fees, possible funding, the detailed descriptions of minicourses and deadlines.

Your e-mail address will be handled with special care. It will only be used for communicating news related to the Summer School; the organizers do not pass it to third parties, and the address will be deleted when the Summer School ends.

Application is now open. Application deadline: March 1, 2022
Link to the registration web-form of the Summer School:

Organizers

Miklós Abért
László Lovász
Gábor Pete
Balázs Szegedy

Invited Speakers

Peter Csikvari (Rényi Institute)
Mikolaj Fraczyk (University of Chicago)
Yair Hartman (Ben-Gurion University)
Tom Hutchcroft (Caltech)
Dan Kral (Masaryk University)
Balint Virag (University of Toronto)

Participants