{"id":"243b0095-aff3-4902-8d51-da9369ba6677","arxiv_id":"2501.00234","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For an Erdős-Rényi graph with fixed edge probability, the random graph Laplacian has simple spectrum with overwhelmingly high probability, with a quantitative n^{-3/2-o(1)} lower bound on the minimum gap.","lead":"This paper proves that the Laplacian of a random graph almost never has repeated eigenvalues, and gives a quantitative bound on how close consecutive eigenvalues can come. The result supports the common assumption behind quantum walks on graphs and spectral clustering algorithms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 7's proof of Theorem 2.1 assumes the last coordinate b of the eigenvector is large, but Claim 3.4 only yields a constant fraction of large coordinates, not a fixed one; the small-b case is unhandled.","rationale":"After reading the full manuscript, the most load-bearing weakness is exactly the one identified by the reader: the proof of Theorem 2.1 (and hence of Theorem 1.2) reduces a small eigenvalue gap to a small-ball probability for v·c_n, but the reduction requires the fixed last coordinate b of the eigenvector to be ≫ n^{-1/2+o(1)}. The cited no-gaps delocalization (Theorem 2.3) and Claim 3.4 only guarantee that all but a constant fraction of the coordinates are large; they say nothing about the specific coordinate used in the interlacing step. The small-b case is not handled separately, and the zero eigenvector of L'_n (with b=0) shows the case is real, although for i=1 the large gap makes it harmless. This is a proof gap, not a contradiction of the theorem; the statement is plausible and the surrounding machinery (no-structure delocalization, overcrowding, switching) is substantial and mostly self-contained. I also examined the τ scaling in Section 4 flagged by the reader; while the notation is terse, the final probability exponent appears compatible with the claimed exp(−Θ(k^{3/2}/log n)) bound, so I do not regard it as the primary obstruction. Because the Section 7 gap is likely fixable with an additional averaging or small-coordinate argument but is not addressed in the current text, the reader's CONDITIONAL verdict remains appropriate; no change is needed.","tokens_in":30117,"tokens_out":22056,"duration_ms":210993,"concrete_test":"Analytical check: Re-derive the reduction in Section 7 starting from Eq. (2) under the assumption |b| ≤ n^{-1/2-o(1)}, attempting to prove |v^T c_n| = O(n^{o(1)}δ) using only the switching randomness on c_n over I_{n−2} and no division by |b|. If no such proof can be given, the proof of Theorem 2.1 is incomplete at this point and the concern lands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 2.1 (Section 7), the authors write an eigenvector u=(w,b) of L'_n and claim: 'By Theorem 2.3 and Claim 3.4, we assume that |b| ≥ n^{-1/2-o(1)} (as these results imply that with probability 1−n^{-ω(1)} the set of indices where |b| ≥ n^{-1/2-o(1)} is of size Θ(n)).' This inference is invalid: Claim 3.4 shows that for every S of size ⌊c0n⌋ there is i∈S with |x_i| ≥ (c1/c0)^{1/2}/√n, and hence at most ⌊c0n⌋−1 coordinates are below that threshold. It does not say anything about a fixed coordinate such as the last one. The subsequent bound |v^T c_n| ≤ n^{o(1)}δ is obtained from |b||v^T c_n| ≤ δn^{-1/2} by dividing by |b|; if |b| is small, this division is unavailable and no alternative argument is given. The case |b| ≤ n^{-1/2-o(1)} is never treated. This is not purely hypothetical: the null eigenvector of L'_n, namely Q^T 1, has last coordinate 0, so the case occurs (though for the zero eigenvalue the gap is large and harmless); for nonzero eigenvalues, nothing in Theorems 2.3/2.4 prevents the last coordinate from being small. Without a bound on |v^T c_n| in the small-b case, the reduction of the gap event to a small-ball probability over the switched column c_n fails.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies eigenvalue gaps of the Laplacian of an Erdős–Rényi graph G(n,p). The main theorem (Theorem 1.2) asserts that for fixed 0<p<1 and any A, for δ ≥ n^{-A}, the maximum over i of P(|λ_{i+1}(L_n)−λ_i(L_n)| ≤ δ n^{-1/2}) is O(n^{o(1)}δ), so the spectrum is simple with probability 1−o(1) and the minimum gap is at least n^{-3/2−o(1)}. The proof works with the centered Laplacian L_n, establishes affine no-gaps delocalization (Theorem 2.3), no-structure delocalization via the least common denominator (Theorem 2.4), an overcrowding estimate (Theorem 2.6), and a small-coordinate bound (Theorem 2.7). A switching/reshuffling argument decouples the last two columns, reducing the gap event to a small-ball probability for a structured vector. The uncentered case follows by a Weyl comparison with L_n.","tokens_in":30482,"tokens_out":25578,"duration_ms":237300,"significance":"If correct, this is a substantial contribution: it appears to be the first proof of simplicity of the spectrum and quantitative gap bounds for the graph Laplacian, a model with dependent entries and a different bulk distribution than Wigner matrices. The auxiliary delocalization results, particularly the affine no-gaps estimate and the no-structure (LCD) delocalization for eigenvectors, are new and likely to be useful beyond this paper. The proof is constructive and quantitative, and it builds on earlier published tools (Cauchy interlacing, Talagrand concentration, LCD small-ball estimates, restricted invertibility) rather than fitting parameters to the target conclusion.","major_comments":[{"comment":"The sentence 'By Theorem 2.3 and Claim 3.4, we assume that |b| ≥ n^{-1/2-o(1)}' is not justified. Claim 3.4 states only that at most ⌊c0 n⌋−1 coordinates can lie below (c1/c0)^{1/2}/√n; it gives no information about a fixed coordinate, and the last coordinate of an eigenvector of L'_n may be zero (e.g., the null vector Q^T 1 has last coordinate 0). The derivation of |v^T c_n| ≤ n^{o(1)}δ from |b| |v^T c_n| ≤ δ n^{-1/2} divides by |b|, so the small-b case is not covered. No alternative argument is supplied. This is load-bearing: without a bound on |v^T c_n| when |b| is small, the reduction of the gap event to the small-ball probability over the switched column c_n fails, so the proofs of Theorem 2.1 and hence Theorem 1.2 are incomplete as written.","section":"Section 7, proof of Theorem 2.1"},{"comment":"The parameter choice τ = K log n / k is not valid over the stated range k ≥ C log n. Since τ is used to form column blocks of size 2τ, it must be a positive integer; for k ≫ log n (for instance k = n^{1−δ0} in Section 5, or k = Θ(n/log^C n) as highlighted after Theorem 2.6), τ = o(1) and 2τ is not an integer, while the binomial variable B(2τ,p) is no longer meaningful. Even ignoring integrality, the Chernoff bound P(|X−2τp| ≥ δ2τp) ≤ 2 exp(−2δ^2τp/3) with δ=1/2 gives a failure probability close to 1 when τ→0, so the claim P(|X−2τp| < δ2τp) ≥ 1−k/(5n) is false in this regime. Consequently, the proof of the overcrowding estimate does not cover the values of k that are used in the no-gaps and no-structure delocalization arguments (Sections 5 and 6).","section":"Section 4, proof of Theorem 2.6"},{"comment":"The inequality in the event is reversed. The proof in Section 6 bounds the probability of the existence of v and I with LCD_{κ,γ}(v_I) ∈ [D0, 2D0) for D0 ≍ n^A, i.e., the structured (small-LCD) event; it does not bound the probability of LCD ≥ n^A. As stated, the theorem asserts the opposite of what is proved. The proof of Theorem 2.1 in Section 7 uses the correct version ('LCD ≥ n^{2A} with probability 1−n^{−ω(1)}'), so the statement must be corrected to LCD_{κ,γ}(v_I) ≤ n^A.","section":"Section 2.2, Theorem 2.4 statement"}],"minor_comments":[{"comment":"The informal 'but let's ignore this minor problem for now' regarding the √2 normalization should be replaced by a precise statement, since the normalization affects the distribution of the switched entries and the small-ball application.","section":"Section 2.1"},{"comment":"In Case 2, the threshold 't Pn i=1 Ex2 i pii' appears dimensionally inconsistent; it should presumably be t√(∑ Ex_i^2 p_ii) or tT√k.","section":"Section 4, Lemma 4.1 proof"},{"comment":"The phrase 'the presence of small entries in the eigenvectors' is the opposite of the content of Theorem 2.7, which bounds the number of small entries; rephrase as 'bounds on the number of small entries'.","section":"Abstract"},{"comment":"After deriving |v·c_n| ≤ n^{o(1)}δ, the application of Theorem 3.7 requires the subvector v_{I_{n-2}} to have non-negligible norm; this follows from Theorem 2.3 but should be stated explicitly.","section":"Section 7, proof of Theorem 2.1"},{"comment":"The bound '1√log logn ≤ λn' should be typeset as 1/√log log n ≤ λ_n to avoid confusion with the earlier bound in Theorem 2.3.","section":"Section 2.5, remark after Theorem 2.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically ambitious and the overall strategy is credible, but the two gaps identified above (the small-|b| case in Section 7 and the τ scaling in Section 4) are genuinely load-bearing, and the theorem statement of Theorem 2.4 is wrong as printed. All three issues appear fixable within the scope of the manuscript, so I recommend major revision rather than rejection. I would also encourage the authors to double-check the parameter bookkeeping in Section 4, since the current τ = K log n / k choice seems to be a straightforward algebraic slip."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves that the Laplacian of G(n,p) has simple spectrum with quantitative gap bounds, and it does so with genuinely new machinery. The affine no-gaps and no-structure delocalization results are new and should be independently useful. The neighbor-reshuffling trick is a clever workaround for the dependence between the last column and the principal minor, and the applications to quantum walks and spectral clustering are honestly motivated. If the proofs hold, Theorem 1.2 is a real step beyond the adjacency-matrix results.\n\nThe proof has two soft spots, and both are real. The more serious one is in Section 7. The authors claim that by Theorem 2.3 and Claim 3.4, the last coordinate b of the eigenvector satisfies |b| ≥ n^{-1/2-o(1)}. Claim 3.4 only says that at most a constant fraction of coordinates are small; it says nothing about a fixed coordinate. The null eigenvector of L'_n is exactly the all-ones vector rotated, and its last coordinate is zero, so the small-b case actually occurs. Without a lower bound on |b|, the division in equation (2) is unavailable and the reduction to the small-ball estimate for |v^T c_n| is unsupported. This is a gap in the argument as written, not a minor typo.\n\nThe second issue is in Section 4. The proof of Theorem 2.6 first calls tau a sufficiently large constant, then sets tau = K log n / k. For k of order n/2, tau is sub-constant and the block sizes make no sense; the Chernoff bound written does not give the claimed probability. I suspect the authors meant tau = K log n, but as written the overcrowding estimate is not proved for the full stated range.\n\nThe paper's own remarks are honest about what is and is not addressed, and the citations to prior work look appropriate. The main theorem is novel and the strategy is credible, but the two gaps must be fixed before the proof is convincing.\n\nThis paper deserves a serious referee, despite the gaps. I would send it to review, with instructions to look closely at Section 7. If the small-b case can be handled, the result is an important contribution to random matrix theory and spectral graph theory.","headline":"Strong, novel result with two proof gaps that need fixing before the theorem is fully supported.","tokens_in":30982,"tokens_out":6561,"would_cite":true,"duration_ms":64942,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","60C05","05C80","15B52"],"pacs":[],"model":"deepseek-v4-flash","headline":"The eigenvalue gaps of a random graph Laplacian are controlled by a quantitative bound: for any fixed edge probability p and any polynomial-scale threshold δ, the chance that two consecutive eigenvalues are closer than δ n^{-1/2} is at…","keywords":["eigenvalue gaps","graph Laplacian","Erdős-Rényi random graphs","simple spectrum","delocalization","least common denominator","overcrowding","random matrices"],"falsifier":"Compute the probability that the eigenvector of the smallest nonzero eigenvalue of the Laplacian of G(n,1/2) has last coordinate below $n^{{-1/2-o(1)}}$. If that probability is not o(1), the proof's assumption that |b| ≥ $n^{{-1/2-o(1)}}$ fails and the small-b case would require a new argument; if it is o(1), the gap is harmless and the theorem still stands. A direct simulation of |b| for moderate n, or a conditional calculation given the no-gaps and no-structure events, would settle which holds.","tokens_in":29941,"feed_emoji":"🎲","tokens_out":6563,"duration_ms":60883,"temperature":0.7,"pith_summary":"Random Erdős–Rényi graphs have Laplacians whose eigenvalues are all distinct with probability tending to one, and the paper proves a quantitative version of this: for any fixed edge probability p and any polynomial-scale threshold δ, the chance that any two consecutive eigenvalues are closer than δ $n^{{-1/2}}$ is at most O($n^{{o(1)}}$δ). A union bound over the n gaps gives that the minimum eigenvalue gap is at least $n^{{-3/2-o(1)}}$ with probability 1-o(1). This matters because algorithms for quantum walks on graphs, spectral clustering, and graph neural networks assume or benefit from simple spectra and non-degenerate gaps, and the result supplies a theoretical guarantee for those assumptions. The proof works for both the combinatorial Laplacian and its centered version, and along the way establishes new delocalization and small-ball estimates for Laplacian eigenvectors that are of independent interest.","feed_headline":"Random graph Laplacians have simple spectrum with high probability","feed_subtitle":"For every polynomial-scale threshold δ, a gap below δ n^{-1/2} has probability only O(n^{o(1)}δ).","key_machinery":"The mechanism that carries the argument is a spectrum-preserving reshuffling of the last two columns of the Laplacian: replacing (c_{n-1}, c_n) by (c_{n-1}+c_n)/√2 and (c_{n-1}-c_n)/√2 preserves the spectrum while creating fresh independent randomness on the set of vertices adjacent to exactly one of the two last vertices. This converts the small-gap event into a small-ball estimate |v·c_n| ≤ $n^{{o(1)}}$δ for an eigenvector v of the (n-1)-by-(n-1) minor. To make that estimate uniform in v, the paper proves affine no-gaps delocalization (no segment v_I of linear size is well approximated by a constant vector after any shift), no-structure delocalization (segments v_I have large least common denominator, the smallest scaling at which a normalized vector lands near the integer lattice), and an overcrowding bound showing that rectangular minors of the Laplacian are nearly isometric. These ingredients let the proof run the classical interlacing and eigenvector-gap argument despite the Laplacian's dependent diagonal entries.","core_discovery":"The paper's central claim is Theorem 1.2: for fixed 0<p<1 and any fixed constant A, for any δ ≥ $n^{{-A}}$, the probability that the random graph Laplacian L_n of G(n,p) has a pair of consecutive eigenvalues within δ $n^{{-1/2}}$ is O($n^{{o(1)}}$δ). Consequently the spectrum is simple with probability 1-o(1), and the minimum gap is at least $n^{{-3/2-o(1)}}$ with probability 1-o(1). An equivalent statement, Theorem 2.1, holds for the centered Laplacian L_n = L_n - EL_n, whose dependent diagonal entries are handled directly; the proof is carried out for the centered model and then transferred to L_n by a Weyl-type argument that isolates the zero eigenvalue. The paper also proves affine no-gaps delocalization and no-structure delocalization for Laplacian eigenvectors, an overcrowding estimate for the spectrum of rectangular minors, and a bound showing that eigenvectors cannot have more than one coordinate of size below $n^{{-B}}$.","pith_inferences":["The reshuffling trick acts as a general recipe for dependent-entry matrices: an orthogonal rotation that creates fresh randomness in a low-dimensional block may replace the independence assumption that fails for Laplacians, so a similar strategy could apply to stochastic block model Laplacians or random weighted graphs.","The bound O(n^{o(1)}δ) is a first-order repulsion estimate; if the method can be sharpened to O(δ^2), it would match the quadratic level repulsion of the GOE that bulk eigenvalue statistics already suggest for this model.","The 'at most one small coordinate' theorem suggests a concrete testable extension for spectral graph theory: counting nodal domains of random graphs should almost surely show no zero components, so nodal domain counts should equal those predicted for generic eigenfunctions."],"forward_implications":["For every fixed p, the Laplacian of G(n,p) has simple spectrum with probability 1-o(1), so graph algorithms that assume distinct Laplacian eigenvalues are justified on random inputs.","The minimum eigenvalue gap is at least n^{-3/2-o(1)} with probability 1-o(1), giving a concrete stability window for spectral graph partitioning and graph neural network positional encodings.","The same conclusion holds for the centered Laplacian L_n - EL_n, the model whose bulk spectral statistics match the free convolution of a semicircle and a Gaussian.","Laplacian eigenvectors are affine-delocalized: every segment of linear size carries mass at least (log n)^{-O(1)} after any shift, and segments have large least common denominator, so they are far from arithmetic structure.","With high probability an eigenvector cannot have more than one coordinate of size below n^{-B}; in particular, soft nodes — vanishing or near-vanishing eigenvector entries — are essentially forbidden in random graphs."],"supporting_citations":[{"why":"Supplies the interlacing-and-eigenvector reduction for small eigenvalue gaps and the analogous simple-spectrum result for adjacency matrices that this paper adapts to Laplacians.","marker":"[52]"},{"why":"Provides the original no-gaps delocalization theorem for general random matrices, which the paper refines into an affine no-gaps statement for the Laplacian model.","marker":"[60]"},{"why":"Supplies the least-common-denominator small-ball probability estimate and the tensorization lemma used throughout the density estimates.","marker":"[58]"},{"why":"Provides the overcrowding estimate for i.i.d. and symmetric matrices that Theorem 2.6 adapts to the Laplacian's rectangular minors.","marker":"[53]"},{"why":"Supplies the restricted-invertibility lemma used to locate a well-conditioned rectangular submatrix inside the overcrowding argument.","marker":"[51]"},{"why":"Provides the affine Erdős–Littlewood–Offord anti-concentration result used to control rows that involve shifted vector entries.","marker":"[55]"}],"fun_headline_variants":["Random graph Laplacians have simple spectrum with high probability","Random graph Laplacians: simple spectrum with high probability","Simple spectrum for random graph Laplacians","Random graph spectra are simple with high probability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the chosen eigenvector's last coordinate has size at least $n^{{-1/2-o(1)}}$; the cited no-gaps results only guarantee that all but a constant fraction of the coordinates are that large, and the proof does not separately handle the possibility that the last coordinate is small.","fun_headline_variants_meta":{"raw":{"variants":["Random graph Laplacians have simple spectrum with high probability","Random graph Laplacians: simple spectrum with high probability","Simple spectrum for random graph Laplacians","Random graph spectra are simple with high probability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001017,"raw_usage":{"total_tokens":4230,"prompt_tokens":817,"completion_tokens":3413,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":433,"completion_tokens_details":{"reasoning_tokens":3352}},"tokens_in":433,"tokens_out":3413,"duration_ms":25031,"temperature":1.0,"reasoning_tokens":3352,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:57:13.306988+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the probability that the eigenvector of the smallest nonzero eigenvalue of the Laplacian of G(n,1/2) has last coordinate below $n^{{-1/2-o(1)}}$. If that probability is not o(1), the proof's assumption that |b| ≥ $n^{{-1/2-o(1)}}$ fails and the small-b case would require a new argument; if it is o(1), the gap is harmless and the theorem still stands. A direct simulation of |b| for moderate n, or a conditional calculation given the no-gaps and no-structure events, would settle which holds.","supporting_citations":[{"cited_title":"Random matrices: tail bounds for gaps between eigenvalues.Probab","cited_arxiv_id":null,"evidence_quote":"Supplies the interlacing-and-eigenvector reduction for small eigenvalue gaps and the analogous simple-spectrum result for adjacency matrices that this paper adapts to Laplacians."},{"cited_title":"No-gaps delocalization for general random matrices","cited_arxiv_id":null,"evidence_quote":"Provides the original no-gaps delocalization theorem for general random matrices, which the paper refines into an affine no-gaps statement for the Laplacian model."},{"cited_title":"The Littlewood-Offord problem and invertibility of random matrices.Adv","cited_arxiv_id":null,"evidence_quote":"Supplies the least-common-denominator small-ball probability estimate and the tensorization lemma used throughout the density estimates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the overcrowding estimate for i.i.d. and symmetric matrices that Theorem 2.6 adapts to the Laplacian's rectangular minors."},{"cited_title":"Restricted invertibility revisited","cited_arxiv_id":null,"evidence_quote":"Supplies the restricted-invertibility lemma used to locate a well-conditioned rectangular submatrix inside the overcrowding argument."},{"cited_title":"Local and global universality of random matrix cokernels.Mathematische Annalen, pages 1–94, 2024","cited_arxiv_id":null,"evidence_quote":"Provides the affine Erdős–Littlewood–Offord anti-concentration result used to control rows that involve shifted vector entries."}],"review_version":1}