SRI ‘Phase Transitions in Combinatorics, Algorithms, Probability' (PhaseCAP)
Abstract/description
How can we understand the underlying structure of a large-scale network? Which local constraints impact the running time of an algorithm?
In recent years intuition from physics has become extremely fruitful in tackling these and related questions. Central among these ideas is the concept of a phase transition: a sudden shift in the global behaviour of a system driven by local interactions. A familiar example is water, which abruptly changes from ice to liquid as the temperature crosses a critical point.
In random network theory, a classic instance of this phenomenon occurs when the structure of connected components changes abruptly once a parameter passes a certain threshold. Related effects have also been identified in combinatorics and algorithmic theory, even in entirely deterministic settings—for example in counting complexity or extremal combinatorics. Many of these initially surprising behaviours are now being reinterpreted through the lens of phase transitions. This suggests that deeper, unifying principles are at work beneath the surface. Developing a systematic framework to capture these principles would help shed light on the questions raised above.
This SRI is designed to bring together leading researchers to tackle central problems at the intersection of these themes. Through focused, problem-driven collaboration, the goal is to generate new insights and advances. We hope that this work will act as a catalyst for further breakthroughs in this rapidly developing field.
This SRI started on 01-11-2025 and aims to reach its goals before 01-11-2027.
Goals
Our main goal is to connect different scientific communities through the lens of phase transitions. In particular, there is potential for greater connections among probability, combinatorics and algorithms, not only at a national level but also in the wider international scientific arena.
To support our aim of strengthening community ties across institutions and research areas, we will organise three open, interactive workshops centred on sharing ideas, tackling problems together, and launching new collaborations. We will also facilitate long-term visits from internationally recognised experts.
- The first workshop is scheduled in the week beginning 30 March 2026 and is centered around Probability. This includes topics such as sharp thresholds in random discrete structures and graph limits.
- The second workshop is scheduled in the week beginning 13 April 2026 and is centered around Combinatorics. This includes problems and methods that mix extremal and probabilistic combinatorics.
- The third workshop is scheduled in the week beginning 25 May 2026 and is centered around Algorithms. The topic of the workshop is algorithms for counting colouring, homomorphisms, satisfiable assignments, and phase transitions in these. This includes topics such as graph polynomials, parameterized complexity, approximate counting and randomised algorithms.
These workshops are done in collaboration with the CWI Research Semester Programme; see this page on the CWI website for further information.
The workshops bring together researchers from the 4TU universities working on combinatorics, algorithms and probability, as well as national and international experts in these fields.
Each workshop will have expert talks in the mornings and collaborative sessions in the afternoons with the aim to solve open problems proposed by the participants. We plan to advertise suitable talks to a wider audience, including master students. To prompt cohesion and interaction, we augment the workshops with weekly meetings of the organisers and the long-term participants as well as an online platform.
We are committed to fostering a diverse and inclusive environment, and will actively engage junior participants and provide them with unique opportunities to contribute to research and connect with experienced researchers. Our program enables our participants to get to know concurrent cutting edge research in computer science, mathematics and statistical physics and start new collaborations.
Participants
Contact person
- Noela Müller (TU Eindhoven)
Other members
- Ferenc Bencs (CWI)
- Jop Briët (CWI)
- Serte Donderwinkel (Groningen University)
- Carla Groenland (TU Delft)
- Ross Kang (University of Amsterdam)
- Guus Regts (University of Amsterdam)