Summer school: Techniques in Random Discrete Structures
University of Athens, Greece, May 22-27
The aim of this school is to acquaint graduate students and researchers with some of the most exciting phenomena and techniques around random discrete structures. It consists of the following three mini-courses, comprising five 90-minute lectures each.
Amin Coja-Oghlan (Frankfurt): Phase transitions in random structures
Since the early 2000s physicists have put forward exciting predictions on phase transitions in random graphs and the combinatorial phenomena that cause them. Recently significant advances have been made toward putting the physics calculations on a rigorous basis. This has led to fantastic results in the theory of random graphs as well as to breakthroughs in coding theory and related areas. In this lecture series I will give an introduction to this work, from the physics intuition to the rigorous state of the art, and highlight promising future directions.
Will Perkins (Birmingham): Gibbs measures in statistical physics and combinatorics
The hard-core model is a basic model from statistical physics in which gas molecules are represented by vertices of a random independent set from a graph. As the typical density of this independent set increases on a lattice like Z^d, the model undergoes a phase transition from a disordered to an ordered state, which represents a crystallization phase transition in physics. While Gibbs measures such as the hard-core model were developed in statistical physics, they have proved invaluable in many seemingly distant scientific areas including statistics, machine learning, and combinatorics. In this mini-course, we will focus on the use of Gibbs measures in combinatorics and graph theory, and in particular on the extremal theory of sparse graphs. We will answer questions such as “Which d-regular graph has the most matchings?” using methods that combine probability, statistical physics, and optimization. Along the way, many open research problems and directions will be presented. The course will include exercises and some hands-on demonstration of computer-assisted proof techniques.
Stephan Wagner (Stellenbosch): Analytic Combinatorics
The analysis of generating functions is a powerful tool for the exact and asymptotic enumeration of discrete structures as well as the study of parameters of random structures. Typical examples include trees and other types of graphs, words over finite alphabets, permutations, compositions, number partitions and set partitions. I will provide an introduction to some common techniques in this area, such as singularity analysis of generating functions, the saddle point method and the quasi-power theorem. By means of different topical examples, I will show how these methods can be applied to determine asymptotic enumeration formulas as well as limit theorems for random discrete structures.
Organisers: Agelos Georgakopoulos & Dimitris Cheliotis