{"id":"2bac3441-163c-45a7-b48e-c16b96c56f5b","arxiv_id":"2607.15941","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The asymptotic maximum of λ₁(G)+λ₂(complement of G) is exactly 8/7 per vertex, with new general bounds for all pairs and a short proof of Terpai's spectral-radius bound.","lead":"This paper bounds the sum of an eigenvalue of a graph and an eigenvalue of its complement (Nordhaus-Gaddum type inequalities). It proves the exact asymptotic value 8/7 for the (1,2) pair, gives general bounds for all pairs, and offers a short proof of a known spectral-radius result.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound proof for α_{1,2}=8/7 is invalid: Proposition 13 computes λ_k(G) instead of λ_k(\\bar G) and its Perron-vector claim fails for k≥3. The true extremal graph is stated but its spectrum is not shown, so tightness is unproven as written.","rationale":"After reading the paper, I focused on whether the proof establishes α_{1,2}=8/7. The upper bound via Lemma 16 and Theorem 18 is rigorous: Lemma 16's algebra and the construction of two disjoint positive vectors from the components of the complement are both valid. The only issue is the lower bound. The reader's weakest_assumption points precisely to Proposition 13, and I agree that it is the load-bearing weak point. Proposition 13 is demonstrably false for k≥3 (the Perron-vector condition fails), and even for k=2 it proves a statement about λ_k(G) rather than λ_k(\\bar G). The complement of J3∨2J2 under the looped definition is three isolated vertices plus a simple C4, whose second eigenvalue is 0, giving ratio 6/7, not 8/7. Thus the paper's only written justification for tightness is wrong. However, I checked the alternative graph J3∨C4: a simple 2×2 quotient (constant vectors on the clique and on the cycle) yields λ1=6, and the looped complement (three isolated vertices plus a looped C4) has λ2=2, so λ1+λ2=8, n=7, matching 8/7. This means the central claim is likely correct but the proof as written is incomplete: the authors must replace Proposition 13 with a correct computation for the extremal graph, or at least display the spectrum. The conjecture for k≥3 is entirely unsupported and may be false. Therefore the reader's CONDITIONAL verdict is appropriate; I would not change it. The concrete check I propose would settle whether the lower bound for α_{1,2} holds and would expose the false proposition for k≥3.","tokens_in":13857,"tokens_out":25886,"duration_ms":214195,"concrete_test":"Compute the full spectrum of G=J3∨C4 (looped clique on 3 vertices joined with a 4-cycle) and of its complement defined by A+\\bar A=J. If λ1(G)=6 and λ2(\\bar G)=2, then the t-blowup sequence gives α_{1,2}≥8/7, confirming the lower bound despite the flawed Proposition 13.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 13 claims α_{1,k} ≥ 4k/(4k−1) using G = J_{2k−1}∨kJ_2. Two flaws: (i) For k≥3, the asserted Perron vector (2k on J_{2k−1}, 2k−1 on kJ_2) is not an eigenvector: on a kJ_2 vertex, (Ax)_i = (2k−1)(2k+2) while λ x_i = (4k−2)(2k−1), which are unequal unless k=2. (ii) Even for k=2, the proof uses λ_k(G), not λ_k(\\bar G). Since \\bar G for G=J3∨2J2 is three isolated vertices plus a simple C4 (no loops), λ_2(\\bar G)=0, so λ1(G)+λ2(\\bar G)=6, not 8. The stated lower bound for α_{1,2} therefore does not follow. The separately claimed extremal graph J3∨C4 (with looped complement) does appear to give λ1=6 and λ2(\\bar G)=2, ratio 8/7, but this spectrum is never computed in the paper. Without a valid lower-bound argument, the central equality α_{1,2}=8/7 is not established by the text; the conjecture α_{1,k}=4k/(4k−1) for k≥3 rests on the same false proposition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Nordhaus–Gaddum type problems for adjacency eigenvalues of looped graphs, focusing on α_{i,j} = lim n^{-1} max_G (λ_i(G)+λ_j(\\bar G)) and the analogous minimum quantity β_{i,j}. The authors prove general upper bounds on α_{i,j} using the Brooks–Linz–Lu spread bounds, give a new short proof of Terpai's theorem λ_1(G)+λ_1(\\bar G) ≤ (4/3)n − 1, and prove the upper bound λ_1(G)+λ_2(\\bar G) ≤ (8/7)n. They further claim the exact value α_{1,2} = 8/7, achieved by a blowup of J_3∨C_4, and conjecture α_{1,k} = 4k/(4k−1) for all k ≥ 3, supported by a construction in Proposition 13. The paper also proves an upper bound α_{1,k} ≤ (k+√(k(4k−1)))/(3k−1) and bounds on |β_{i,j}|.","tokens_in":14233,"tokens_out":22649,"duration_ms":196873,"significance":"The upper-bound machinery is attractive and, in particular, Lemma 16 gives a genuinely short and self-contained proof of Terpai's bound, which is a meaningful contribution. The claimed upper bound λ_1(G)+λ_2(\\bar G) ≤ 8n/7, if correct, is also a strong result, and the connection to spectral spreads is well motivated. However, the paper's claimed exact value α_{1,2}=8/7 is not established as written: the lower-bound argument in Proposition 13 is false, and the spectrum of the separately stated extremal graph J_3∨C_4 is never computed. Because the exactness claim and the conjecture for k ≥ 3 rest on that invalid proposition, the central contribution of the paper is currently unsupported. The upper bounds and the Terpai proof are sound and salvageable, so the manuscript has clear potential after a substantial revision.","major_comments":[{"comment":"Proposition 13 is false. For G = J_{2k−1}∨kJ_2, the vector x with x_i=2k on the J_{2k−1} part and x_i=2k−1 on the kJ_2 part is not an eigenvector for k ≥ 2. For a vertex in kJ_2, (Ax)_i = (2k−1)(2k+1), whereas (4k−2)x_i = (2k−1)(4k−2); these agree only when k=3/2. Thus the asserted λ_1(G)=4k−2 is incorrect. Moreover, the proof applies λ_k(G) rather than λ_k(\\bar G). For k=2, G=J_3∨2J_2 has complement consisting of three isolated vertices plus a simple C_4, so λ_2(\\bar G)=0, and λ_1(G)+λ_2(\\bar G)=2+√13≈5.61, not 8. This proposition cannot provide the claimed lower bound α_{1,k} ≥ 4k/(4k−1).","section":"Section 3, Proposition 13"},{"comment":"The proof of Theorem 18 concludes 'Proposition 13 shows that this bound is tight', but Proposition 13 is not only false; its graph J_3∨2J_2 is not the extremal graph J_3∨C_4 named in Theorem 3. The spectrum of J_3∨C_4 is never computed in the paper, and no other lower-bound construction for α_{1,2}=8/7 is supplied. Since the equality claim requires both an upper bound and a matching lower bound, α_{1,2}=8/7 is unproven as written. A direct computation (λ_1(J_3∨C_4)=6 and λ_2 of its complement =2) would repair this, but the computation must actually appear.","section":"Theorem 18 and Theorem 3"},{"comment":"The conjecture α_{1,k}=4k/(4k−1) for k ≥ 3 and the lower-bound entries in Table 2 for row i=1 rely entirely on Proposition 13. Since that proposition is false, these lower bounds are unsupported. In particular, Table 2 lists 'J_3∨2J_2' as the extremal graph for α_{1,2}, contradicting Theorem 3's claim that the extremal graph is J_3∨C_4. The tables and conjecture should be revised to reflect only constructions whose spectra are actually verified.","section":"Conjecture 20 and Appendix Table 2"}],"minor_comments":[{"comment":"Theorem 14 states an upper bound on λ_1(G)+λ_k(G), but the proof and the definition of α_{1,k} show the intended quantity is λ_1(G)+λ_k(\\bar G). The notation should be corrected consistently.","section":"Theorem 14 statement"},{"comment":"In the sentence 'we denote the eigenvalues of G by μ_1 ≥ ... ≥ μ_n', the graph should be \\bar G, as is clear from the trace identity that follows.","section":"Proof of Theorem 14"},{"comment":"The expression 'G = kJ_2 ∪ (2k−1)K_1 = J_{2k−1} ∨ kJ_2' is confusing: a disjoint union is not a join. The graph should be defined unambiguously, preferably with an explicit adjacency-matrix description.","section":"Proposition 13, notation"},{"comment":"The extremal graph listed for α_{1,2} is inconsistent with the statement of Theorem 3. If J_3∨C_4 is the intended graph, the table should say so and give its spectrum.","section":"Appendix Table 2"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound part of the paper, especially Lemma 16 and the new proof of Terpai's theorem, is sound and worth publishing. The problem is the lower-bound/tightness portion: Proposition 13 is not merely incomplete but mathematically false, and the claimed equality α_{1,2}=8/7 is unsupported without a correct spectral computation. I verified that a direct computation for J_3∨C_4 does give the missing lower bound, so the central claim can likely be rescued. However, the current manuscript contains a false proposition, an inconsistent table, and a conjecture based on that false proposition; these need substantive correction before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's upper-bound program is real, and Lemma 16 is a genuinely nice piece of work. But the flagship result — the exact value α_{1,2}=8/7 — is not actually proved. The lower-bound side rests on Proposition 13, which is wrong. For k≥3, the alleged Perron vector of J_{2k−1}∨kJ₂ is not an eigenvector; for k=2, the proof uses λ_k(G) instead of λ_k(complement). The complement of that construction has λ_k=0, so it gives no lower bound at all. The extremal graph J₃∨C₄ mentioned in Theorem 3 may be the right one, but its spectrum is never computed, so tightness is simply unverified.\n\nWhat is new and worth keeping: Theorem 4's bound on α_{1,k}, Theorem 5's bound on |β_{i,j}|, and the short proof of Terpai's bound via Lemma 16. The way Lemma 16 converts Perron-vector information into a clean inequality is elegant, and the connection to the Brooks–Linz–Lu spread problem is natural. The paper is also transparent about which items are due to Nikiforov and which are new.\n\nThe soft spot is concentrated in the lower-bound constructions. Proposition 13 feeds the conjecture α_{1,k}=4k/(4k−1) and the tables in the appendix, so those need to be reassessed. The Lagrange multiplier step in Theorem 14 is compressed but seems plausible. The sparse6 graph encodings in the appendix are hard to check by eye, but that is minor — the code can be run.\n\nWho is this for: spectral graph theorists working on Nordhaus–Gaddum type extremal problems. The upper-bound results, especially Lemma 16, are worth referee time. The paper should not be accepted as is, but it is not a desk reject.\n\nRecommendation: send it to review, and ask the authors to fix or remove Proposition 13, compute the spectrum of the claimed extremal graph, and correct the conjecture and tables. With that repair, the 8/7 result has a good chance of being right.","headline":"The upper-bound machinery is solid and worth reading, but the claimed exact value α_{1,2}=8/7 is not established because the lower-bound proposition is wrong.","tokens_in":14812,"tokens_out":5353,"would_cite":false,"duration_ms":51650,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that for every looped graph on n vertices, the largest eigenvalue plus the second-largest eigenvalue of its complement never exceeds 8n/7, and that this constant is asymptotically exact.","keywords":["Nordhaus–Gaddum inequalities","adjacency eigenvalues","spectral radius","eigenvalue sum","graph complement","Perron vector","spectral gap","looped graphs"],"falsifier":"Compute the adjacency spectrum of G=J_{2k−1}∨kJ₂ for k=3 (or any k≥3) and check whether λ1(G)+λk(G) equals 4k; the proposed Perron vector fails Ax=(4k−2)x, so this is directly checkable. Also compute the spectrum of the 7-vertex graph J3∨C4 and verify whether its t-blowup has (λ1+λ2)/n tending to 8/7. If the first quantity is less than 4k, Conjecture 20 is false; if the second is not 8/7, the stated extremal graph is wrong.","tokens_in":13705,"feed_emoji":"📐","tokens_out":8781,"duration_ms":75986,"temperature":0.7,"pith_summary":"Across all looped graphs on n vertices, the paper proves that λ1(G)+λ2(complement) is at most (8/7)n, and that this ratio is asymptotically sharp, so α_{1,2}=8/7 exactly. This is the first exact value in a natural family of Nordhaus–Gaddum problems for eigenvalues. The same proof technique gives a short, self-contained derivation of the known bound λ1(G)+λ1(complement) ≤ (4/3)n−1 for simple graphs. For every k≥2, the paper also derives general upper bounds on λ1(G)+λk(complement), reducing them to a quadratic inequality and a Lagrange-multiplier optimization. The results are obtained from Perron vectors, Weyl inequalities, and trace identities, with no heavy machinery.","feed_headline":"Complementary eigenvalue pair never exceeds 8n/7","feed_subtitle":"Exact asymptotic constant found for a long-studied eigenvalue sum; same trick recovers the 4n/3 bound.","key_machinery":"The main instrument is Lemma 16, which bounds λ1(G)+λk(complement) by 4kn/(4k−1) whenever the complement has k nonnegative vectors y_r with pairwise disjoint supports satisfying A(complement)y_r ≥ λk y_r. The proof introduces the deficit vector d=(c/λ1)1−x for the Perron eigenvector x of G, and shows that each y_r forces at least c μ^2/(λ(λ+μ)) total deficit on its support; disjointness then sums these lower bounds to produce the inequality. For k=2, the required vectors are constructed by examining the component structure of the complement. The general upper bounds of Section 3 instead combine the trace identities tr(A^2)+tr(B^2)=n^2 and tr(A)+tr(B)=n with Weyl's inequalities, yielding a qu","core_discovery":"The central claim is the exact asymptotic constant α_{1,2}=8/7: the limit of max_G (λ1(G)+λ2(complement))/n over looped graphs G equals 8/7, and equality is attained by blowups of the looped graph J3∨C4 (a looped triangle joined to a 4-cycle). The proof of the upper bound models the complement's second eigenvalue by two nonnegative vectors with pairwise disjoint supports that act as approximate eigenvectors, then uses a 'deficit vector' derived from the Perron eigenvector of G to obtain λ1+λ2 ≤ 8n/7. The same lemma immediately yields λ1+λ1 ≤ 4n/3, reproducing the known spectral-radius Nordhaus–Gaddum bound with a short argument. For general k, a trace-plus-Weyl argument produces a quadratic","pith_inferences":["The deficit-vector construction might generalize to all k: if one can produce k disjoint approximate eigenvectors for the complement of a candidate extremal graph, the bound 4k/(4k−1) would be tight for every k, making the paper's Conjecture 20 plausible despite the apparent error in the stated lower-bound construction.","The lower-bound construction in Proposition 13 appears to contain an algebraic error for k≥3 (the claimed Perron vector is not actually an eigenvector); correcting it could change the conjectured values of α_{1,k}.","The method of bounding λ1+λk by a quadratic inequality in the two individual eigenvalues may extend to other pairs (i,j), potentially yielding exact constants for all (i,j) where the extremal graphs are regular.","Because the (1,2) extremal graph J3∨C4 is near-regular, a plausible pattern is that extremal sequences for all pairs are regular or nearly regular; if so, the gap between the two spread bounds in Lemma 9 closes and gives exact α_{i,j}."],"forward_implications":["If α_{1,2}=8/7 is correct, extremal sequences must asymptotically look like blowups of J3∨C4, giving a concrete structural prediction for near-extremal graphs.","The deficit-vector lemma gives a one-page proof of the spectral-radius Nordhaus–Gaddum bound λ1+λ1 ≤ 4n/3, making the previously analytic proof elementary.","The quadratic-inequality method yields the general upper bound λ1+λk ≤ n(k+√(k(4k−1)))/(3k−1), which for k≥2 improves the bound obtained from spectral-gap estimates.","The analogous smallest-eigenvalue problem is settled up to a signed constant: |β_{i,j}| ≤ (1/2)√(1/i+1/j), with equality for i=j=k whenever a symmetric Hadamard matrix of order 2k exists.","The connection via Weyl's inequalities shows that α_{i,j} lies between the spread constants s_{i−1,j−1} and s_{i−1,j−2}, so progress on spectral gaps transfers directly to Nordhaus–Gaddum constants."],"fun_headline_variants":["Exact 8/7 constant for λ1+λ2 with complements","Graph-complement eigenvalue sum maxes at 8n/7","Sharp 8/7 asymptotic for eigenvalue pairs of graphs","New short proof of 4/3 Nordhaus-Gaddum from 8/7"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The tightness results for the α_{1,k} bounds rely on a specific Perron-vector computation for the graph J_{2k−1}∨kJ₂ (Proposition 13); for k≥3 that vector does not satisfy the eigenvector equation, so the lower bounds and the exactness of α_{1,2}=8/7 as proven in the paper depend on this unsupported calculation, even though the separately stated extremal graph J3∨C4 may still be correct if its spectrum is checked directly.","fun_headline_variants_meta":{"raw":{"variants":["Exact 8/7 constant for λ1+λ2 with complements","Graph-complement eigenvalue sum maxes at 8n/7","Sharp 8/7 asymptotic for eigenvalue pairs of graphs","New short proof of 4/3 Nordhaus-Gaddum from 8/7"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000619,"raw_usage":{"total_tokens":2738,"prompt_tokens":802,"completion_tokens":1936,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":546,"completion_tokens_details":{"reasoning_tokens":1856}},"tokens_in":546,"tokens_out":1936,"duration_ms":13364,"temperature":1.0,"reasoning_tokens":1856,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T21:57:13.679689+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the adjacency spectrum of G=J_{2k−1}∨kJ₂ for k=3 (or any k≥3) and check whether λ1(G)+λk(G) equals 4k; the proposed Perron vector fails Ax=(4k−2)x, so this is directly checkable. Also compute the spectrum of the 7-vertex graph J3∨C4 and verify whether its t-blowup has (λ1+λ2)/n tending to 8/7. If the first quantity is less than 4k, Conjecture 20 is false; if the second is not 8/7, the stated extremal graph is wrong.","supporting_citations":[],"review_version":1}