Prerequisite omissions and potential defects

finding-original-exact-root-expansion-rate · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 33, Theorem 6.2 and (6.3); p. 38 proof (PDF p. 33).

Then G(n, p)

The exact unshifted-root expansion event does not have the claimed polynomial failure rate. Its boundary-degree obstruction has probability of order at least $1\mathrm{/}\sqrt{\log n}$. This differs from Proposition 6.9’s shifted-root failure and does not refute synchronization.

Theorem 6.2 uses the unshifted equation (6.3) exactly; the example independently tests those roots and the full Loewner lower bound. It is not an inference from the shifted-root counterexample.

Correction: Use outward slack in the Laplacian parameters; prove the synchrony probability separately.

Counterexample: Fix $\gamma =2$, $\epsilon =1\mathrm{/}2$, $p=2\log n\mathrm{/}n$, $\mu =2\log n$. Let $a=1+c^{-}\in (0,1)$ solve $2(a\log a-a+1)=1$, and set $k=\lceil a\mu -p\rceil -1$.

The original parameter restrictions hold, and $p\in (0,1)$ eventually. A degree-$k$ vertex violates the necessary diagonal condition $d(v)\ge a\mu -p$ for ${\mathrm{\Delta }}_L⪰c^{-}\mu I$. For $q=\mathbb{P}(\mathrm{B}\mathrm{i}\mathrm{n}(n-1,p)=k)$, Stirling’s two-sided bounds and $k=a\mu +O(1)$ give $q=\mathrm{\Theta }(1\mathrm{/}(n\sqrt{\log n}))$: the exponent is $-\mu I(a)=-\log n$, with bounded rounding error and prefactor $\mathrm{\Theta }({\mu }^{-1\mathrm{/}2})$. For two vertex events, write $r=\mathbb{P}(\mathrm{B}\mathrm{i}\mathrm{n}(n-2,p)=k-1)\mathrm{/}\mathbb{P}(\mathrm{B}\mathrm{i}\mathrm{n}(n-2,p)=k)=k(1-p)\mathrm{/}((n-1-k)p)\to a$. Their joint probability divided by $q^2$ is $1+p(1-p)(r-1{)}^2\mathrm{/}(1-p+pr{)}^2\to 1$. The first two inclusion–exclusion terms yield occurrence probability at least $nq\mathrm{/}2\ge \kappa \mathrm{/}\sqrt{\log n}$ eventually. This exceeds $C(\log n{)}^4{n}^{-1\mathrm{/}2}$ for every fixed $C$.

finding-original-spectral-normalization-typo · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 37, first line of Proposition 6.9 proof (PDF p. 37).

By Corollary 6.6

The cited spectral event is missing its degree scale. Corollary 6.6 supplies $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }\le \alpha d^{\ast }=8\sqrt{\gamma \log n}$ in the applicable range, not $\mathrm{\parallel }{\mathrm{\Delta }}_A\mathrm{\parallel }\le \alpha$.

The original line and Definition 1.9 use different normalizations; the chosen value of $\alpha$ makes the missing factor explicit.

Correction: Insert $d^{\ast }$; this only corrects the normalization.

finding-original-gaussian-variable-parity-typo · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 34, Gaussian-comparison paragraph between the two trace displays (PDF p. 34).

On the other hand, if G is a symmetric matrix

The Gaussian comparison sentence uses the wrong variable and omits the even-power restriction. The printed $\mathbb{E}{W}_{xy}^k\ge 1$ fails for the defined Bernoulli difference. Replacing $W$ by $G$ still requires even $k$.

The PDF image prints W in the Gaussian paragraph. The following trace lower bound is justified using even Gaussian moments on even walks; this correction does not repair the separate reversed Bernoulli comparison.

Correction: Use $\mathbb{E}{G}_{xy}^{2j}=(2j-1)!!\ge 1$ for positive integers $j$; odd Gaussian moments vanish.

Counterexample: Use $p=1\mathrm{/}2$, $x\mathrm{\ne }y$, $k=2$, and any arbitrarily large $n\ge 2$.

These obey Proposition 6.3 and its independent-copy graph law. The defined $W=A-A^{\mathrm{\prime }}$ has probabilities $1\mathrm{/}4,1\mathrm{/}2,1\mathrm{/}4$ at $-1,0,1$, so $\mathbb{E}{W}_{xy}^2=1\mathrm{/}2<1$. For a standard Gaussian the odd moment at $k=1$ is zero by symmetry. Thus both the variable and parity corrections are needed; the even-walk Gaussian trace lower bound remains valid.

finding-original-rounding-logarithm-typo · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 37, final line of the rounding paragraph, immediately before Lemma 6.7 is applied (PDF p. 37).

as |Lk −Lk+η| ⩽|η| log log n + log(k + 1).

The rounding explanation bounds a difference of L-values instead of their logarithms. With $L_k=(\log n{)}^k\mathrm{/}k!$, the preceding exponent contains $\log L_k$. The printed bound for $\mathrm{\mid }{L}_k-L_{k+\eta }\mathrm{\mid }$ is false.

The rendered formula omits both logarithms despite explicitly bounding exponent variation. The logarithmic correction supplies the intended type of estimate, without validating the separate degree-target inference.

Correction: For adjacent integer indices use $\mathrm{\mid }\log L_k-\log L_{k+\eta }\mathrm{\mid }$; handle fractional rounding by a mean-value bound on the smooth exponent.

Counterexample: Take the permitted $\gamma =2$, $\epsilon =1\mathrm{/}2$, its printed lower shifted root, $\delta =2(1+c^{-}-1\mathrm{/}2)$, $k=\lfloor \delta \log n\rfloor$, and the adjacent-index test $\eta =1$.

The parameter restrictions $0<1\mathrm{/}2<1$ and $3\mathrm{/}2<2<5$ hold. The root has $-1\mathrm{/}2<c^{-}<0$, hence $0<\delta <1$ and eventually $1\le k<k+1\le n-1$, $0<p=2\log n\mathrm{/}n<1$. Put $L=\log n$. Exactly $L_{k+1}\mathrm{/}{L}_k=L\mathrm{/}(k+1)\to 1\mathrm{/}\delta >1$. Also $k!\le k^k$ gives $L_k\ge (L\mathrm{/}k{)}^k\ge {\delta }^{-k}\ge \delta n^{\delta \log (1\mathrm{/}\delta )}$. Thus $\mathrm{\mid }{L}_{k+1}-L_k\mathrm{\mid }$ grows at least as a positive power of n, exceeding the printed $O(\log L)$ right side. This tests the printed unit-index inequality, not the probability conclusion. The correct logarithmic identity is $\log L_{k+1}-\log L_k=\log \log n-\log (k+1)$.