{"id":"9c77b2c7-5d73-4885-8de3-90d0be1de6f4","arxiv_id":"2507.10037","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A new spectral argument shows that very dense graphs far from unions of cliques have least eigenvalue at most -n^{1/4-epsilon}, and this yields max-cut surpluses of order n^{1.01} and m^{0.5001} for H-free graphs.","lead":"This paper proves a sharp spectral bound for very dense graphs that are far from Turan graphs, extending earlier work that only covered density at most one half. It also shows such graphs have unusually large max-cuts, improving a classical bound by a polynomial factor and making progress on several conjectures.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified for the central claim (Theorem 1.3); the proof is internally consistent, with only repairable constant issues in the max-cut applications.","rationale":"The central claim, Theorem 1.3, is well supported. I checked the main chain: Lemma 2.1 gives a correct recursive inequality for S_T; Lemma 4.1 solves this recursion rigorously, with the parameter conditions q + max(p,r) < 2 satisfied in Lemma 2.2; Lemma 2.3 correctly converts a spectral mass bound into either closeness to a disjoint union of cliques or a linear negative eigenvalue, using the induced removal lemma only in a standard way. The reader's identified weakest assumption—the non-explicit δ from the induced K_{1,2} removal lemma—is real but is a matter of effectivity, not correctness; it does not jeopardize the theorem's asymptotic validity. The minor errors flagged by the reader (e.g., the constant in Theorem 7.1 and the p_{i+1} ≥ 2p_i claim) are indeed present but repairable. My own check found an additional arithmetic slip in Lemma 6.6, where multiplying the combined inequality by n introduces an extra factor of n in the error term; this changes a numerical constant but not the structure of the argument or the final results. Since no step appears to assume the conclusion and the core recursion is sound, the paper's conditional verdict remains appropriate; the author should correct the displayed constants and state the required n thresholds more carefully, but no deeper revision is needed.","tokens_in":23979,"tokens_out":43224,"duration_ms":394133,"concrete_test":"Re-derive the inequality in Lemma 6.6 after substituting dim W ≤ S_T^2/T^2 and multiplying by n; verify whether the last term becomes 8 n^{5/3+52c/3} S_T^2/T^2. If so, update the constant 250 to a safe upper bound (e.g., 10^3) and recheck that Sections 7–8 only use the existence of some absolute constant, which they do.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the proof of Theorem 1.3. The contrapositive argument via Lemmas 2.1–2.3 checks out: Lemma 2.1's recursion is valid for general graphs, Lemma 4.1 correctly solves the recursion, and Lemma 2.3's spectral-partitioning argument (including Claims 1–3) is sound. The appeal to the induced graph removal lemma for K_{1,2} in Lemma 5.1 is legitimate, though it makes the δ(ε) constants ineffective and hence all 'n ≫_ε 1' thresholds non-explicit; that is a weakness, not a correctness risk. In the max-cut sections there is a repairable arithmetic slip: after substituting dim W into the inequality following (8)–(10) in Lemma 6.6, the term 8 n^{2/3+52c/3} dim(W) acquires an extra factor of n when multiplied through, changing the lemma's constant from 250 to roughly 556; this does not affect the qualitative structure of Lemma 4.1, so Theorem 1.5 and Theorem 1.7 survive with a modified constant. The 'misquoted' bound in Theorem 7.1 and the p_{i+1} ≥ 2p_i threshold are similarly cosmetic.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an Alon--Boppana-type lower bound on the second eigenvalue of very dense regular graphs: for every ε > 0, every regular n-vertex graph that is ε-far from every Turán graph satisfies λ_2 ≥ n^{1/4−ε}. The main theorem is proved in the complementary form (Theorem 1.3): if G is ε-far from a disjoint union of cliques, then λ_n ≤ −n^{1/4−ε}, with no regularity assumption. The proof introduces a recursive inequality for sums of positive eigenvalues (Lemma 2.1), solves it by a general recursion lemma (Lemma 4.1), and converts the resulting spectral mass bound into structural closeness to a union of cliques via spectral partitioning and the induced graph removal lemma (Lemma 2.3). The same machinery is adapted to the surplus sp(G) = mc(G) − m/2, yielding Theorem 1.5 (sp(G) ≥ n^{1.01} for graphs ε-far from a disjoint union of cliques) and Theorem 1.7 (a density-increment theorem implying that K_r-free graphs with m edges have surplus at least c_r m^{0.5001}). The paper also proves that the exponent 1/4 in the spectral bound is optimal, citing de Caen's construction.","tokens_in":24185,"tokens_out":23323,"duration_ms":218394,"significance":"If correct, Theorem 1.3 is a substantial advance: it confirms the Ráty--Sudakov--Tomon conjecture up to the lower-order factor n^{−ε}, and it removes the previous density restriction d ≤ (1/2−ε)n from earlier independent work of Balla, Ráty--Sudakov--Tomon, and Ihringer. The max-cut consequences are also significant, giving the first absolute polynomial improvement over Edwards' bound for H-free graphs and answering questions posed by Glock--Janzer--Sudakov and Balla--Janzer--Sudakov. The proof is largely self-contained and structurally clear: the key recursion in Lemma 2.1 is derived carefully, the general recursion lemma is stated with explicit parameter conditions, and the spectral-to-structural translation is organized into verifiable claims. A notable weakness is that Lemma 5.1 relies on the induced graph removal lemma for K_{1,2}, so the constant δ(ε) is ineffective and all 'n ≫_ε 1' thresholds are non-explicit; this does not affect the validity of the results but should be acknowledged as a limitation.","major_comments":[],"minor_comments":[{"comment":"In the display following the substitution of dim W into the inequality, the term coming from (10) acquires an extra factor of n after multiplying through by n: it should read 8n^{5/3+52c/3}/T^2 · S_T^2, not 8n^{2/3+52c/3}/T^2 · S_T^2. With this correction the estimate 8n^{5/3+52c/3}/T^2 ≤ 8n^{64c/3−1/3} is still valid for c = 1/99, and the stated conclusion S_T^2 ≤ 250nS_{T^2/(8n)} continues to hold for sufficiently large n; the displayed computation should be fixed.","section":"Section 6, Lemma 6.6"},{"comment":"The sentence 'we just showed that −λ_n ≤ n^{1−4c}' is not literally what was derived from Lemma 6.2; Lemma 6.2 gives −λ_n ≤ n^{(2+c)/3}. The displayed bound n^{1−4c} is valid a fortiori because (2+c)/3 < 1−4c for c = 1/99, but the wording should be corrected to avoid the appearance of a misquoted bound.","section":"Section 7, proof of Theorem 7.1"},{"comment":"In Case 2 of Claim 1, the estimate 'x^T A_G x ≤ 1 − 2(1−µ) + µ ≤ −1 + 3µ ≤ 0.4' has the wrong final inequality: since µ < 0.1, one has −1 + 3µ < −0.7. The Rayleigh-quotient conclusion λ_n ≤ −min(|V_i|,|V_j|)/10 is unaffected once this sign is corrected, so this is a typographical error in a central proof, but it should be corrected.","section":"Section 5, Lemma 2.3, Claim 1"},{"comment":"The claim 'We can check that p_{i+1} ≥ 2p_i always holds' is false as stated for case 2 of Lemma 8.2 unless p_i ≤ (10^{−10}/2)^2. The intended argument uses the fact that before termination p_i < 10^{−100}, which indeed implies the inequality; the qualifier should be added. Also, 'Gi+1 be the graph G1' should read 'Gi+1 be the graph obtained by applying Lemma 8.2 with G0 = Gi'.","section":"Section 8, proof of Theorem 1.7"},{"comment":"In the lower bound for the edge density of H, the displayed term '1 − c0 + 2·10^{−300}ε^3 n_k^2/c_0^2' should be '1 − 1/c_0 − 2·10^{−300}ε^3 n_k^2/c_0^2'. The following estimate is valid with the stated lower bound c_0 ≥ (1/3)p_k n_k, but the formula as written is incorrect.","section":"Section 8, final density calculation"},{"comment":"There are several small typos that should be cleaned up: 'Rayley quotient' should be 'Rayleigh quotient', 'Recal' should be 'Recall', 'paritition' should be 'partition', and the phrase 'with applications to max-cut' in the title is typeset with an en-dash issue in the header. These do not affect the mathematics.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The paper's central theorem and applications are significant and the main proof line is sound. I found no load-bearing error requiring major revision; the issues are local arithmetic/typographical slips that are easily fixed. One point the editor may wish to monitor is that the reliance on the induced graph removal lemma makes all constants ineffective, which is a real limitation but not a correctness concern. The reference to [21] as 'Personal Communication' should be updated if that work has appeared by publication time."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this is the real thing. Theorem 1.3 gives lambda_n <= -n^{1/4-eps} for any graph eps-far from a disjoint union of cliques, confirming the Raty–Sudakov–Tomon conjecture up to a lower-order factor and matching the optimal exponent. The earlier dense Alon–Boppana results only covered density at most 1/2 and gave exponent 1/3. The max-cut consequences—sp(G) >= n^{1.01} for graphs far from a disjoint union of cliques, and sp(G) >= c_H m^{0.5001} for H-free graphs—are genuine progress on two conjectures and answer questions posed by Glock–Janzer–Sudakov and Balla–Janzer–Sudakov.\n\nWhat is actually new: the clipped Gaussian test-vector recursion (Lemma 2.1) that avoids the density restriction, the spectral partitioning in Lemma 2.3, and the fast density increment in Lemma 8.2. The contrapositive architecture is sound: Lemma 2.2 solves the recursion, Lemma 2.3 translates spectral mass into structural closeness, and Theorem 1.3 follows without any circular parameter fitting. I checked the key estimates; no step seems to assume the conclusion.\n\nThe soft spots are real but mostly in the presentation. Three displayed statements are wrong as written: Theorem 7.1 cites -lambda_n <= n^{1-4c} when Lemma 6.2 gives n^{(2+c)/3} (both are o(n), so the contradiction survives); the assertion in Theorem 1.7's proof that p_{i+1} >= 2p_i always holds is too quick—case 2 of Lemma 8.2 only gives p_{i+1} >= constant * sqrt(p_i), and the termination argument only needs p_i^3 n_i non-decreasing; and in Lemma 6.6 the constant 250 appears to drift after substituting the dim W bound (the stress-test note suggests ~556). All of these are repairable with constants adjusted. The more structural weakness is that the induced graph removal lemma for K_{1,2} makes delta(eps) ineffective, so all size thresholds are non-explicit and astronomical. That is a limitation, not a correctness error. The max-cut applications also inherit a log n factor from the Grothendieck constant, which is fine for the claimed polynomial exponents.\n\nThe citation pattern is responsible: the author clearly credits Balla, Raty–Sudakov–Tomon, Ihringer, and the follow-up by Jin–Milojevic–Tomon. The paper is written for spectral graph theorists and extremal combinatorists working on max-cut; it deserves a serious referee. I would send it out, asking for a cleanup of the misquoted inequalities and a careful statement of the thresholds. With that done, accept.","headline":"Proves the dense Alon–Boppana conjecture up to n^{-eps} via a clean spectral recursion; the max-cut consequences are real, and the misstatements in the write-up are cosmetic.","tokens_in":24800,"tokens_out":3636,"would_cite":true,"duration_ms":37083,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that every n-vertex graph which is ε-far from a disjoint union of cliques has least eigenvalue at most −n^{1/4−ε}, and derives from the same spectral recursion new max-cut surplus bounds down to an absolute exponent…","keywords":["spectral graph theory","least eigenvalue","max-cut surplus","complete multipartite graphs","disjoint union of cliques","eigenvalue recursion","H-free graphs","induced graph removal lemma"],"falsifier":"Search for an explicit infinite family of regular $n$-vertex graphs that are $\\epsilon$-far from every balanced complete multipartite graph yet satisfy $\\lambda_2 \\le n^{1/4-\\delta}$ for some fixed $\\delta > 0$ and arbitrarily large $n$. One such family would directly contradict Theorem 1.3; the known equiangular-lines construction is the boundary case where $\\lambda_2$ stays at order $n^{1/4}$.","tokens_in":23707,"feed_emoji":"📉","tokens_out":13292,"duration_ms":130652,"temperature":0.7,"pith_summary":"This paper proves a dense analogue of the classical spectral lower bound for sparse graphs: for any ε > 0, every n-vertex graph that differs from each disjoint union of cliques by at least ε $n^{2}$ edge edits has least eigenvalue at most −$n^{{1/4−ε}}$. Restricting to regular graphs and passing to the complement yields a second eigenvalue at least $n^{{1/4−ε}}$ whenever the graph is ε-far from every balanced complete multipartite graph; the exponent 1/4 is optimal, and only a lower-order $n^{{−ε}}$ factor separates the theorem from the full conjecture. The same recursive inequality powers max-cut surplus results: surplus at least $n^{{1.01}}$ for graphs far from unions of cliques, and surplus at least c_H $m^{{0.5001}}$ for H-free graphs, an absolute exponent improvement over the long-standing √m lower bound. A sympathetic reader should care because very dense graphs, where the classical sparse bound is silent, are shown to obey an equally rigid spectral–structural dichotomy.","feed_headline":"Dense graphs far from cliques get an n^{1/4}-scale eigenvalue","feed_subtitle":"Graphs ε-far from every clique-union have least eigenvalue at most −n^{1/4−ε}, and max-cut bounds improve.","key_machinery":"The key machinery is the recursive inequality of Lemma 2.1: for a graph on $n$ vertices and threshold $T \\ge 4(-\\lambda_n)\\sqrt{n}$, the cumulative positive-eigenvalue sum $S_T = \\sum_{\\lambda_i \\ge T} \\lambda_i$ satisfies $S_T^2 \\le 2n S_{T^2/4n}$. It is proved from the identity $A_G = A_G \\circ A_G$ (the adjacency matrix equals its entrywise square because its entries are 0 or 1), the spectral decomposition, and a Gaussian test vector on the subspace spanned by entrywise products of high eigenvectors; a flatness property of eigenvectors bounds the error terms. Iterating this recursion through Lemma 4.1 controls the total square mass of eigenvalues below any threshold, and Lemma 2.3 translates that spectral control into the structural alternative: close to a clique-union or a linear least eigenvalue. For the max-cut theorems, the same recursion runs with the SDP value $\\mathrm{sp}^*(G)$ in place of $-\\lambda_n$, using a clipped Gaussian vector and energy and inertia bounds, plus a logarithmic approximation factor relating $\\mathrm{sp}^*(G)$ to the true surplus $\\mathrm{sp}(G)$.","core_discovery":"On the paper's terms, the central discovery is that the eigenvalue recursion $S_T^2 \\le 2n S_{T^2/4n}$ (where $S_T$ is the sum of eigenvalues at least $T$) forces a dichotomy: a graph whose spectral mass below $\\gamma n$ is small is either $\\epsilon$-close to a disjoint union of cliques or has a least eigenvalue of linear size. Iterating the recursion shows that if $\\lambda_n \\ge -n^{1/4-\\epsilon}$, the small-eigenvalue mass must be tiny, and Theorem 1.3 follows: for all $n \\ge n_0(\\epsilon)$, being $\\epsilon$-far from a disjoint union of cliques implies $\\lambda_n \\le -n^{1/4-\\epsilon}$. For regular graphs, the complement statement gives $\\lambda_2 \\ge n^{1/4-\\epsilon}$ when the graph is $\\epsilon$-far from every balanced complete multipartite graph. The same machinery, run with a clipped Gaussian test vector and an SDP approximation of max-cut, proves surplus bounds $\\mathrm{sp}(G) \\ge n^{1+c}$ with $c=1/100$, and via a density-increment step, $\\mathrm{sp}(G) \\ge c_H m^{0.5001}$ for $H$-free graphs.","pith_inferences":["If the non-explicit constant in the cherry-removal lemma could be made polynomial, the abstract 'for all $n \\gg_\\epsilon 1$' thresholds would become effective, potentially converting the max-cut bounds into explicit algorithmic guarantees.","The recursion appears to be a general principle for $\\{0,1\\}$ matrices with controlled entrywise products of high-eigenvalue vectors, suggesting analogous eigenvalue lower bounds for higher-dimensional simplicial complexes or hypergraphs with bounded codegrees.","The surplus exponent $1.01$ is probably not optimal; optimizing the clipping parameters and the SDP bounds could push it toward $5/4$, the natural target suggested by the conjectured regular-graph bound.","The density-increment step may be iterable beyond what the paper proves; if it could be repeated polynomially many times, the $H$-free surplus exponent might climb well beyond $0.5001$ toward $3/4$."],"forward_implications":["For regular graphs, the only way to keep the second eigenvalue below $n^{1/4-\\epsilon}$ is to be close to a balanced complete multipartite graph.","Any graph $\\epsilon$-far from a disjoint union of cliques has max-cut surplus at least $n^{1.01}$, improving the classical $\\sqrt{m}$-type bound by a polynomial factor in this very dense regime.","Every $H$-free graph with $m$ edges has max-cut surplus at least $c_H m^{0.5001}$, improving the exponent in the classical bound by an absolute constant.","The spectral recursion is transferable: replacing the least-eigenvalue control by an energy/SDP control yields the same structural dichotomy for surplus problems.","The density-increment result locates a large, very dense induced subgraph whenever a graph has many edges and small surplus, which is exactly the input needed for the $H$-free max-cut application."],"supporting_citations":[{"why":"states the dense-graph conjecture that motivates the paper and supplies the earlier $\\lambda_2 = \\Omega_\\epsilon(n^{1/3})$ result and the max-cut formulation it extends.","marker":"[29]"},{"why":"gives the short linear-algebraic proof for graphs of density at most $1/2$ whose $\\{0,1\\}$-matrix identity Lemma 2.1 refines.","marker":"[9]"},{"why":"supplies the induced graph removal lemma used to convert few induced cherries into closeness to a disjoint union of cliques.","marker":"[4]"},{"why":"provides the equiangular-lines construction that shows the exponent $1/4$ is optimal.","marker":"[15]"},{"why":"supplies the SDP formulation and the energy bound used in the max-cut version of the recursion.","marker":"[28]"},{"why":"establishes the logarithmic approximation factor between the SDP value and the true surplus.","marker":"[5]"},{"why":"gives the classical $\\Omega(\\sqrt{m})$ surplus lower bound that the max-cut theorems improve.","marker":"[16]"},{"why":"provides the previous best $H$-free max-cut exponent and the open question the paper partially answers.","marker":"[18]"}],"fun_headline_variants":["Spectral n^{1/4} bound for dense far-from-Turán graphs","Second eigenvalue at least n^{1/4} for dense far-from-Turán graphs","n^{1/4} spectral gap for dense graphs far from Turán","Dense far-from-Turán graphs have second eigenvalue ≥ n^{1/4}","Far-from-Turán dense graphs force second eigenvalue n^{1/4} scale"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that graphs with few induced cherries (a vertex with two non-adjacent neighbours) are forced to be close to a disjoint union of cliques by a removal-lemma constant that the proof does not make explicit, so every 'for all $n$ sufficiently large' threshold inherits it; for the max-cut theorems, a second premise is that the SDP relaxation stays within a logarithmic factor of the true surplus.","fun_headline_variants_meta":{"raw":{"variants":["Spectral n^{1/4} bound for dense far-from-Turán graphs","Second eigenvalue at least n^{1/4} for dense far-from-Turán graphs","n^{1/4} spectral gap for dense graphs far from Turán","Dense far-from-Turán graphs have second eigenvalue ≥ n^{1/4}","Far-from-Turán dense graphs force second eigenvalue n^{1/4} scale"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002367,"raw_usage":{"total_tokens":9247,"prompt_tokens":1210,"completion_tokens":8037,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":826,"completion_tokens_details":{"reasoning_tokens":7926}},"tokens_in":826,"tokens_out":8037,"duration_ms":63243,"temperature":1.0,"reasoning_tokens":7926,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:44:17.236287+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for an explicit infinite family of regular $n$-vertex graphs that are $\\epsilon$-far from every balanced complete multipartite graph yet satisfy $\\lambda_2 \\le n^{1/4-\\delta}$ for some fixed $\\delta > 0$ and arbitrarily large $n$. One such family would directly contradict Theorem 1.3; the known equiangular-lines construction is the boundary case where $\\lambda_2$ stays at order $n^{1/4}$.","supporting_citations":[{"cited_title":"Positive discrepancy, MaxCut, and eigenvalues of graphs","cited_arxiv_id":"2311.02070","evidence_quote":"states the dense-graph conjecture that motivates the paper and supplies the earlier $\\lambda_2 = \\Omega_\\epsilon(n^{1/3})$ result and the max-cut formulation it extends."},{"cited_title":"Note on the second eigenvalue of regular graphs","cited_arxiv_id":"2311.07629","evidence_quote":"gives the short linear-algebraic proof for graphs of density at most $1/2$ whose $\\{0,1\\}$-matrix identity Lemma 2.1 refines."},{"cited_title":"Efficient testing of large graphs","cited_arxiv_id":null,"evidence_quote":"supplies the induced graph removal lemma used to convert few induced cherries into closeness to a disjoint union of cliques."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the equiangular-lines construction that shows the exponent $1/4$ is optimal."},{"cited_title":"Large cuts in hypergraphs via energy.Mathematical Proceedings of the Cambridge Philosophical Society, page 1–17, May 2025","cited_arxiv_id":null,"evidence_quote":"supplies the SDP formulation and the energy bound used in the max-cut version of the recursion."},{"cited_title":"Quadratic forms on graphs","cited_arxiv_id":null,"evidence_quote":"establishes the logarithmic approximation factor between the SDP value and the true surplus."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the classical $\\Omega(\\sqrt{m})$ surplus lower bound that the max-cut theorems improve."},{"cited_title":"New results for MaxCut in H-free graphs","cited_arxiv_id":null,"evidence_quote":"provides the previous best $H$-free max-cut exponent and the open question the paper partially answers."}],"review_version":1}