Asymptotics in bond percolation on expanders
Vortrag von Prof. Dr. Benjamin Sudakov
Datum: 18.04.18 Zeit: 17.15 - 19.00 Raum: Y27H12
The evolution of the largest connected component has been studied intensely in a variety of random graph processes, starting with celebrated work of Erdos-Renyi, who in 1960 proved that a random subgraph of an $n$-vertex complete graph undergoes a phase transition at edge probability $1/n$ when, asymptotically almost surely, a linear-sized (``giant'') component appears.
In this talk we consider edge percolation on a family of high-girth $d$-regular expanders. Alon-Benjamini-Stacey in 2004 established that a critical probability for the appearance of a giant component in this case is $p_c=1/(d-1)$. Our main result recovers the sharp asymptotics, similar to the classical Erdos-Renyi result, of the size and degree distribution of the vertices in the giant component at any $p>p_c$. On the other hand we show that, unlike the situation in the classical random graph case, the second largest component in edge percolation on a regular expander, even with an arbitrarily large girth, can have size at least $n^a$ for any fixed $a<1$. Several related results will be discussed as well. Joint work with Krivelevich and Lubetzky.