{"id":"4684c80a-c27a-4629-adc3-490920d2eadc","arxiv_id":"2506.11401","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The complete split graph K_{⌊n/3⌋} ∨ N_{⌈2n/3⌉} (plus one more when n≡2 mod 3) maximizes ρ(G)+ρ(\\bar G) for all n, resolving Stevanović's conjecture.","lead":"This paper proves a 2007 conjecture that the sum of the spectral radii of a graph and its complement is maximized by a particular complete split graph and its complement, for every order n. The proof is purely linear algebraic, completing cases left open by previous analytic arguments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof hinges on Lemma 2.1 being a universal classification of all extremal graphs; if Csikvári's result only supplies an extremal graph in S*_s, Sections 3–7 never bound graphs outside the staircase class.","rationale":"The paper's central claim is a full resolution of Stevanović's conjecture, and the combinatorial case analysis is intricate and largely self-consistent. In good faith, the argument works if Lemma 2.1 has the universal reading adopted by the authors: every extremal graph admits an ordering whose adjacency matrix lies in S*_s(n). That reading is exactly what makes the phrase 'By Lemma 2.1, to prove Conjecture 1.1, it suffices to consider graphs G such that A(G) ∈ S*_s(n)' valid. The sole support for universality is Remark 2.2, which says Csikvári's proof 'implicitly demonstrates' essentiality. This is a substantial logical dependency: all later propositions assume the staircase hypothesis, so any extremal graph outside S*_s would be outside the scope of the proof. The reader's weakest_assumption identifies the same point. I do not claim the lemma is false; the concern is that the paper's central conclusion depends on a nontrivial 'only if' direction that is cited but not demonstrated, and the published source may state only existence of an extremal representative. The concrete test — reading the original statement or brute-forcing small n — would settle whether this dependency is benign. If the universal form is verified, the proof should be accepted; if only existence is available, the classification statement needs revision, although the conjectured attainment might still be salvaged. Hence a conditional verdict is the most honest adjustment.","tokens_in":21152,"tokens_out":16202,"duration_ms":133996,"concrete_test":"Independently extract the exact statement of the result used from Csikvári [5], and determine whether it proves 'G extremal ⇒ G has an S*_s ordering' or only 'there exists an extremal G with an S*_s ordering'. If only the latter, the proof of Lemma 2.1 / Remark 2.2 is incomplete. As a second check, enumerate all graphs for n ≤ 7 (2^21 = 2,097,152 cases) and test whether every graph attaining the maximum of ρ(G)+ρ(Gbar) is a complete split graph or its complement; a non-split maximizer would refute the classification and hence the universal lemma.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 7 starts from an arbitrary extremal graph and, via Lemma 2.1, claims A(G) ∈ S*_s(n). The paper's own Remark 2.2 is the only place where the 'only if' direction is justified, and it is asserted rather than proved. Csikvári's method, as cited, is typically a shifting/compression argument: it shows that among all graphs an extremal graph can be chosen in the staircase class. Existence of an extremal representative in S*_s is weaker than the statement that every extremal graph has such an ordering. The entire chain of inequalities in Sections 3–7, including Lemmas 3.1, 3.3–3.5, Propositions 5.4, 6.1, 6.4, 6.5, and the equality characterization in Lemma 4.1, begins with an A ∈ S*_s. If a non-staircase graph attained the same maximum, that graph would be invisible to the proof, and the paper's classification of extremal graphs would fail even though Conjecture 1.1's literal 'attained by' statement might still be true. Thus the universal reading of Lemma 2.1 is load-bearing and currently rests on an unproved assertion in Remark 2.2. If only the existential reading is correct, the theorem should be weakened to 'the maximum is attained by the complete split graph', and the claimed classification of every extremal graph would not follow from the present argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Nordhaus-Gaddum problem for the spectral radius and claims to resolve Stevanović's 2007 conjecture: for every n, the maximum of ρ(G)+ρ(\\bar G) over n-vertex graphs is attained by the complete split graph K_{⌊n/3⌋}∨N_{⌈2n/3⌉}, and, when n≡2 (mod 3), also by K_{⌈n/3⌉}∨N_{⌊2n/3⌋}. The proof uses Csikvári's reduction to staircase matrices, introduces parameters c,v,s and their complement counterparts, derives upper bounds φ(A) and φ(\\bar A), then reduces to five residue-class cases and one exceptional case, which is handled by a Kronecker-sum matrix argument. The final section claims that every graph attaining the maximum is a complete split graph or its complement.","tokens_in":21497,"tokens_out":30429,"duration_ms":301938,"significance":"If correct, this is a complete proof of a conjecture that was previously known only for large n via analytic methods, and it is notable for being purely linear algebraic. The paper makes explicit parameter computations, gives equality cases for the row-sum bounds, and reduces the problem to a finite case analysis; these are concrete and checkable strengths. The main caveat is the dependence on the exact quantifier in Lemma 2.1, discussed below.","major_comments":[{"comment":"The proof of §7 begins 'By Lemma 2.1, A∈S*_s(n)' for an arbitrary graph with ρ(A)+ρ(\\bar A)≥ρ0. This requires the universal reading of Lemma 2.1: every extremal graph admits a staircase ordering. The manuscript's own Remark 2.2 states that Csikvári [5] showed the maximum is achieved by a graph with a staircase ordering and then asserts, without proof, that the maximum is attained only by such graphs. If only the existential reading holds, the argument in §§3–7 does not classify every extremal graph, and the final conclusion that G or its complement is complete split is not justified. The conjecture itself can still be recovered by applying the proof to an extremal representative in S*_s, but the quantifier in Lemma 2.1 and the wording of Remark 2.2 must be corrected or the universal statement proved.","section":"§2, Lemma 2.1 and Remark 2.2"},{"comment":"Proposition 3.2 is stated as ρ(A)<ρ(A1), but the proof shows only φ(A)<φ(A1) via (3.2). Because ρ(A)≤φ(A) and ρ(A1)≤φ(A1), the strict inequality for ρ does not follow from the displayed argument. The subsequent applications (after Figure 1 and in Lemma 3.3) use the φ comparison, so the proposition should be restated as φ(A)<φ(A1); if ρ(A)<ρ(A1) is intended, additional justification is needed.","section":"§3, Proposition 3.2"},{"comment":"The derivation of (6.4) and the later use of the equality case of (5.1) in Proposition 6.5 silently assume equality in Lemma 5.1. Lemma 5.1 states only a sufficient condition for equality, and the matrices obtained after Lemma 3.4 satisfy v=n−\\bar c rather than v=n−\\bar c−1. The equality is true when c+\\bar c≥n because then a_{c+1,n−\\bar c}=1 and row c+1 has exactly n−\\bar c ones, but this justification is omitted. Please add it explicitly, since Lemma 6.3 is the basis for the monotonicity of g(x) in Proposition 6.4.","section":"§6, Lemma 6.3 and §7"}],"minor_comments":[{"comment":"Several typos should be corrected: 'suck' → 'such' in the proof of Lemma 2.9, 'shell' → 'shall' in the proof of Proposition 6.1, 'Morover' → 'Moreover' in Lemma 3.5, 'Disctrete' → 'Discrete' in reference [2], and 'Cambrigde' → 'Cambridge' in reference [9].","section":"Throughout"},{"comment":"The proof of Lemma 3.5 is much less detailed than that of Lemma 3.4; please specify the row and column moves used in the construction of A2 and the termination condition for the iterative process.","section":"§3, Lemma 3.5"},{"comment":"The informal description of reading the complement parameters 'leftward from the a_{6,6} position' is hard to follow; a more systematic explanation of how to compute \\bar c, \\bar v, \\bar s from A would improve readability.","section":"§3, after (3.3)"}],"recommendation":"major_revision","confidential_remarks":"The essential concern is the quantifier in Lemma 2.1. If the authors can confirm Csikvári's universal form or supply a proof, the paper is essentially correct; otherwise the classification claim must be weakened to the 'attained by' statement required by the conjecture. I do not see a circularity problem, and the algebra in Sections 6–7 appears internally consistent. The paper is within scope for this journal after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper settles Stevanović's 2007 conjecture: for every n, the maximum of ρ(G)+ρ(\\bar G) is attained by K_{⌊n/3⌋}∨N_{⌈2n/3⌉} and its complement, with an additional extremal graph when n≡2 mod 3. Previous work only gave asymptotic bounds (Terpai) or large-n proofs (Liu). That is a real closed problem, and the finite-n proof is a genuine contribution.\n\nWhat the paper does well: the reduction to staircase matrices via Lemma 2.1 is the right structural framework; the upper bound ϕ(A) obtained from Csikvári's row-sum bound is used cleverly; the case analysis is detailed, and the last remaining case (n=3k+2, c=c̄=2k+1) is handled by a concrete 6×6 matrix argument. The chain of inequalities in Sections 6–7 is intricate but internally consistent as far as I checked. The paper also recovers Nikiforov's conjecture as a corollary. The citations to the authors' own earlier work are to published theorems, so I do not see a circularity problem.\n\nThe main soft spot is the status of Lemma 2.1. As stated, it says every extremal graph has a vertex ordering with adjacency matrix in S*_s(n), but Remark 2.2 only asserts that Csikvári's proof shows this, without giving the precise theorem or the argument. If the actual Csikvári result is only that some extremal graph lies in the staircase class, then the paper's claim that every extremal graph is complete split (or its complement) does not follow from the present argument. The conjecture itself can still be recovered: apply the whole chain to that extremal representative and the maximum value is the complete split value. So this is a significant but patchable gap: the authors should pin down the exact statement and prove the universal direction, or soften the classification claim. A couple of lemmas (3.4, 3.5) are sketched with 'similar to' earlier proofs, which slows independent verification. I did not find a decisive error elsewhere.\n\nWho it is for: spectral graph theorists, especially people working on Nordhaus–Gaddum problems or extremal spectral bounds. It deserves a serious referee; I would send it to review, with the request that the authors clarify Lemma 2.1 and expand the sketched parts.","headline":"Settles a 2007 Nordhaus-Gaddum conjecture for all n; the main argument holds up, but Lemma 2.1's universality is asserted rather than proved.","tokens_in":21991,"tokens_out":6015,"would_cite":true,"duration_ms":62115,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A18"],"pacs":[],"model":"deepseek-v4-flash","headline":"Complete split graphs maximize the spectral radius of a graph plus its complement, for every order.","keywords":["nonnegative matrices","spectral radius","spectral bounds","Nordhaus-Gaddum type problem","complete split graph","graph complement","extremal graph","adjacency matrix"],"falsifier":"For a fixed small $n$, exhaustively compute $\\rho(G)+\\rho(\\bar G)$ over all unlabeled graphs of that order and check that the maximum agrees with the right-hand side of (4.3) and is attained only by the named complete split graphs; a single counterexample would refute the claim. Alternatively, in the exceptional case $(n,c,\\bar c)=(3k+2,2k+1,2k+1)$, evaluate the spectral radius of the explicit $6\\times 6$ matrix $M$ in Section 7: if it ever reaches $\\rho_0=4k+1$, the exclusion argument fails.","tokens_in":20976,"feed_emoji":"📊","tokens_out":11559,"duration_ms":104823,"temperature":0.7,"pith_summary":"The paper claims to settle a 2007 conjecture about the Nordhaus–Gaddum type behavior of the spectral radius. For every order $n$, the quantity $\\rho(G)+\\rho(\\bar G)$ is maximized by the complete split graph $K_{\\lfloor n/3\\rfloor}\\vee N_{\\lceil 2n/3\\rceil}$ and its complement, with a second extremizer when $n\\equiv 2\\pmod 3$. The proof works for all $n$ and uses only linear algebra, yielding the exact maximum in closed form. A reader should care because this closes a long-standing open problem and, as a corollary, confirms the conjectured bound $\\rho(G)+\\rho(\\bar G)\\le (4/3)n+O(1)$ with the explicit constant $1/3$.","feed_headline":"Complete split graphs maximize graph-plus-complement spectral radius","feed_subtitle":"A 2007 conjecture is proved for every n, using linear algebra alone and identifying all extremal graphs.","key_machinery":"The carrying object is the staircase class $S^*_s(n)$: symmetric zero-diagonal $0$-$1$ matrices whose $1$'s fill a staircase shape, with corner conditions $a_{12}=1$ and $a_{n-1,n}=0$. The proof begins with the structural lemma that every extremal graph has a vertex ordering whose adjacency matrix lies in this class. For such a matrix $A$, three integer parameters $c,v,s$ record where the staircase stops, and mirrored parameters $\\bar c,\\bar v,\\bar s$ are read from the reflected complement. A row-sum bound supplies the closed upper estimate $\\rho(A)\\le \\phi(A)$ in terms of $(c,v,s)$, and a sequence of local staircase moves shows that no candidate can beat the complete split form. The final comparison is reduced to a quartic polynomial $g(x)$ that is increasing on the relevant interval, with one exceptional parameter triple excluded by a rooted-matrix bound and the characteristic polynomial of an explicit $6\\times 6$ matrix.","core_discovery":"The paper's central claim is that the conjecture holds in full: among all simple graphs of order $n\\ge 3$, the sum $\\rho(G)+\\rho(\\bar G)$ is maximized by the complete split graph $K_{\\lfloor n/3\\rfloor}\\vee N_{\\lceil 2n/3\\rceil}$ and by its complement, and when $n\\equiv 2\\pmod 3$ also by $K_{\\lceil n/3\\rceil}\\vee N_{\\lfloor 2n/3\\rfloor}$ and its complement. A complete split graph is formed by joining a clique to an independent set with all possible edges, so its complement is a disjoint union of an independent set and a clique. The proof gives the exact maximum value in closed form as (4.3) and shows that the equality cases are exactly these graphs up to complementation. A direct corollary is the uniform bound $\\rho(G)+\\rho(\\bar G)\\le (4/3)n+1/3$.","pith_inferences":["The same staircase-and-parameter strategy could plausibly transfer to other Nordhaus–Gaddum sums of spectral invariants, such as Laplacian or signless Laplacian eigenvalues, if an analogue of the structural lemma holds; the paper does not pursue this.","The equality analysis suggests a stability statement: graphs whose spectral sum is within $\\varepsilon$ of the maximum should be close, in edge-edit distance, to the complete split extremizers. No such stability bound is proved here.","The explicit determinant computations in the exceptional case could be refined to extract a quantitative gap between subextremal graphs and the maximum, a testable extension of the same polynomial method."],"forward_implications":["The exact extremal value of $\\rho(G)+\\rho(\\bar G)$ is known for every $n$ through the closed formula (4.3), so the maximum no longer needs to be estimated asymptotically.","Every extremal graph is classified: it is the complete split graph $K_{\\lfloor n/3\\rfloor}\\vee N_{\\lceil 2n/3\\rceil}$, its complement, and additionally $K_{\\lceil n/3\\rceil}\\vee N_{\\lfloor 2n/3\\rfloor}$ or its complement when $n\\equiv 2\\pmod 3$.","The uniform bound $\\rho(G)+\\rho(\\bar G)\\le (4/3)n+1/3$ follows, verifying the previously conjectured $4n/3+O(1)$ form.","Because the proof is purely linear algebraic, it covers all $n$ uniformly and does not rely on analytic large-$n$ methods."],"supporting_citations":[{"why":"It supplies the structural lemma that every extremal graph has a staircase vertex ordering, which is the starting reduction of the proof.","marker":"[5]"},{"why":"It supplies the row-sum upper bound $\\phi_\\ell(A)$ used to define the main working bound $\\phi(A)$.","marker":"[6, 10]"},{"why":"It supplies the rooted-matrix comparison used to rule out the last exceptional parameter case.","marker":"[4]"},{"why":"It verified the optimal choice of $q$ within the restricted family of complete split graphs, making the conjectured extremizers concrete.","marker":"[1]"},{"why":"It is the 2007 research problem that states the conjecture resolved by this paper.","marker":"[13]"},{"why":"It posed the asymptotic bound $4n/3+O(1)$ for this spectral sum, which the paper verifies in explicit form.","marker":"[12]"},{"why":"It gave an analytic proof of that asymptotic bound, the previous best result of this type.","marker":"[14]"},{"why":"It proved the conjecture for large $n$ by analytic methods, and this paper removes the largeness restriction.","marker":"[11]"}],"fun_headline_variants":["Split graphs maximize graph-plus-complement spectral radius","Spectral radius sum max achieved by complete split graphs","2007 conjecture on spectral radii of graphs and complements proved","Complete split graphs win spectral radius sum conjecture","Nordhaus-Gaddum for spectral radii: split graphs extremal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof depends on the structural lemma that every extremal graph, after relabeling, has its adjacency matrix in the staircase class; if some extremal graph lacked such an ordering, the whole reduction would only cover a subclass of candidates.","fun_headline_variants_meta":{"raw":{"variants":["Split graphs maximize graph-plus-complement spectral radius","Spectral radius sum max achieved by complete split graphs","2007 conjecture on spectral radii of graphs and complements proved","Complete split graphs win spectral radius sum conjecture","Nordhaus-Gaddum for spectral radii: split graphs extremal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2725,"prompt_tokens":772,"completion_tokens":1953,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":388,"completion_tokens_details":{"reasoning_tokens":1876}},"tokens_in":388,"tokens_out":1953,"duration_ms":16917,"temperature":1.0,"reasoning_tokens":1876,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:09:03.487375+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed small $n$, exhaustively compute $\\rho(G)+\\rho(\\bar G)$ over all unlabeled graphs of that order and check that the maximum agrees with the right-hand side of (4.3) and is attained only by the named complete split graphs; a single counterexample would refute the claim. Alternatively, in the exceptional case $(n,c,\\bar c)=(3k+2,2k+1,2k+1)$, evaluate the spectral radius of the explicit $6\\times 6$ matrix $M$ in Section 7: if it ever reaches $\\rho_0=4k+1$, the exclusion argument fails.","supporting_citations":[{"cited_title":"Csikv´ ari, On a conjecture of V","cited_arxiv_id":null,"evidence_quote":"It supplies the structural lemma that every extremal graph has a staircase vertex ordering, which is the starting reduction of the proof."},{"cited_title":"Cheng and C.-w","cited_arxiv_id":null,"evidence_quote":"It supplies the rooted-matrix comparison used to rule out the last exceptional parameter case."},{"cited_title":"Aouchiche, F","cited_arxiv_id":null,"evidence_quote":"It verified the optimal choice of $q$ within the restricted family of complete split graphs, making the conjectured extremizers concrete."},{"cited_title":"Stevanovi´ c, Research problems from the Aveiro workshop on graph spectra,Linear Algebra Appl., 423 (2007), 172–181","cited_arxiv_id":null,"evidence_quote":"It is the 2007 research problem that states the conjecture resolved by this paper."},{"cited_title":"Nikiforov, Eigenvalue problems of Nordhaus-Gaddum type,Discrete Math., 307 (2007), 774–780","cited_arxiv_id":null,"evidence_quote":"It posed the asymptotic bound $4n/3+O(1)$ for this spectral sum, which the paper verifies in explicit form."},{"cited_title":"Terpai, Proof of a conjecture of V","cited_arxiv_id":null,"evidence_quote":"It gave an analytic proof of that asymptotic bound, the previous best result of this type."},{"cited_title":"Liu, Graph limits and spectral extremal problems for graphs,SIAM J","cited_arxiv_id":null,"evidence_quote":"It proved the conjecture for large $n$ by analytic methods, and this paper removes the largeness restriction."}],"review_version":1}