Valid restricted spectral tails and a counterexample to the shifted degree-failure conclusion

PDF p. 37: Proof of Proposition 6.9; equation (6.9) and final displays; PDF p. 38: Proof of Proposition 6.9; equation (6.9) and final displays

Fix $0<\epsilon <1$ and $1+\epsilon <\gamma <1+{\epsilon }^{-2}$, and let $c^{-}<0<c^{+}$ be the article's shifted roots. For each sufficiently large integer $n$, put $p=\gamma \log n\mathrm{/}n$ and sample the loop-free simple graph $G\sim G(n,p)$ on $[n]=\{1,\dots ,n\}$: distinct possible edges occur mutually independently, each with probability $p$. All probabilities and expectations below use this finite graph law. Write $A$ for the adjacency matrix of $G$, $J$ for the $n\times n$ all-ones matrix, $d(v)={\sum }_{w\in [n]}{A}_{vw}$ for the degree of $v$, $d_{\min }={\min }_{v\in [n]}d(v)$ and $d_{\max }={\max }_{v\in [n]}d(v)$. For every integer $k$, let $X_k$, $X_{\le k}$ and $X_{\ge k}$ count vertices of degree exactly $k$, at most $k$ and at least $k$, respectively. For a matrix $M$ on ${\mathbb{C}}^{[n]}$, use the operator norm $\mathrm{\parallel }M\mathrm{\parallel }={\max }_{\mathrm{\parallel }f{\mathrm{\parallel }}_2=1}\mathrm{\parallel }Mf{\mathrm{\parallel }}_2$ induced by the standard Euclidean norm.

Set $\mu =np$, $\alpha =8\mathrm{/}\sqrt{\mu }$, and rounded thresholds $k^{-}=\lfloor (1+c^{-}-\epsilon )\mu \rfloor$, $k^{+}=\lceil (1+c^{+}+\epsilon )\mu \rceil$. Set $a=\epsilon -c^{-}$ and $b=c^{+}+\epsilon$, and $R_{\pm }=\exp (-\epsilon \log n+2p{k}^{\pm }+4\log \log n)$. For all sufficiently large $n$, $\mathbb{P}(d_{\min }\le k^{-})\le a^{-2}{R}_{-},\mathbb{P}(d_{\max }\ge k^{+})\le \frac{1+b}{b}{R}_{+},\mathbb{P}(\mathrm{\parallel }A-pJ\mathrm{\parallel }\ge 8\sqrt{\mu })\le 2n^{-\gamma }\mathrm{.}$ These valid estimates do not imply the original degree target (6.9), namely $(1+c^{-}+\alpha )\mu \le d_{\min }\le d_{\max }\le (1+c^{+}-\alpha )\mu$.

The article's original final claim that the failure probability of (6.9) is at most $C(\gamma ,\epsilon )(\log n{)}^4{n}^{-\epsilon }$ is false. At the fixed admissible pair $(\gamma ,\epsilon )=(2,1\mathrm{/}2)$, its failure probability tends to one; the probability that $G$ is an $(n,d^{\ast },\alpha ,c^{-},c^{+})$-expander with $d^{\ast }=\mu$ tends to zero. The original source displays the tail prefactors $(c^{-}+\epsilon {)}^{-2}$ and $(1+c^{+}-\epsilon )\mathrm{/}(c^{+}-\epsilon )$; these are preserved as attributed formulas, while the proved estimates above use $a$ and $b$.

Counts of vertices of each degree

Adjacency, degrees, graph Laplacian, and spectral notation

The operator norm is zero on the zero domain and otherwise is max_‖ v‖=1‖ Tv‖

Two-sided spectral expander — Definition 1.9

The original article at PDF pp. 36–38 defines the shifted roots (6.7)–(6.8), thresholds and degree target (6.9), then claims the displayed final small failure probability. Definition 1.9 on PDF p. 8 supplies the attributed expander predicate. The initial proof line on p. 37 writes $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }\le \alpha$; the spectral input appropriate to that predicate is $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }\le \alpha d^{\ast }=8\sqrt{\gamma \log n}$, supplied here by the separate restricted spectral lemma. The article under study supplies attribution only; the probability deductions use the local mathematical suppliers in Facts & Assumptions. The counterexample concerns Proposition 6.9's shifted-root parameters and this proof's failure claim; it does not by itself refute the unshifted-root Theorem 6.2, synchronization conclusions, or every individual displayed tail formula.