UP - logo
E-resources
Peer reviewed Open access
  • Asymptotics in percolation ...
    Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny

    Random structures & algorithms, July 2020, 2020-07-00, 20200701, Volume: 56, Issue: 4
    Journal Article

    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 pc=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>pc. 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.