Asymptotics in percolation on high-girth expanders

Michael Krivelevich, Eyal Lubetzky, Benny Sudakov

Published 2018-03-30, updated 2020-01-08Version 2

We consider supercritical bond percolation on a family of high-girth $d$-regular expanders. Alon, Benjamini and Stacey (2004) established that its critical probability for the appearance of a linear-sized ("giant'') component is $p_c=1/(d-1)$. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2-core at any $p>p_c$. It was further shown in [ABS04] that the second largest component, at any $0<p<1$, has size at most $n^{\omega}$ for some $\omega<1$. We show that, unlike the situation in the classical Erd\H{o}s-R\'enyi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size $n^{\omega'}$ for $\omega'$ arbitrarily close to $1$. Moreover, as a by-product of that construction, we answer negatively a question of Benjamini (2013) on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, e.g., the existence of a linear path.