Seminar series
Date
Tue, 19 Nov 2019
Time
14:00 -
15:00
Location
L6
Speaker
Endre Csóka
Further Information
We analyze the asymptotic relative size of the largest independent set of a random d-regular graph on n → ∞ vertices. This problem is very different depending on d because of a surprising phase transition. This is somewhat similar to finding the density of ``water'' above and below its freezing point. These phase transitions are related to algorithmic thresholds, mixing properties, counting, graph reconstruction, graph limits and other questions. We are still far from a complete understanding of all these questions. Our tools are partially coming from statistical physics.