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. 

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 15:24.