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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Polynomial components in spectrally subcritical percolation on near-regular graphs

Yitzchak Shmalo
1 links
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Polynomial components in spectrally subcritical percolation on near-regular graphs

Yitzchak Shmalo
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon