Asymptotics in percolation on high‐girth expanders. Issue 4 (6th January 2020)

• Record Type: Journal Article
• Authors: Krivelevich, Michael; Lubetzky, Eyal; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 927
• Page End: 947
• Publication Date: 2020-01-06
• Subjects: bond percolation -- high‐girth expanders -- giant component -- component sizes; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20903
• Languages: English
• ISSNs: 1042-9832

Abstract

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.