Endre Csóka (Rényi): Local Algorithms on Sparse Random Graphs

Abstract:

We examine the structures and phase transitions in large random graphs. For example, the structure of a largest independent set in a random d-regular graph on n→∞ vertices is in a "solid state" for d≥20 but probably in a "spin glass state" for d≤19 . We are using the tools of graph limit theory, local algorithms (IID-factor processes), and probability theory, and we are trying to translate and extend some intuitive arguments in statistical physics into this mathematical language.