Asymptotics in percolation on high-girth expanders

Michael Krivelevich, Eyal Lubetzky, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

Abstract

We consider supercritical bond percolation on a family of high-girth (Formula presented.) -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 (Formula presented.). 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 (Formula presented.). It was further shown in the previous study that the second largest component, at any (Formula presented.), has size at most (Formula presented.) for some (Formula presented.). 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 (Formula presented.) for (Formula presented.) 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.

Original languageEnglish (US)
Pages (from-to)927-947
Number of pages21
JournalRandom Structures and Algorithms
Volume56
Issue number4
DOIs
StatePublished - Jul 1 2020

Keywords

  • bond percolation
  • component sizes
  • giant component
  • high-girth expanders

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Asymptotics in percolation on high-girth expanders'. Together they form a unique fingerprint.

Cite this