Answers are grounded in this paper and cite their sources.
Let G be a finite graph with spectral radius λ and maximum degree Δ, and keep each edge independently with probability p=(1-ε)/λ. 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 Δ≤(1+δ)λ. We show that the answer depends on the product (1-ε)(1+δ). 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 Δ≤(1+δ)λ whose largest component has at least nᶜ vertices with high probability, for a constant $c>0$, and the spectral radius can be taken of order nᵃ for any 0≤ a<1. When it equals one, the largest component has O((log n)³) vertices with high probability. We also sharpen the resolvent bound of Christoph, Morawski and Wigderson for graphs with bounded ratio Δ/λ. The optimal order in the polynomial regime remains open.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: