Summer school: Techniques in Random Discrete Structures

Πότε 22/05/2017 09:15 έως
27/05/2017 18:00
Που Department of Mathematics, UoA
Προσθήκη γεγονότος στο ημερολόγιο vCal


A summer school around combinatorics, probability, and statistical physics. May 22-27 (Monday to Saturday), Department of Mathematics, University of Athens. Three courses, each consisting of five 90 minute lectures.


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.


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

This event is sponsored by the ERC project "Random Graph Geometry and Convergence".

All participants are required to register here

Περισσότερες πληροφορίες σχετικά με το γεγονός