Networks

Algorithmic and combinatorial aspects of partition functions

Summary This project concerns the study of various aspects of partition functions and graph polynomials. This is a very active area of research and lies at the interface of combinatorics, probability, theoretical computer science, and statistical physics. The partition function of the Potts model and the hardcore model, also known as the Tutte polynomial and the independence polynomial respectively are prototypical examples. Evaluating these polynomials at certain points gives a lot of information about the graphs, e.g. the number of independent sets, the number of spanning trees, the number of proper q-colourings of a graph, etc. Some of the fundamental questions in this area include: What sort of network structure allows for efficient computation of the partition function? Which network structures maximizes/minimizes the partition function? How does the partition function of a random network behave? Recent developments have shown strong connections between phase transitions in statistical physics and answers to these type of questions.
Supervisors Viresh Patel (UvA) and Guus Regts(UvA)
PhD Student Maurizio Moreschi
Location Universiteit van Amsterdam (UvA)