Asymptotics in percolation on high‐girth expanders. Issue 4 (6th January 2020) - Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
Abstract : We consider supercritical bond percolation on a family of high‐girth d ‐regular expanders. The previous study of Alon, Benjamini and Stacey 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 the previous study that the second largest component, at any 0 < p < 1, has size at most n ω for some ω < 1 . We show that, unlike the situation in the classical Erdős‐Rényi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size n ω ′ for ω ′ arbitrarily close to 1. Moreover, as a by‐product of that construction, we answer negatively a question of Benjamini 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, for example, the existence of a linear path.