{"id":"7ffb1220-73d6-42c5-ba1a-8b01b64e9132","arxiv_id":"2501.12205","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"With high probability, every graph in the random graph process after the connectivity time is globally synchronizing for the homogeneous Kuramoto model.","lead":"The paper proves that in the random graph process, once the graph becomes connected, the homogeneous Kuramoto model on that graph almost surely synchronizes, and every later graph in the process remains synchronizing. It settles a conjecture from the expander-graph synchronization literature, showing that connectivity is the only obstruction.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.11 Case 1 invokes Lemma 2.6 without verifying |Cγ∩W|≤(1+δ)|Cβ∩W|; this ratio can fail under the stated hypotheses, so the amplification step is not justified.","rationale":"I read the paper in good faith and found the overall strategy plausible: the defective-expander framework is a natural way to handle low-degree vertices at the connectivity threshold, and the probabilistic verification in Section 3 appears standard. However, the stress-test pass surfaced a concrete gap in the deterministic core of the argument rather than in the probabilistic estimates. In Lemma 2.11, Case 1, the proof applies Lemma 2.6 to subsets of the core G[W] without checking the ratio hypothesis |Y|≤(1+δ)|X|. I verified by a direct set-size calculation that this hypothesis can fail while all Case 1 assumptions hold, so the application is not justified as written. This matters because Lemma 2.11 is the amplification step that takes the level set from the small-expansion regime to size n/2, where the contradiction with Lemma 2.3 is obtained. The concern is not that the theorem is false, but that the proof has a missing justification in a load-bearing place. I therefore recommend conditional acceptance: the authors should either supply the missing argument for the claimed lower bound in Case 1 or adjust the statement and proof of Lemma 2.11. The reader's weakest-assumption analysis focused on Lemma 3.1; my concern is different and located in Section 2, so I disagree that Lemma 3.1 is the main soft spot. If Lemma 2.11 is repaired, the rest of the proof, including the simultaneous union bound over the random graph process, appears coherent.","tokens_in":11301,"tokens_out":26592,"duration_ms":253535,"concrete_test":"Fix δ=0.1, a=10, b=5 and take X of size 5, Y of size 6 with X⊆Y⊆W, Cβ∩W=X, Cβ∩B of size 5, and Cγ∩B=Cβ∩B while Cγ∩W=Y. This satisfies |Cβ∩B|≤(1/2+δ)|Cβ|, |Cγ|≤(1+δ)|Cβ|, and |Cγ|≤n/2 for large n, yet |Y|>(1+δ)|X|. Then check whether the claimed lower bound e(X,Y^c)≥(ε d/n)|X||Y^c| can be derived from [1, Proposition 3.2] or Lemma 2.6 without the ratio condition; if it cannot, Lemma 2.11 requires modification.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Lemma 2.11, Case 1 assumes |Cβ∩B|≤(1/2+δ)|Cβ| and, toward contradiction, |Cγ|≤(1+δ)|Cβ| and |Cγ|≤n/2. It then claims, by Lemma 2.6, that e(Cβ∩W,Cγ^c∩W) ≥ (ε d/|W|)|Cβ∩W||Cγ^c∩W|. This application requires the hypothesis |Y|≤(1+δ)|X| for X=Cβ∩W and Y=Cγ∩W. That hypothesis does not follow from the stated assumptions. Write a=|Cβ| and b=|Cβ∩B|; then |X|=a−b. If Cγ contains no new B vertices, the largest possible |Y| with |Cγ|≤(1+δ)a is (1+δ)a−b, which exceeds (1+δ)(a−b) whenever b>0. For instance, a=10, b=5, δ=0.1 satisfies the Case 1 bound b≤(1/2+δ)a, and |Y|=6>5.5=(1+δ)|X| while |Cγ|=11≤(1+δ)a. Thus Lemma 2.6 cannot be invoked as written. Since Lemma 2.11 is the only mechanism that amplifies the stable-state level set from size (1+δ)^{k_*}|C_{π/2}| up to n/2, this is a load-bearing gap in the proof of Theorem 1.6 and hence of Theorem 1.2. The theorem may still be true, but the written proof does not establish this step.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a conjecture of Abdalla, Bandeira, Kassabov, Souza, Strogatz, and Townsend by showing that, with high probability, the Erdős–Rényi random graph process is globally synchronizing at every time m at or after the connectivity time tau. The proof introduces a deterministic notion of a 'defective expander' (Theorem 1.6), which allows a small set B of low-degree vertices to violate the usual expander degree conditions while still guaranteeing global synchronization under hypotheses (B1)–(B4). Applying this to the random graph process, with B taken to be the set of vertices of degree at most 11*epsilon*log n just below the connectivity threshold, the authors verify the hypotheses and deduce the stronger form of Conjecture 1.1. The paper is concise and builds on the spectral-expansion framework of [1].","tokens_in":11644,"tokens_out":11339,"duration_ms":99449,"significance":"If the proof is correct, this resolves a notable open conjecture and gives a best-possible result: connectivity is both necessary and, with high probability, sufficient for global synchronization throughout the random graph process. The defective-expander framework is a genuine technical contribution that extends the deterministic methods of [1] to graphs with a small set of low-degree vertices. The paper is clearly organized, with a clean separation between the deterministic theorem (Theorem 1.6) and the probabilistic verification (Section 3). However, the proof relies on several key lemmas imported from [1] without proof, and, more importantly, the current manuscript contains a load-bearing gap in the defective-expander transfer, as detailed below.","major_comments":[{"comment":"The proof of Lemma 2.8 invokes Lemma 2.6 on H = G[W] with X' = X∩W and Y' = Y∩W, but the hypotheses of Lemma 2.6 require |Y'| ≤ (1+δ)|X'| and |Y'| ≤ |W|/2. The paper only verifies the analogous bounds for the full sets X and Y, namely |Y| ≤ (1+δ)|X| and |Y| ≤ n/2. These do not imply the W-restricted versions: if Y contains B-vertices not in X, then |Y∩W| can exceed (1+δ)|X∩W| even when |Y| ≤ (1+δ)|X|. For instance, with |X| = 10, |X∩B| = 5, δ = 0.1, and Y formed by adding one vertex in W to X, one has |Y| = 11 ≤ (1+δ)|X| but |Y∩W| = 6 > 5.5 = (1+δ)|X∩W|. Since Lemma 2.8 feeds directly into Lemma 2.10, the first amplification phase is not justified as written.","section":"Section 2.2, Lemma 2.8"},{"comment":"In Case 1 of Lemma 2.11, the application of Lemma 2.6 with X = Cβ∩W and Y = Cγ∩W suffers the same missing-hypothesis problem. The assumptions |Cγ| ≤ (1+δ)|Cβ| and |Cβ∩B| ≤ (1/2+δ)|Cβ| do not imply |Cγ∩W| ≤ (1+δ)|Cβ∩W|, nor do they imply |Cγ∩W| ≤ |W|/2 (since |Cγ| ≤ n/2 does not control |Cγ∩W| relative to |W|/2 when B is nonempty). Thus the lower bound e(Cβ∩W, (Cγ)^c∩W) ≥ (εd/n)|Cβ∩W||(Cγ)^c∩W| is not established. Because Lemma 2.11 is the only mechanism in the proof of Theorem 1.6 that grows the stable-state level set from size αn up to n/2, this is a load-bearing gap. The theorem may still be true, but the written proof does not establish this step.","section":"Section 2.3, Lemma 2.11"}],"minor_comments":[{"comment":"The title contains a typo: 'GLOBALL Y' should be 'GLOBALLY'.","section":"Title"},{"comment":"The definition repeats 'is an': 'A graph G = (V,E) is an is an (n,d,α,c−,c+)-expander' should be corrected.","section":"Definition 1.4"},{"comment":"The proof sketch contains garbled symbols such as '/BD' and 'BD_{|x|≥π/2}'; the intended indicator notation should be cleaned up for readability.","section":"Lemma 2.9"},{"comment":"In the paragraph after Proposition 3.2, the line 'Let d = pn, α = 20 log n' should read α = 20(log n)^{-1/2}, matching the definition in Proposition 3.2.","section":"Proof of Theorem 1.2"},{"comment":"The displayed expectation formula is missing a closing bracket and the final inequality is not a well-formed probability statement; it should be rewritten as a product of two probabilities, consistent with the preceding estimate.","section":"Lemma 3.1(4)"}],"recommendation":"major_revision","confidential_remarks":"The gap identified in the major comments is genuine and affects the core defective-expander transfer in Lemmas 2.8 and 2.11. It was independently flagged in a stress-test review. I believe it is fixable within the scope of the manuscript, for instance by strengthening the hypotheses of those lemmas to include W-restricted ratio and size bounds, or by proving those bounds using (B4). The rest of the argument appears sound and the result is significant, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Both of us know the background, so I'll be direct. The paper confirms the strong form of the Abdalla et al. conjecture: with high probability, every graph in the random graph process after the connectivity time is globally synchronizing. The new deterministic object, Theorem 1.6, is a real extension of the expander framework in [1], and the probabilistic verification in Section 3 is mostly standard. If the theorem is true, it is a clean capstone result. But I found a serious gap in the proof of Theorem 1.6, in Lemma 2.11.\n\nThe issue: in Case 1 of Lemma 2.11, the authors apply Lemma 2.6 to H = G[W] with X = Cβ∩W and Y = Cγ∩W. Lemma 2.6 requires |Y| ≤ (1+δ)|X|. The hypotheses only give |Cγ| ≤ (1+δ)|Cβ|. Since Cβ ⊆ Cγ, the B-vertices in Cβ are included in Cγ, and they do not cancel when you remove B. Writing a=|Cβ|, b=|Cβ∩B|, the largest possible |Cγ∩W| is (1+δ)a − b, which exceeds (1+δ)(a−b) whenever b>0. For example, a=10, b=5, δ=0.1 gives |Cγ∩W| up to 6, while (1+δ)|Cβ∩W|=5.5. So the ratio condition is not satisfied, and Lemma 2.6 cannot be invoked as written. The same problem appears in Lemma 2.8, where Lemma 2.6 is applied to XW and YW without checking the ratio. This is not cosmetic: Lemma 2.11 is the only step that amplifies from (1+δ)^{k_*}|Cπ/2| to n/2. Without a valid proof, Theorem 1.6 is not established.\n\nI want to stress the paper is not careless elsewhere: the probability estimates in Section 3 check out, and the use of [1] as an external benchmark is appropriate. The gap may well be repairable — perhaps by proving a variant of Lemma 2.6 that only needs |Y| ≤ K|X| for a constant K and tracking the constant, or by handling the B-vertices separately. But as written, the central technical theorem is unproven.\n\nRecommendation: This deserves serious peer review, but not acceptance without fixing the gap. I would send it back for major revision and ask the authors to either repair Lemma 2.11 (and Lemma 2.8) or clearly state the additional argument needed. If they can produce a correct amplification step, the paper would be strong.","headline":"The defective-expander theorem is a genuine advance, but Lemma 2.11's amplification step has a load-bearing gap that leaves Theorem 1.6 unproven as written.","tokens_in":12151,"tokens_out":5937,"would_cite":false,"duration_ms":52887,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","34D06","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that in the random graph process, every graph from the connectivity time onward is globally synchronizing with high probability.","keywords":["Kuramoto model","global synchronization","random graph process","binomial random graph","defective expander","connectivity threshold","spurious local minima","spectral expansion"],"falsifier":"Run the random graph process on a large $n$ and, for a fixed $\\varepsilon>0$, check the set $B$ of vertices with degree at most $11\\varepsilon\\log n$ at the time $\\sigma=(\\log n-g(n))/(n-1)$: if $B$ ever has an internal edge in $G_\\omega$ or some vertex outside $B$ has two neighbors in $B$, the proof's decomposition fails at that $\\varepsilon$. The decisive test is to search numerically for a non-trivial local minimum of the oscillator energy in $G(n,\\tau)$; finding one with positive probability would refute the theorem.","tokens_in":11107,"feed_emoji":"🎵","tokens_out":12297,"duration_ms":120895,"temperature":0.7,"pith_summary":"The paper proves that in the standard random graph process, connectivity is the only obstruction to global synchronization — meaning convergence to the all-in-phase state from almost every initial condition: with high probability every graph $G(n,m)$ with $m \\ge \\tau$, where $\\tau$ is the hitting time of connectivity, is globally synchronizing. This is the stronger, simultaneous reading of the conjecture from [1], and it is best possible because a disconnected graph can never be globally synchronizing. The proof works by isolating the few low-degree vertices that exist at the connectivity time, treating them as 'defects', and showing that the remaining core is a strong spectral expander. A new deterministic theorem says any such defective expander has no spurious local minima for the oscillator energy, which is exactly what global synchronization requires.","feed_headline":"Random graphs synchronize the moment they connect","feed_subtitle":"For the random graph process, the Kuramoto oscillator network synchronizes as soon as the graph is connected.","key_machinery":"The load-bearing object is the defective expander: a graph whose vertex set is partitioned as $V=W\\cup B$, where $G[W]$ satisfies the spectral bound $\\|A_{G[W]}-(d/|W|)J\\|\\le 2\\alpha d$ and the defect set $B$ obeys (B1)–(B4) — small size, no internal edges, bounded degree, and no vertex of $W$ adjacent to two vertices of $B$. Theorem 1.6 shows such graphs have no non-trivial stable states. The proof's engine is a pair of amplification lemmas: starting from the half-circle lemma, they show that if many vertices have phases at least $\\beta$, then either many more vertices have phases at least a slightly smaller $\\gamma$, or the set has already reached size $\\alpha n$ or $n/2$. Iterating this geometric growth eventually forces $|C_\\beta|\\sin^2\\beta$ beyond the expander bound $5\\alpha^2 n/2$, a contradiction.","core_discovery":"The central claim is Theorem 1.2: with probability tending to 1, the graphs $G(n,m)$ are globally synchronizing for every $m$ from the connectivity time $\\tau$ onward, simultaneously. The route is a deterministic theorem (Theorem 1.6): a graph with no isolated vertices is globally synchronizing whenever its vertices split into a core $W$ and a small exceptional set $B$ such that the whole graph is an $(n,d,\\alpha)$-expander, the induced core $G[W]$ has degrees between roughly $2(\\varepsilon+\\alpha)d$ and $d_{\\max}$, and $B$ obeys (B1)–(B4): small size, no internal edges, bounded degree, and no vertex of $W$ adjacent to two vertices of $B$. In the random process, $B$ is chosen as the set of vertices whose degree in $G_\\sigma$ is at most $11\\varepsilon\\log n$ just before the connectivity time, and the hypotheses are shown to hold simultaneously for every $p\\in[\\lambda,\\omega)$. For $p\\ge\\omega$, the earlier expander theorem from [1] applies, so the entire process from $\\tau$ onward is synchronizing.","pith_inferences":["The defective-expander criterion is likely portable: other random graph models whose low-degree vertices form a small, independent set with private neighborhoods, and whose core is spectrally expanding, should become globally synchronizing at their own connectivity times.","The constants in the proof ($11\\varepsilon$, $20\\sqrt{\\log n}$, the cutoff $\\omega=5\\log n/(n-1)$) are not optimized; the argument only needs some sufficiently small $\\varepsilon>0$, so the threshold statement is probably robust to tighter choices.","One could test whether the same phenomenon holds for random $d$-regular processes or percolated expanders, where low-degree defects are absent or controlled differently.","The angular amplification argument suggests a quantitative stability statement: near a spurious local minimum, phases would have to concentrate on two arcs, and the expander bound forbids that; this might be turned into explicit energy barriers."],"forward_implications":["With high probability, every graph in the process from the connectivity time onward is globally synchronizing, so adding edges after $\\tau$ cannot be required for synchronization.","The connectivity threshold $\\log n/n$ is simultaneously the synchronization threshold for the process, matching the necessary condition exactly.","The defective-expander theorem provides a deterministic sufficient condition for global synchronization in graphs with a small set of low-degree vertices, a regime where previous expander criteria fail.","The simultaneous statement rules out the possibility that individual times $m\\ge\\tau$ are synchronizing only marginally; the entire tail of the process is synchronizing at once."],"supporting_citations":[{"why":"Supplies the deterministic expander-to-synchronization theorem, the half-circle bound used as the contradiction target, and the dense-regime results Corollary 6.6 and Proposition 6.9.","marker":"[1]"},{"why":"Provides the concentration lemma (Lemma 5.1) that Lemma 3.1 modifies to control the low-degree set $B$.","marker":"[2]"},{"why":"Provides the other source lemma (Lemma 10.2) used for the $B$-set concentration estimates.","marker":"[3]"},{"why":"Establishes the previous best threshold $p=\\Omega(n^{-1}(\\log n)^2)$ that the current result improves to the connectivity threshold.","marker":"[4]"},{"why":"Introduced the threshold question for global synchronization on $G(n,p)$ and conjectured the optimal $n^{-1}\\log n$ scaling.","marker":"[6]"}],"fun_headline_variants":["Random graphs sync exactly when they connect","Connectivity is the tipping point for global sync","Global synchronization begins at graph connectivity","Random graph process syncs at the connected moment"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on Lemma 3.1, a concentration assertion that just before connectivity the low-degree vertices are few, have no edges among themselves, have bounded degree, and no other vertex is adjacent to more than one of them; if this assertion fails at the chosen $\\varepsilon$, the defective-expander theorem cannot be applied at the connectivity time.","fun_headline_variants_meta":{"raw":{"variants":["Random graphs sync exactly when they connect","Connectivity is the tipping point for global sync","Global synchronization begins at graph connectivity","Random graph process syncs at the connected moment"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000238,"raw_usage":{"total_tokens":1493,"prompt_tokens":907,"completion_tokens":586,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":532}},"tokens_in":523,"tokens_out":586,"duration_ms":6101,"temperature":1.0,"reasoning_tokens":532,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:25:11.362600+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the random graph process on a large $n$ and, for a fixed $\\varepsilon>0$, check the set $B$ of vertices with degree at most $11\\varepsilon\\log n$ at the time $\\sigma=(\\log n-g(n))/(n-1)$: if $B$ ever has an internal edge in $G_\\omega$ or some vertex outside $B$ has two neighbors in $B$, the proof's decomposition fails at that $\\varepsilon$. The decisive test is to search numerically for a non-trivial local minimum of the oscillator energy in $G(n,\\tau)$; finding one with positive probability would refute the theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the other source lemma (Lemma 10.2) used for the $B$-set concentration estimates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the previous best threshold $p=\\Omega(n^{-1}(\\log n)^2)$ that the current result improves to the connectivity threshold."},{"cited_title":"39, Springer, Berlin-New York, 1975, pp","cited_arxiv_id":null,"evidence_quote":"Introduced the threshold question for global synchronization on $G(n,p)$ and conjectured the optimal $n^{-1}\\log n$ scaling."}],"review_version":1}