Prerequisite omissions and potential defects

29 confirmed findings in the original article.

finding-original-spurious-point-basin · confirmed

Tags: insufficient assumptions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 3, paragraph immediately after Definition 1.1; footnote 2 (PDF p. 3).

converge to said minimum

A specified spurious minimum need not attract an open set, even modulo common rotation. The passage confuses trapping near a nonisolated minimum with attraction to that particular minimum. Its conclusion that spurious minima obstruct global synchrony survives.

The authors explicitly claim convergence to the specified minimum; footnote 2 only removes a common rotation, not the free relative phase in this example.

Correction: Use an aggregate trapping/basin assertion; require isolation of the critical rotation orbit for point-orbit attraction.

Counterexample: Take the two-vertex edgeless graph, common frequency zero, and phases $(0,\pi )$.

The introduction and Definition 1.1 impose no connectedness requirement. Symmetric binary adjacency is zero, so the energy is identically zero and this nonsynchronized state is a local minimum. Every rotating-frame trajectory is constant. Its rotation class has fixed relative phase $\pi$ and empty interior in the relative-phase circle. Its basin is exactly that class, hence contains no open set. The example respects footnote 2, and challenges only attraction to the specified minimum.

finding-original-complete-graph-stationarity · confirmed

Tags: insufficient assumptions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 8, continuation of Remark 1.7 (PDF p. 8).

the only states

Remark 1.7 omits stationarity from its complete-graph PSD assertion. A positive-semidefinite Hessian at a noncritical configuration does not force phase agreement.

The original sentence says states, without the equilibrium qualification used in the preceding general criterion on p. 4.

Correction: Restrict the assertion to equilibrium states.

Counterexample: $K_2$, with phases $0$ and $\pi \mathrm{/}3$.

This is the complete graph with symmetric binary adjacency. The printed assertion assumes only PSD of the energy Hessian. The Hessian is $\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$, with eigenvalues $0,1$, while the two phases differ. The state is not stationary, showing exactly why that missing hypothesis matters.

finding-original-zero-degree-theorem-boundary · confirmed

Tags: insufficient assumptions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF pp. 6–8, Definitions 1.3/1.9, Theorems 1.4/1.10; contrast p. 11 (PDF p. 8).

then G is globally synchronizing

The introductory expander theorems need a positive reference degree or an explicit connectedness restriction. The literal definitions admit zero-degree graphs. Section 2.1 later assumes connectedness, excluding the example there, but that restriction is absent from the introductory statements.

PDF p. 6 specifies an expected-average-degree choice but no positivity; p. 8 states the full numerical criterion without connectedness. The subsequent local convention on p. 11 explains the intended restriction, not a positive-degree counterexample.

Correction: State $d>0$ in Theorem 1.4 and $d^{\ast }>0$ in Theorem 1.10.

Counterexample: Use the edgeless graph on two vertices. For Theorem 1.4 set $d=0$, $\alpha =0.0816$; for Theorem 1.10 set $d^{\ast }=0$, $\alpha ={10}^{-4}$, $c^{-}=c^{+}=0$.

The graph is binary, symmetric and 0-regular, consistent with an expected average degree of zero. All centered matrices vanish, satisfying both expander definitions. For Theorem 1.10, $c^{-}>-1$, $0<\alpha \le 1\mathrm{/}5$ and the scalar left side is $0.0032\log (5000.5)<0.0288<1$, since the exponential series gives $e^9>5000.5$. Every rotating-frame trajectory is constant. Only the initially synchronized diagonal converges to synchrony; that diagonal has two-dimensional phase volume zero. Thus both literal conclusions fail. This does not challenge their positive-degree versions or Section 2.1 lemmas.

finding-original-loop-edge-equality · confirmed

Tags: missing proof steps

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 13, last paragraph of Lemma 2.1 proof; p. 18 loop convention (PDF p. 13).

If the number of edges

The edge-cardinality hypothesis does not give the ordered adjacency equality when loops are allowed. The proof substitutes $⟨\mathbf{1},A\mathbf{1}⟩=d^{\ast }n$ from $\mathrm{\mid }E\mathrm{\mid }=d^{\ast }n\mathrm{/}2$. With $\mathrm{\ell }$ loops the actual sum is $2\mathrm{\mid }E\mathrm{\mid }-\mathrm{\ell }$. The regular-graph estimate remains justified by row sums.

The authors explicitly make the edge-count-to-ordered-sum substitution; p. 18 counts loops once. Neither their regular theorem nor the refined inequality itself is refuted here.

Correction: Use the ordered-sum hypothesis, or supply a separate proof for the stronger looped edge-count extension.

Counterexample: Take the three-vertex path $1$–$2$–$3$, with loops at $1$ and $2$, $d^{\ast }=8\mathrm{/}3$, $\alpha =3\mathrm{/}5$, and synchronized phases.

The graph is connected, binary, symmetric and nonregular, so it avoids the special regular-graph reference convention. Its adjacency is $A=\left(\begin{array}{ccc}1& 1& 0\\ 1& 1& 1\\ 0& 1& 0\end{array}\right)$. It has four unordered edges, hence $\mathrm{\mid }E\mathrm{\mid }=4=d^{\ast }n\mathrm{/}2$, but six ordered adjacency entries. Its centered adjacency is $A-(8\mathrm{/}9)J_3$; its squared Frobenius norm is $6\mathrm{/}81+3(64\mathrm{/}81)=22\mathrm{/}9$, so its operator norm is at most $\sqrt{22}\mathrm{/}3<8\mathrm{/}5=\alpha d^{\ast }$. This reference degree is allowed by Definition 1.3. Synchronized phases are a stable global minimum, with real nonnegative order parameters and valid representatives. Nevertheless $⟨\mathbf{1},A\mathbf{1}⟩=6\mathrm{\ne }8=d^{\ast }n$. This refutes only the equality, not the stronger refined inequality, which remains true at these phases.

finding-original-real-part-sign · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 14, absolute-real-part display in Lemma 2.3 proof (PDF p. 14).

which implies that

The far-half-circle real-part lower bound is missing a minus sign or absolute value. On that indicator support, $\cos {\theta }_y\le 0$. The printed nonpositive lower bound alone cannot justify the next squared estimate; the preceding real-part inequality gives the intended nonnegative bound.

The rendered display prints the positive cosine, while the preceding displayed inequality and following square identify the required correction.

Correction: Use $-d^{\ast }{\rho }_1\cos {\theta }_y$ on the indicated support, equivalently $d^{\ast }{\rho }_1\mathrm{\mid }\cos {\theta }_y\mathrm{\mid }$.

finding-original-discriminant-endpoint · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 16, discriminant paragraph in Lemma 2.5 proof (PDF p. 16).

In particular

The discriminant is zero at the allowed endpoint $\alpha =0$. The strict-negativity sentence includes zero, where the displayed polynomial has a factor ${\alpha }^4$. This does not refute the order-parameter conclusions.

The original displayed discriminant and the strict inequality in the next sentence conflict at zero.

Correction: Handle $\alpha =0$ directly and restrict strict negativity to positive $\alpha$.

Counterexample: $A=J_2$, $d^{\ast }=2$, $\alpha =0$, synchronized phases.

This connected binary looped regular graph has centered adjacency zero and stable normalized phases. Thus zero is an admissible expansion value. The printed discriminant is exactly zero, not negative.

finding-original-regular-cubic-sign · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 16, Remark 2.7 (PDF p. 16).

the relevant cubic being now

The regular-bootstrap cubic has the wrong constant-term sign. Multiplying $2x+3\alpha -1-(1-2{\alpha }^2\mathrm{/}x{)}^2$ by $x^2$ gives constant term $-4{\alpha }^4$.

The authors instruct substitution of (2.9) for (2.8); direct expansion of precisely that expression gives the negative sign. No failure of the remark’s final bounds is asserted.

Correction: Replace $+4{\alpha }^4$ by $-4{\alpha }^4$; check root estimates separately.

finding-original-connectivity-quantifier · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 19, after Proposition 3.2; p. 20, Remark 3.5 (PDF p. 19).

equivalent to the graph being connected

Connectivity does not force every admissible prescribed $c^{-}$ to exceed $-1$. For positive reference degree, $c^{-}>-1$ implies connectivity. The reverse direction requires choosing a sufficiently sharp lower parameter.

The authors state an equivalence but their supplied eigenvalue argument establishes only the sufficient direction for the prescribed parameter.

Correction: Say that a connected graph admits such a lower bound, rather than quantifying over arbitrary admissible bounds.

Counterexample: $K_2$ with $d^{\ast }=1$, $\alpha =1$, $c^{-}=-1$, $c^{+}=1$.

The graph is connected and 1-regular. The centered adjacency has eigenvalues $0,-1$, so its norm is $1=\alpha d^{\ast }$. Its centered Laplacian has eigenvalues $0,1$, lying in $[-1,1]$. Thus the entire Definition 1.9 predicate holds with the prescribed $c^{-}=-1$, violating the asserted reverse implication.

finding-original-tail-sine-proof · confirmed

Tags: missing proof steps; typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 23, proof of Lemma 4.1 (PDF p. 23).

non-negative non-increasing function

The tail sine-square comparison in the proof is invalid. Squared sine decreases beyond $\pi \mathrm{/}2$, so a phase tail need not have sine-square at least its cardinality times the boundary value. The stated lemma follows directly from $H$ instead.

The original display explicitly inserts the tail sine-square sum; the earlier definition of $H$ supplies a direct valid replacement.

Correction: Use $H({\theta }_x)\ge H({\beta }_M)\ge {\sin }^2{\beta }_M$ on the tail; replace “non-increasing” by nondecreasing in absolute angle.

Counterexample: The six-cycle with successive phases $0,\pi \mathrm{/}3,2\pi \mathrm{/}3,\pi ,-2\pi \mathrm{/}3,-\pi \mathrm{/}3$; take $M=0$, ${\beta }_0=\pi \mathrm{/}2$.

The graph is connected, binary and symmetric. Near this winding state the six consistently lifted edge differences remain near $\pi \mathrm{/}3$ with sum $2\pi$. Strict convexity of $1-\cos t$ there and Jensen give a local energy minimum, hence stability. Its first order parameter is zero, satisfying the normalization. The tail has three vertices and sine-square sum $3\mathrm{/}2<3{\sin }^2(\pi \mathrm{/}2)=3$. The total-$H$ conclusion remains true.

finding-original-large-set-degree-factor · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 25, last display in Lemma 4.3 proof; compare p. 26 (PDF p. 25).

so by Lemma 3.6

The incident-edge estimate omits a factor $d^{\ast }$. Lemma 3.6 gives $(1+c^{+}+\alpha )d^{\ast }\mathrm{\mid }{\mathcal{C}}_{\pi \mathrm{/}2}\mathrm{\mid }$. The next page uses that factor in the contradiction.

The rendered p. 25 display lacks the reference degree, whereas the cited lemma and p. 26 restore it. This is a local transcription correction, not a counterexample to Lemma 4.3.

Correction: Insert $d^{\ast }$ in the p. 25 display.

finding-original-numerical-angle-direction · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 30, sentence before geometric-tail display (PDF p. 30).

will never produce an angle

The prose reverses the intended lower-angle invariant. It says the sequence never produces ${\beta }_M\ge 0.131$, immediately before proving that lower bound.

The sentence and immediately following rendered display have opposite logical directions; the subsequent cap argument needs the display’s lower bound.

Correction: Replace the prose comparison by ${\beta }_M<0.131$.

finding-original-numerical-rounding-justification · confirmed

Tags: missing proof steps

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 29, (5.1); p. 30, explanation of $3.326\mathrm{/}{c}_i$ (PDF p. 29).

contradiction if

Two rounded scalar deductions need stronger justification. At $\alpha =0.0816$, $5{\alpha }^2\mathrm{/}4=0.0083232>0.00832$. Also $1.05\cdot 3.168=3.3264>3.326$. The cited estimates alone do not give the printed rounded constants.

The exact coefficient comes from Remark 2.7; p. 30 cites the loose $1.05x$ bound for the smaller printed coefficient. This identifies scalar proof gaps, not a graph counterexample or failure of the numerical threshold.

Correction: Carry $0.0083232$ exactly and prove the sharper arcsine bound directly; both cap comparisons retain slack.

finding-original-ramanujan-cutoff-translation · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 29, paragraph after Table 1 (PDF p. 29).

which translates to

The stated $d=85730$ translation does not follow from $\alpha \le 0.0068$ alone. At that degree, $4(d-1)\mathrm{/}{d}^2>{0.0068}^2$. The degree conclusion can instead be checked directly in the regular specialization of (1.3).

The rendered source explicitly links the decimal threshold to this degree. The mismatch is in the arithmetic translation, not a demonstrated failure of synchrony.

Correction: Use the direct criterion, or the integer cutoff $d\ge 86505$ implied by $0.0068$.

finding-original-symmetric-even-moments · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 31, paragraph before (6.1) (PDF p. 31).

then all even moments would vanish

The symmetry sentence should refer to odd moments. A symmetric centered distribution generally has nonzero even moments.

This exact word appears in the original paragraph, independently of any draft transcription; the later symmetrization paragraph correctly mentions odd moments.

Correction: Replace “even” by “odd” for existing moments.

Counterexample: Let $B,B^{\mathrm{\prime }}$ be independent Bernoulli$(1\mathrm{/}2)$ variables and $W=B-B^{\mathrm{\prime }}$.

The law is symmetric: probabilities at $-1,0,1$ are $1\mathrm{/}4,1\mathrm{/}2,1\mathrm{/}4$. It is bounded and centered, so all moments exist. Yet $\mathbb{E}{W}^2=1\mathrm{/}2$, contradicting the printed even-moment conclusion.

finding-original-sparse-constant-two-edge · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 31, (6.1) and inferred $\alpha$; p. 32, Corollary 6.1 (PDF p. 31).

best result is due to

The constant-two adjacency bound fails in part of the stated near-connectivity regime. Independent critical sparse-graph eigenvalue estimates yield an outlier gap at $p=3\log n\mathrm{/}(2n)$, contradicting the article’s constant-two tolerance in that regime.

The original p. 31 estimate is immediately used in the $\gamma \log n\mathrm{/}n$ regime, and Corollary 6.1 imposes the same constant-two adjacency tolerance. The independent theorem applies to exactly the original loop-free graph law.

Correction: Use a sparse-law estimate with an appropriate constant; separate that repair from the synchronization conclusion.

Counterexample: Let $d_n=(3\mathrm{/}2)\log n$, $p_n=d_n\mathrm{/}n$, $g=9\mathrm{/}(2\sqrt{5})-2>0$.

These are the original loop-free independent-edge graphs, with fixed $\gamma =3\mathrm{/}2>1$ and $0<p_n<1$ eventually. In Alt–Ducatez–Knowles, Corollary 2.4(i), take $\kappa =\theta =1\mathrm{/}10$, so $a=2\mathrm{/}5$ and $(\log n{)}^{5\mathrm{/}6}\le d_n\le n\mathrm{/}2$ eventually. The deterministic degree root ${\beta }_1$ solves $d_{n}I({\beta }_1)+\frac{1}{2}\log (2\pi {\beta }_1{d}_n)=\log n$. Since $I(9\mathrm{/}4)<5\mathrm{/}8$, its left side is increasing for $\beta \ge 1$ and at $9\mathrm{/}4$ is at most $(15\mathrm{/}16+o(1))\log n$, hence ${\beta }_1>9\mathrm{/}4$ and index 1 is admissible, including $1\le n\mathrm{/}(C\sqrt{d_n})$ eventually for the fixed source constant. Here $I(t)=t\log t-t+1$ and $I(9\mathrm{/}4)<5\mathrm{/}8$ follows from $\log (9\mathrm{/}4)<5\mathrm{/}6$, since the exponential series gives $e^{5\mathrm{/}6}>9\mathrm{/}4$. The source theorem gives $-{\lambda }_{\min }(A)\ge (2+g-o(1))\sqrt{d_n}$ with probability tending to one. Subtracting PSD $p_{n}J$ cannot increase the least eigenvalue, so $\mathrm{\parallel }A-p_{n}J\mathrm{\parallel }\ge (2+g\mathrm{/}2)\sqrt{d_n}$ eventually with high probability. This contradicts (6.1). It also contradicts Corollary 6.1 at its fixed $\epsilon ={10}^{-3}<g\mathrm{/}2$, since $p_n\ge (1+\epsilon )\log n\mathrm{/}n$. The synchronization conclusion is not tested by this example.

finding-original-symmetrization-centering · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 33, first display in Proposition 6.3 proof (PDF p. 33).

From Jensen’s inequality

The independent-copy display centers at the wrong mean. For the loop-free model, $\mathbb{E}(A-pJ)=-pI$, so its first equality and resulting comparison need a diagonal correction.

Section 6 uses the loop-free model; p. 6 sets $d^{\ast }=pn$. The equality in the authors’ display consequently subtracts a nonzero mean.

Correction: Apply Jensen at $\mathbb{E}A=p(J-I)$; for the stated centering add $p$.

Counterexample: For every $n\ge 2$, set $p=1-1\mathrm{/}[4n(n-1)]$.

The original proposition permits every $0<p<1$, including this sequence above every cutoff. Every diagonal entry of $A-pJ$ equals $-p$, giving $\mathbb{E}\mathrm{\parallel }A-pJ\mathrm{\parallel }\ge p$. For $W=A-A^{\mathrm{\prime }}$, the sum of absolute entries bounds its norm and has expectation $2n(n-1)p(1-p)=p\mathrm{/}2$. Thus the printed comparison $\mathbb{E}\mathrm{\parallel }A-pJ\mathrm{\parallel }\le \mathbb{E}\mathrm{\parallel }W\mathrm{\parallel }$ is false.

finding-original-zeroth-even-moment · confirmed

Tags: typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 33, even-moment formula in Proposition 6.3 proof (PDF p. 33).

can be easily computed

The even-moment formula includes an invalid zeroth moment. The formula $\mathbb{E}{W}_{xy}^{2\mathrm{\ell }}=2p(1-p)$ is printed for $\mathrm{\ell }\ge 0$ rather than $\mathrm{\ell }\ge 1$.

The rendered original formula explicitly includes $\mathrm{\ell }=0$; this is an endpoint correction, not a defect in the positive-moment calculation.

Correction: Separate the zeroth moment, equal to one.

Counterexample: $p=1\mathrm{/}2$, $x\mathrm{\ne }y$, $\mathrm{\ell }=0$, any sufficiently large $n$.

Independent Bernoulli copies satisfy every graph-law hypothesis. The zeroth power is the constant one, of expectation 1; the displayed right side is $1\mathrm{/}2$. Positive even moments are correctly computed.

finding-original-even-walk-comparison · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 34, first trace-moment display (PDF p. 34).

the set of even cycles

The even-walk comparison has its inequality reversed. With $q=2p(1-p)<1$, a walk using at most $\mathrm{\ell }$ distinct edges contributes $q^m\ge q^{\mathrm{\ell }}$, not at most $q^{\mathrm{\ell }}$.

The rendered original display explicitly replaces the distinct-edge exponent by $\mathrm{\ell }$ with an upper inequality; this is not an extraction error.

Correction: Use an applicable sparse-moment theorem or a different valid comparison.

Counterexample: Take $p=1\mathrm{/}2$ and $\mathrm{\ell }=2$ for any $n\ge 2$, arbitrarily large.

Here $q=1\mathrm{/}2$. Every alternating length-four closed walk over one edge has expectation $q$, whereas the proposed upper bound assigns $q^2$. Every nonzero even length-four walk has one or two distinct edges, so all actual terms are at least the proposed terms and the one-edge terms are strictly larger. Hence $\mathbb{E}\mathrm{Tr}{W}^4>q^2\mathrm{\mid }{\mathcal{C}}_4\mathrm{\mid }$. The independent-copy graph law and integer-moment hypotheses all hold.

finding-original-uniform-expected-norm · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF pp. 33–34, Proposition 6.3 and Remark 6.4 (PDF p. 33).

every p

Proposition 6.3 is false with its uniform all-$p$ quantifier. Both the diagonal term near $p=1$ and sparse degree spikes violate the bound. Remark 6.4’s proposed cutoffs inherit this failure; its scalar evaluations do not repair it.

The original proposition explicitly quantifies over every $p\in (0,1)$ after choosing a cutoff depending only on $C$. The two counterexamples address that exact order of quantifiers.

Correction: State and prove a density-dependent estimate including the diagonal contribution and sparse-degree effect.

Counterexample: Fix any $C>2\sqrt{2}$ and set $p=1-1\mathrm{/}(16C^{2}n)$ for arbitrarily large $n\ge 2$.

All original quantifiers are met. Every outcome has $\mathrm{\parallel }A-pJ\mathrm{\parallel }\ge p>1\mathrm{/}2$ from its diagonal, while $C\sqrt{np(1-p)}=\sqrt{p}\mathrm{/}4<1\mathrm{/}4$. Thus no $n_0(C)$ works.

Counterexample: Use the explicit sparse family $p_k=1\mathrm{/}{n}_k$ and $k>(1+5C\mathrm{/}4{)}^2$.

For integer $k\ge 1$, set $n_k=4^{k+2}k!$, $p_k=1\mathrm{/}{n}_k$, split vertices into equal halves, and count cross-degrees $D_u$ from the first half. These are independent Bin$(n_k\mathrm{/}2,1\mathrm{/}{n}_k)$ variables because they use disjoint edge coordinates. For $n_k\ge 4k$, $\mathbb{P}(D_u=k)\ge 1\mathrm{/}(24^{k}k!)$: each falling-factorial factor is at least $n_k\mathrm{/}4$, and $(1-1\mathrm{/}{n}_k{)}^{n_k\mathrm{/}2-k}\ge 1\mathrm{/}2$. Therefore the number of independent trials times this lower bound is 4, and $\mathbb{P}(\max D_u\ge k)\ge 4\mathrm{/}5$, using $(1-q{)}^m\le (1+mq{)}^{-1}$. A degree-$k$ column gives $\mathrm{\parallel }A\mathrm{\parallel }\ge \sqrt{k}$, and $\mathrm{\parallel }J\mathrm{/}{n}_k\mathrm{\parallel }=1$, hence $\mathrm{\parallel }A-J\mathrm{/}{n}_k\mathrm{\parallel }\ge \sqrt{k}-1$ on that event. These are exactly the original loop-free graphs, all $p_k\in (0,1)$, and $n_k\to \mathrm{\infty }$. Nonnegativity yields $\mathbb{E}\mathrm{\parallel }A-p_{k}J\mathrm{\parallel }\ge (4\mathrm{/}5)(\sqrt{k}-1)>C$, whereas $C\sqrt{n_k{p}_k(1-p_k)}<C$.

finding-original-edge-coordinate-lipschitz · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 35, proof of Corollary 6.6 (PDF p. 35).

convex and 1-Lipschitz

The edge-coordinate norm map is not 1-Lipschitz in the Euclidean metric. Its sharp cube constant is $\sqrt{2(n-1)\mathrm{/}n}>1$ for $n\ge 3$. Convexity is unaffected.

The authors apply Euclidean product concentration to the independent upper-triangular coordinates and explicitly claim the unit constant there.

Correction: Use an admissible Lipschitz constant and rederive any concentration application.

Counterexample: Take $n=1000$, $p=1\mathrm{/}4$, $x_{ij}=p$, $y_{ij}=p-s$ for all $i<j$, with $s=1\mathrm{/}8$.

Both vectors belong to the exact independent-coordinate cube. Zero-diagonal symmetric assembly gives $T(x)-pJ=-pI$, while $T(y)-pJ=-(p-s)I-sJ$. Thus $f(x)=p$, $f(y)=p+(n-1)s$ and $\mathrm{\parallel }x-y{\mathrm{\parallel }}_2=s\sqrt{n(n-1)\mathrm{/}2}$. Their quotient is $\sqrt{2(n-1)\mathrm{/}n}>1$, disproving the printed Lipschitz assertion. The corollary’s $n,p$ assumptions hold; Theorem 6.5 requires the function property on the entire cube.

finding-original-uniform-median-bound · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 35, median bound in proof of Corollary 6.6 (PDF p. 35).

Together with Proposition 6.3

The all-$p$ median bound used in the proof is false. Sparse degree spikes force every median above the printed upper bound.

The rendered p. 35 proof explicitly claims this median bound for $n\ge 1000$, with no density qualification.

Correction: Replace the invalid expected-norm input and reprove a density-qualified median estimate.

Counterexample: Set $k=100$, $n=4^{102}100!$, $p=1\mathrm{/}n$.

For integer $k\ge 1$, set $n_k=4^{k+2}k!$, $p_k=1\mathrm{/}{n}_k$, split vertices into equal halves, and count cross-degrees $D_u$ from the first half. These are independent Bin$(n_k\mathrm{/}2,1\mathrm{/}{n}_k)$ variables because they use disjoint edge coordinates. For $n_k\ge 4k$, $\mathbb{P}(D_u=k)\ge 1\mathrm{/}(24^{k}k!)$: each falling-factorial factor is at least $n_k\mathrm{/}4$, and $(1-1\mathrm{/}{n}_k{)}^{n_k\mathrm{/}2-k}\ge 1\mathrm{/}2$. Therefore the number of independent trials times this lower bound is 4, and $\mathbb{P}(\max D_u\ge k)\ge 4\mathrm{/}5$, using $(1-q{)}^m\le (1+mq{)}^{-1}$. A degree-$k$ column gives $\mathrm{\parallel }A\mathrm{\parallel }\ge \sqrt{k}$, and $\mathrm{\parallel }J\mathrm{/}{n}_k\mathrm{\parallel }=1$, hence $\mathrm{\parallel }A-J\mathrm{/}{n}_k\mathrm{\parallel }\ge \sqrt{k}-1$ on that event. These are exactly the original loop-free graphs, all $p_k\in (0,1)$, and $n_k\to \mathrm{\infty }$. Here $n\ge 1000$, and with probability at least $4\mathrm{/}5$, $Z=\mathrm{\parallel }A-pJ\mathrm{\parallel }\ge 9$. For every $m<9$, $\mathbb{P}(Z\le m)\le 1\mathrm{/}5<1\mathrm{/}2$, so every median is at least 9. The claimed bound is $4\sqrt{1-1\mathrm{/}n}+4<8$.

finding-original-corollary-six-five-tail · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 35, Corollary 6.6, (6.5) (PDF p. 35).

the adjacency matrix A of G(n, p)

The all-$p$ tail estimate (6.5) fails. The sparse family supplies a fixed positive lower tail probability exceeding the asserted exponential upper bound.

Equation (6.5) is asserted for every $p\in (0,1)$; the example tests its exact centering, threshold and tail probability.

Correction: Replace (6.5) with an independently proved, density-qualified statement.

Counterexample: $k=144$, $n=4^{146}144!$, $p=1\mathrm{/}n$, $t=3$.

For integer $k\ge 1$, set $n_k=4^{k+2}k!$, $p_k=1\mathrm{/}{n}_k$, split vertices into equal halves, and count cross-degrees $D_u$ from the first half. These are independent Bin$(n_k\mathrm{/}2,1\mathrm{/}{n}_k)$ variables because they use disjoint edge coordinates. For $n_k\ge 4k$, $\mathbb{P}(D_u=k)\ge 1\mathrm{/}(24^{k}k!)$: each falling-factorial factor is at least $n_k\mathrm{/}4$, and $(1-1\mathrm{/}{n}_k{)}^{n_k\mathrm{/}2-k}\ge 1\mathrm{/}2$. Therefore the number of independent trials times this lower bound is 4, and $\mathbb{P}(\max D_u\ge k)\ge 4\mathrm{/}5$, using $(1-q{)}^m\le (1+mq{)}^{-1}$. A degree-$k$ column gives $\mathrm{\parallel }A\mathrm{\parallel }\ge \sqrt{k}$, and $\mathrm{\parallel }J\mathrm{/}{n}_k\mathrm{\parallel }=1$, hence $\mathrm{\parallel }A-J\mathrm{/}{n}_k\mathrm{\parallel }\ge \sqrt{k}-1$ on that event. These are exactly the original loop-free graphs, all $p_k\in (0,1)$, and $n_k\to \mathrm{\infty }$. All original hypotheses hold, including $n\ge 1000$ and $t>0$. With probability at least $4\mathrm{/}5$, the norm is at least 11. The threshold $4\sqrt{1-1\mathrm{/}n}+7$ is strictly below 11, so the left side is at least $4\mathrm{/}5$. The asserted right side is $2e^{-9\mathrm{/}4}\le 8\mathrm{/}13<4\mathrm{/}5$.

finding-original-corollary-six-six-small-gamma · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 35, Corollary 6.6, (6.6) (PDF p. 35).

Moreover, for every

The logarithmic-density estimate is false for unrestricted $\gamma >0$. A single fixed sufficiently small $\gamma$ violates it above every proposed size cutoff. This does not test the separate $\gamma >1$ application.

The original statement uses every positive $\gamma$, not only the supercritical range subsequently needed. The graph law and norm convention agree exactly.

Correction: Restrict the parameter range only with an independent proof.

Counterexample: Fix $\gamma ={10}^{-6}$; let $n$ range through even integers with $L=\log n\ge \mathrm{2,000,000}$, $p=\gamma L\mathrm{/}n$, $k=\lceil L\mathrm{/}1000\rceil$.

These satisfy $0<p<1\mathrm{/}2$, $n\ge 1000$ and the exact fixed-$\gamma$ law. For $M=n\mathrm{/}2$ independent cross-degrees, $q=\mathbb{P}(\mathrm{B}\mathrm{i}\mathrm{n}(M,p)=k)\ge (Mp\mathrm{/}k{)}^k{e}^{-2Mp}\ge e^{-L\mathrm{/}50}$, since $L\mathrm{/}1000\le k\le L\mathrm{/}500\le M$, $Mp\mathrm{/}k\ge 1\mathrm{/}4000$ and $\log 4000<9$. Thus some cross-degree equals $k$ with probability at least $1\mathrm{/}(1+2e^{-49L\mathrm{/}50})>1\mathrm{/}2$. Its centered column has squared norm $D(1-p{)}^2+(n-D)p^2$, so the norm is at least $(1\mathrm{/}2)\sqrt{L\mathrm{/}1000}>8\sqrt{\gamma L}$. The asserted upper probability is $2e^{-\gamma L}\le 2e^{-2}<2\mathrm{/}5$. Letting even $n$ increase defeats any $n_0(\gamma )$.

finding-original-shifted-expander-probability · confirmed

Tags: over strong conclusions

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF pp. 36–38, Proposition 6.9, (6.7)–(6.9) and final failure estimate (PDF p. 36).

Then the probability

Proposition 6.9’s shifted-root expander event need not have high probability. Its degree-tail thresholds point away from (6.9). At a permitted fixed parameter pair the entire expander event instead has probability tending to zero.

The original p. 36 equations shift inward by $\epsilon$; the original p. 37 degree target requires the opposite slack. The counterexample tests the whole p. 8 expander predicate, not merely the sufficient degree criterion.

Correction: Rechoose slack roots and prove their degree and spectral estimates independently.

Counterexample: Fix $\gamma =2$, $\epsilon =1\mathrm{/}2$, $L=\log n$, $p=2L\mathrm{/}n$, $\mu =2L$, $\alpha =8\mathrm{/}\sqrt{\mu }$, with exactly the printed shifted roots.

The parameter condition is $3\mathrm{/}2<2<5$; $0<p<1$ eventually. The lower root obeys $1+c^{-}-1\mathrm{/}2>0$, hence $c^{-}>-1\mathrm{/}2$. Testing ${\mathrm{\Delta }}_L⪰c^{-}\mu I$ on a coordinate vector forces $d(v)\ge (1+c^{-})\mu -p>L$ eventually. The sufficient degree target (6.9) also forces this. Put $k=\lfloor L\rfloor$, $a=\mathbb{P}(\mathrm{B}\mathrm{i}\mathrm{n}(n-2,p)\le k)$; the exact binomial atom and $k!\le ek(k\mathrm{/}e{)}^k$ give $a\ge e^{-4}{n}^{-1\mathrm{/}2}\mathrm{/}L$ eventually. If $X$ counts vertices of full degree at most $k$ and $b=\mathbb{P}(\mathrm{B}\mathrm{i}\mathrm{n}(n-2,p)\le k-1)$, then $r=\mathbb{P}(d(v)\le k)=(1-p)a+pb\ge (1-p)a$. Shared-edge conditioning gives joint probability $(1-p)a^2+p{b}^2\le a^2$. Consequently $\mathbb{P}(X=0)\le 1\mathrm{/}(nr)+2p\mathrm{/}(1-p{)}^2\le 2e^{4}L\mathrm{/}\sqrt{n}+2p\mathrm{/}(1-p{)}^2\to 0$. The full expander probability is at most this quantity; the claimed lower bound tends to one. Its failure probability, and that of (6.9), therefore tend to one.

finding-original-upper-degree-prefactor · confirmed

Tags: over strong conclusions; typos

https://static1.squarespace.com/static/5436e695e4b07f1e91b30155/t/6991d638ab1b273169a7becd/1771165240824/expander-graphs-are-globally-synchronizing.pdf; PDF p. 38, upper-degree probability display in Proposition 6.9 proof (PDF p. 38).

We do the same for the maximum degree

The printed upper-tail prefactor can be negative. The threshold uses $c^{+}+\epsilon$, while the display substitutes $c^{+}-\epsilon$.

The original rendered p. 38 formula has minus signs in this prefactor although $k^{+}$ was defined with plus signs on p. 37.

Correction: Use $(1+c^{+}+\epsilon )\mathrm{/}(c^{+}+\epsilon )$. This does not fix the separate degree-target implication.

Counterexample: Take $\epsilon =4\mathrm{/}5$, $\gamma =11\mathrm{/}5$ and the original positive shifted root.

The hypotheses hold: $1.8<2.2<2.5625$. For $h(x)=(1+x)\log (1+x)-x$, direct logarithm estimates give $h(4\mathrm{/}5)<9\mathrm{/}11<h(8\mathrm{/}5)$. Strict increase on positive $x$ and $h(c^{+}+4\mathrm{/}5)=9\mathrm{/}11$ imply $0<c^{+}<4\mathrm{/}5$. Thus the printed prefactor $(1+c^{+}-\epsilon )\mathrm{/}(c^{+}-\epsilon )$ is negative. For all sufficiently large $n$, $0<k^{+}<n-1$ and $0<p<1$, so the degree-tail probability is strictly positive, while the printed right side is negative. The other branch also exists with $c^{-}<0$: $h(-4\mathrm{/}5)<9\mathrm{/}11<1=h(-1^{+})$ gives its shifted argument in $(-1,-4\mathrm{/}5)$ and hence $c^{-}\in (-1\mathrm{/}5,0)$.