Percolation with small clusters on random graphs

Abstract

Consider the problem of determining the maximal induced subgraph in a random $d$-regular graph such that its components remain bounded as the size of the graph becomes arbitrarily large. We show, for asymptotically large $d$, that any such induced subgraph has size density at most $2(\log d)/d$ with high probability. A matching lower bound is known for independent sets. We also prove the analogous result for sparse Erdős-Rényi graphs.

The main result (Theorem 1) has been improved significantly and references have been updated

References in corpus (2)

• The hard-core model on random graphs revisited
• Maximum independent sets on random regular graphs

Cited by in corpus (1)

• Factor of iid percolation on trees