Workshop Graph limits in Bohemian Switzerland 2018
March 26-30, 2018
The aim of the workshop is to bring together junior and senior researchers working on the topic of graph limits, as well as related fields such as extremal graph theory, probability, or real analysis.
The focus of the workshop will be on limits of dense and sparse graphs, and related areas such as quasirandomness, extremal graph theory, inhomogeneous random graph models, and algorithms for large graphs.
Schedule can be found here.
Abstracts are available here.
We will have the following three lecture courses:
- Will Perkins (University of Birmingham): Gibbs measures, sparse graphs, and optimization
Syllabus. Slides. Lecture notes.
The hard-core model is a basic model from statistical physics in which a gas is represented by 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 crystallization phase transition from a disordered to an ordered state, representing a freezing phenomenon. While Gibbs measures like the hard-core model were developed in statistical physics, they have proved invaluable in a wide array of scientific disciplines including statistics, machine learning, and combinatorics. In this mini-course, we will focus on the use of Gibbs measures in graph theory and geometry. We will introduce methods that combine ideas from optimization and the theory of local weak convergence to prove results about independent sets and matchings in bounded-degree graphs, as well as sphere packings in Euclidean space.
- Oleg Pikhurko (University of Warwick): Descriptive graph combinatorics
We will discuss measurable versions of some classical combinatorial
problems (vertex/edge colourings, matchings, etc). Our main objects of
study will be so-called graphings, that appear as limit objects for
bounded degree graphs. We will mostly concentrate on positive results,
where a powerful tool for constructing
a measurable satisfying assignment is to design a parallel
decentralised algorithm that converges to it almost everywhere.
- Guus Regts (University of Amsterdam): Deterministic approximation algorithms for partition functions and zeros of graph polynomials with connections to sparse graph limits
Slides from Guus's lectures are available here
Recently Alexander Barvinok came up with a new approach for approximate counting besides the existing Monte Carlo Markov chain and correlation decay approach. The approach is based on writing the counting problem, e.g. the number of matchings in a graph, as the evaluation of a polynomial $p$ and truncating the Taylor series of $\log(p)$. This approach works well if $p$ has no complex zeros in the domain of interest. Together with Viresh Patel the speaker has shown that this approach leads to polynomial time algorithms essentially when the graphs have bounded degree.
In this mini course I will explain Barvinok's approach and the polynomial time speed up for bounded degree graphs. I will show some results concerning zeros of certain graph polynomials. I will focus on concrete examples, most notably the independence polynomial and the permanent. If time permits I will also say something about connections with sparse graph limits.
The workshop will take place in Janov in the heart of Bohemian Switzerland. The closest major town is Decin (16 km), with regular direct train connections to Prague (90mins), Dresden (40mins), and Berlin (3hours). You can search for public transport for example here (please note that there are several Janovs in Czechia, the one you want to go to is in district Decin).
From Decin to Janov there is an infrequent bus connection. On Sunday, the buses to Janov depart from Decin train station as follows: 12:34, 14:34, 16:34, 18:34, 21:34 and the price is 27 CZK. The ride takes 50mins. There are also several taxi companies based in Decin. Auto Taxi Decin operates 24/7. Their phone number is (+420)412520520. One way should be around 500 CZK or 23 Euro. Credit/debit cards are not accepted.
Currently, the capacity of the workshop has been reached.
Participants: (as of Feb 23, 2018):
The venue of the workshop is Hotel Devitka and a nearby Hotel U zeleneho stromu. A room with possible two persons occupancy is 1,800CZK/night in Devitka and 1500CZK/night in U Zeleneho Stromu (in case of room sharing, two separate receipts can be issued). A single bed room in U Zeleneho stromu is 1300CZK/night. Full board is paid separately. At the moment, all the accommodation has been arranged. The last day of the stay is March 30.
Indicate your arrival/departure time and select your meals in a form. I sent a link to the form to all participants on March 22, the title of the email was "Workshop Graph Limits in Bohemian Switzerland: Last minute information".
There is no workshop fee. Thanks to the generosity of the Alexander von Humboldt Foundation, there is some funding available to cover travel, local board and accommodation for participants with limited funding of their own.
The event is organized by Jan Hladky who is hosted at the Institute of Geometry, the Technical University Dresden. Jan's mobile phone numbers are (+420)702882615 (Czech, preferred) and (+49)1707639168 (German).
There will be a projector, a 180cm x 120cm whiteboard and a flipchart. The projector has VGA and HDMI inputs (and a computer can be borrowed if yours does not have these outputs).