Polynomial components in spectrally subcritical percolation on near-regular graphs
Let $G$ be a finite graph with spectral radius $\lambda$ and maximum degree $\Delta$, and keep each edge independently with probability $p=(1-\varepsilon)/\lambda$. Christoph, Morawski and Wigderson asked for the typical size of the largest component in this regime, singling out graphs that are close to regular in the sense $\Delta\le(1+\delta)\lambda$. We show that the answer depends on the product $(1-\varepsilon)(1+\delta)$. When it is less than one, a known maximum-degree argument gives components of logarithmic order. When it is greater than one, there are connected graphs with $\Delta\le(1+\delta)\lambda$ whose largest component has at least $n^c$ vertices with high probability, for a constant $c>0$, and the spectral radius can be taken of order $n^a$ for any $0\le a<1$. When it equals one, the largest component has $O((\log n)^3)$ vertices with high probability. We also sharpen the resolvent bound of Christoph, Morawski and Wigderson for graphs with bounded ratio $\Delta/\lambda$. The optimal order in the polynomial regime remains open.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24193274
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint