{"id":"8824a11f-a1d0-401b-8c68-27ceaf62afef","arxiv_id":"2508.12034","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For r>=3, k>=1 and sufficiently large n, the unique spectral extremal graph among non-r-partite B_{r,k}-free graphs is Y_r(n), obtained from the Turán graph T_r(n) by one internal edge and some cross-edge deletions.","lead":"The paper proves that among large non-r-partite graphs that avoid the generalized book B_{r,k}, the graph with the largest spectral radius is always the same candidate Y_r(n), built from the r-partite Turán graph by adding one edge inside a part and deleting a few cross edges. This settles the spectral version of a problem the authors had posed for the edge count, for all r>=3 and k>=1.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the reader's Lemma 3.11 gap does not land because the unique-internal-edge scenario is not present inside Claim 2.","rationale":"The reader's weakest assumption is that in Lemma 3.11 Claim 2, the graph G-w may become r-partite when w is the partner of the unique internal edge uv. This reading is inconsistent with the proof state: Claim 2 is proved under the supposition sum_i e(V_i) >= 2, so u has at least two neighbors in V_1 and there is no unique internal edge. Deleting any one neighbor of u leaves another internal edge, so G-w is non-r-partite for every admissible w. The unique-edge regime only starts after Lemma 3.11, where Claim 2 is not invoked. In the later 'analogous' step of Lemma 3.12, the chosen vertices are common neighbors of u and v, so v is adjacent to the shifted vertex and cannot be the missing neighbor. The other candidate missing vertices are not u or v, so uv remains after deletion. The paper's terse assertions that modified graphs remain B_{r,k}-free are not fully written out, but they are supported by the partition argument: after the unique internal edge uv is fixed, any B_{r,k} in a modified graph must contain uv; if a shifted leaf or clique vertex lies in a part V_i, it forces adjacency to a K_r vertex in the same part, which is impossible because V_i is independent for i >= 2 and V_1 has only the single internal edge uv. For Lemma 3.7's shift, replacing a leaf u by z works because the new neighbors of u are contained in N(z). I therefore do not find a load-bearing concern, and the reader's conditional appears to be based on a misreading of the proof context.","tokens_in":21348,"tokens_out":52748,"duration_ms":568030,"concrete_test":"Re-derive Lemma 3.11 Claim 2 under the stated hypothesis sum_i e(V_i) >= 2: verify that for every w in (union_{i != s} V_i) \\ N_G(u_s), either w lies outside V_1, or w = u is impossible because u is adjacent to u_s, or w in V_1 \\ {u} still leaves an internal edge u-u' with u' != w; hence G-w is non-r-partite and Lemma 3.7 yields x_w >= 1 - sqrt(epsilon)n/rho. Separately check that the analogous Claim 4 in Lemma 3.12 uses u_s adjacent to both u and v, so the only potentially problematic vertex v is never the missing neighbor. If both checks pass, the reader's conditional should be lifted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing gap in the central claim. The reader's concern about Lemma 3.11 Claim 2 misplaces the unique-internal-edge setting. Inside Claim 2, the proof assumes sum_i e(V_i) >= 2 and L = {u}, so d_{V_1}(u) >= 2 and every internal edge is incident to u. For w outside N_G(u_s): if w lies in V_j with j >= 2, the internal edge uv survives deletion of w; if w lies in V_1, then w != u because u is adjacent to u_s, and deleting any w in V_1 \\ {u} still leaves at least one internal edge u-u' with u' != w, since deg_{V_1}(u) >= 2. Hence G-w is non-r-partite in all cases and Lemma 3.7 applies. The genuinely unique-edge situation arises only after Lemma 3.11 is proved, and Claim 2 is not used there. The later analogous argument in Lemma 3.12 Claim 4 selects u_s adjacent to both u and v, so v is never a missing neighbor; for any other w, uv survives deletion. The repeated 'B-free' assertions after local edge shifts are terse, but each can be justified from the partition: any B_{r,k} would have to contain the unique internal edge uv, and a K_r containing a shifted leaf would force two vertices from the same independent part to be adjacent, which is impossible. Thus the proof, while condensed, does not exhibit a load-bearing defect.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the spectral Turán problem for non-r-partite graphs avoiding the generalized book graph B_{r,k} = K_r ∨ kK_1, with r ≥ 3 and k ≥ 1. The main result, Theorem 1.5, asserts that for sufficiently large n, the unique n-vertex non-r-partite B_{r,k}-free graph maximizing the spectral radius is Y_r(n), obtained from the Turán graph T_r(n) by adding one edge inside a part and deleting a set of cross edges so that the endpoints of the new edge have no common neighbor in one of the other parts. The proof uses the spectral stability lemma of Nikiforov and Wang–Kang–Xue, Perron–Frobenius theory, Rayleigh quotient comparisons, and a sequence of local structural lemmas (Lemmas 3.1–3.12), culminating in a comparison with a graph from Li and Peng's Lemma 2.8. The paper also discusses connections to the relationship between spectral extremal and edge-extremal graphs and poses several problems.","tokens_in":21558,"tokens_out":38331,"duration_ms":409557,"significance":"If correct, Theorem 1.5 is a natural and nontrivial extension of recent results by Li–Peng (B_{r,1}), Liu–Miao (B_{2,k}), and Lin–Ning–Wu (B_{2,1}), and it partially resolves Problem 2 of Yu–Li for generalized book graphs. The extremal graph Y_r(n) is explicitly described and the claimed extremal value is concrete and falsifiable. The paper uses standard and appropriate tools: spectral stability, Perron-Frobenius bounds, equitable partitions, and Rayleigh quotient edge-shifts. A particular strength is that the proof attempts a full characterization, including uniqueness, rather than only a spectral bound. However, the written proof contains a load-bearing gap: several local edge-shift operations are asserted to preserve B_{r,k}-freeness without proof, and this assertion is not immediate and is used essentially in Claim 2 of Lemma 3.11 and again in Lemma 3.12 and the final step of Theorem 1.5.","major_comments":[{"comment":"The sentence 'Clearly, G' is non-r-partite and B_{r,k}-free' is the load-bearing step of the claim, but the B_{r,k}-freeness assertion is not proved. The non-r-partite part is correct: G' - u_s = G - u_s, and G - u_s is non-r-partite because d_{V_1}(u) ≥ 2. However, adding all missing edges from u_s to the other parts can complete a new copy of B_{r,k}. For instance, if the missing neighbor w is an internal neighbor of u, then the new edge u_s w, together with the internal edge u w, one vertex from each other part except one, and k vertices in the skipped part, can form a B_{r,k} that was not present in G. The fact that G is B_{r,k}-free does not rule this out, because the edge u_s w was absent in G. This step is essential: Claim 2 is used to derive d_{V_s}(u) ≤ k-1 in Claim 3, and hence the contradiction d(u) ≤ r(k-1) with Lemma 3.9. Please supply a complete proof that this shift preserves B_{r,k}-freeness, or replace it with a shift whose B-freeness can be verified.","section":"Lemma 3.11, Claim 2"},{"comment":"The same unproved B_{r,k}-freeness appears in the operations that add an edge vw (Claim 5) or move an edge from u to v (the final 's = 1' step). These operations are used to establish the degree bounds (3.5)-(3.10) and the conclusion that d_{V_2}(u) = 1, which in turn gives the subgraph relation G ⊆ K^1_{|V_1|,...,|V_r|}. Since a new copy of B_{r,k} in the shifted graph would invalidate the contradiction, the proof is not self-contained at these points. The authors should state and prove a general lemma that, under the hypotheses of the respective claims, the local operations used in Claim 2 of Lemma 3.11, Claim 4 and Claim 5 of Lemma 3.12, and the final edge-move all preserve B_{r,k}-freeness.","section":"Lemma 3.12, Claims 4 and 5, and final proof of Theorem 1.5"}],"minor_comments":[{"comment":"The specific concern that G-w might be r-partite when w is the partner of a unique internal edge does not land inside Claim 2: there the hypothesis is sum_i e(V_i) ≥ 2 and L = {u}, so deleting any vertex w ≠ u leaves an internal edge and G-w is non-r-partite. The unique-edge situation arises only later, in Lemma 3.12, where the chosen vertices u_s are adjacent to both u and v. It would help to state this explicitly in the proof.","section":"Lemma 3.11, Claim 2"},{"comment":"After constructing G'', the displayed Rayleigh quotient inequality uses ρ(G') instead of ρ(G''); this is a typo and should be corrected.","section":"Lemma 3.12, Case 2"},{"comment":"The quotient matrix B is displayed without stating the ordering of the six blocks; for reproducibility, please specify the ordering (e.g., {v}, {u}, {w}, V_1\\{v}, V_2\\{u,w}, V_3).","section":"Lemma 3.2"},{"comment":"The assertion that the shifted graph G' − {uv : v ∈ N_G(u)} + {uw : w ∈ N_G(z)\\L} is B_{r,k}-free also deserves a one-line justification; in this case it can be proved by replacing u by z in any new copy, since u's new neighbors are a subset of N_G(z)\\L.","section":"Lemma 3.7"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the overall strategy is standard, but the written proof has a genuine gap: the preservation of B_{r,k}-freeness under the local edge shifts is asserted rather than proved, and this is a load-bearing point. The reviewer's specific objection about the partner of the unique internal edge is not the actual issue; the actual issue is the unproved 'Clearly B-free' statements. I would recommend major revision rather than rejection, because the gap may be repairable within the scope of the paper. The authors also mention an independent derivation by B. Wang's team; if the editor wishes, the authors should clarify the extent of the overlap with that unpublished work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe main theorem is what it claims: for r>=3, k>=1 and n large, Y_r(n) is the unique spectral extremal graph among non-r-partite B_{r,k}-free graphs. This genuinely extends Li-Peng (k=1) and Liu-Miao (r=2), and it answers the open case from your earlier edge-count paper [38]. I read the proof and did not find a load-bearing gap.\n\nThe reader's objection to Lemma 3.11, Claim 2 does not hold up. In that lemma we are in the regime where the total number of internal edges is at least 2 and L = {u}, so all internal edges are incident to u and d_{V1}(u) >= 2. For any w in the non-neighborhood of u_s, either w is outside V_1, in which case the internal edge u-u' survives, or w is in V_1\\{u}, and because u has at least two neighbors in V_1, one internal edge still survives. So G-w is indeed non-r-partite and Lemma 3.7 applies. The unique-internal-edge situation the reader worries about belongs to the later part of the proof, after Lemma 3.11 is settled, and not inside Claim 2.\n\nThat said, the paper is not easy to referee. The stability argument is standard, but several B_{r,k}-freeness assertions after local edge shifts are stated without proof. Each one I checked can be justified from the partition structure, but the authors should spell these out. There are also small notation slips, like using G' when G'' is meant in Lemma 3.12. These are presentation issues, not mathematical ones.\n\nThe math looks sound. The characteristic polynomial computations in Lemma 3.2 are ugly but check out; the local structure lemmas line up with the final equality case. The acknowledgment of the independent result from Wang's group is honest and doesn't change the novelty assessment.\n\nWho will use this: researchers working on spectral Turán-type problems, especially the non-r-partite variant. It is a solid completion of a known program. I would cite it and would send it to a serious referee.","headline":"Theorem is new and likely correct; the reported gap in Lemma 3.11 dissolves on inspection, though the paper is dense.","tokens_in":22194,"tokens_out":4309,"would_cite":true,"duration_ms":43521,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"For large $n$, the unique spectral extremal among non-$r$-partite $B_{r,k}$-free graphs is $Y_r(n)$, the Turán graph with one extra internal edge and deleted cross edges.","keywords":["Non-r-partite graph","Generalized book graph","Spectral radius","Extremal graph","Spectral Turán-type problem","Color-critical graph","Spectral stability","Rayleigh quotient"],"falsifier":"Take $r=3$, $k=1$ and a moderately large $n$ (say $n=30$), compute the Perron vector of the candidate $Y_3(n)$, and check the Rayleigh-quotient inequality in Lemma 3.11 for a neighbour $u_s$ of the internal edge whose non-neighbour $w$ is the other endpoint $v$ of that edge: if deleting $v$ makes the graph 3-partite, the claimed positive gain $2x_{u_s}(x_w-x_u)/x^{\\top}x$ cannot be justified, exposing the missing case. A full exhaustive search over all non-3-partite $B_{3,1}$-free graphs at small $n$ would then show whether any graph with two internal edges actually beats $Y_3(n)$ in spectral radius.","tokens_in":21051,"feed_emoji":"📈","tokens_out":13284,"duration_ms":123351,"temperature":0.7,"pith_summary":"The paper aims to prove that for fixed $r\\ge 3$ and $k\\ge 1$, and sufficiently large $n$, the generalized book graph $B_{r,k}$ (a $K_r$ joined to an independent set of size $k$) has a unique spectral extremal graph among all $n$-vertex non-$r$-partite $B_{r,k}$-free graphs: the graph $Y_r(n)$. $Y_r(n)$ is obtained from the $r$-partite Turán graph $T_r(n)$ by adding one edge inside a part and deleting a set of cross edges so that the two endpoints of the new edge have no common neighbour in the part they both touch. This matters because it completes the spectral Turán problem for this family of color-critical forbidden graphs, where the extremal graph is no longer the Turán graph itself but a nearly Turán graph. The proof combines spectral stability, Perron-vector perturbations, and a quotient-matrix computation, and it partially resolves the open problem raised in [38].","feed_headline":"Unique spectral extremal for book-free non-r-partite graphs found","feed_subtitle":"Adding one inner edge to the Turán graph and deleting selected cross edges gives the unique winner.","key_machinery":"The central object is the candidate graph $Y_r(n)$, a one-edge perturbation of the Turán graph, and the argument is carried by three mechanisms working together. The spectral stability lemma places any extremal graph within $O(\\varepsilon n^2)$ edges of $T_r(n)$. The Perron-vector edge-switch inequality shows that moving an edge from a vertex with smaller Perron coordinate to a vertex with larger coordinate strictly increases the spectral radius, and repeated use of this switch pins down the local structure. The local-structure lemmas use Rayleigh quotients and the characteristic equation of the quotient matrix (the averaged block matrix for an equitable partition) for $Y_r(n)$ to force the unique internal edge, the universality of its neighbours, and the final no-common-neighbour condition.","core_discovery":"Theorem 1.5 states that if $r\\ge 3$, $k\\ge 1$, and $n$ is sufficiently large, then every non-$r$-partite $B_{r,k}$-free graph $G$ of order $n$ satisfies $\\rho(G)\\le \\rho(Y_r(n))$, with equality if and only if $G$ is isomorphic to $Y_r(n)$. The extremal graph $Y_r(n)$ is the unique non-$r$-partite spectral extremal: it is the Turán graph $T_r(n)$ with one edge $uv$ added inside one part and $\\lfloor n/r\\rfloor-1$ cross edges deleted from $u$ to another part plus one cross edge deleted from $v$ to that part, arranged so that $u$ and $v$ have no common neighbour in that part. The proof shows that any extremal graph must be close to $T_r(n)$, then forces all internal edges to shrink to a single edge $uv$, forces every other vertex to be adjacent to all vertices outside its own part, and finally uses the no-common-neighbour condition to identify the graph as $Y_r(n)$.","pith_inferences":["The 'one internal edge plus deleted cross edges' template may be the extremal pattern for every color-critical forbidden graph $H$ whose edge extremal graph is $T_r(n)$ plus $O(1)$ edges, since the structural forcing in the proof uses only color-criticality and the absence of the book.","An exhaustive spectral-radius search over all non-3-partite $B_{3,1}$-free graphs with small $n$ (say 20 to 40) could determine how large 'sufficiently large' must be in Theorem 1.5, and would test the sharpness of the $Y_3(n)$ construction.","If the same stability-and-local-structure argument is applied to other color-critical $H$, it may yield a general principle: the non-$r$-partite spectral extremal is obtained from the Turán graph by adding a single edge in a part whose endpoints have no common neighbour in the part where cross edges are deleted."],"forward_implications":["For every $r\\ge 3$, $k\\ge 1$, and sufficiently large $n$, the set $\\mathrm{SPEX}_{r+1}(n,B_{r,k})$ contains exactly one graph, namely $Y_r(n)$.","Because $Y_r(n)$ is also the edge-extremal graph found in [38], the inclusion $\\mathrm{SPEX}_{r+1}(n,B_{r,k})\\subseteq \\mathrm{EX}_{r+1}(n,B_{r,k})$ holds for generalized book graphs, adding evidence for the general containment problem.","The explicit lower bound $\\rho(Y_3(n))>\\frac{2}{3}n-\\frac{7}{12}$ for $r=3$, together with the $r\\ge 4$ analogue, gives a concrete spectral threshold that any non-$r$-partite $B_{r,k}$-free graph must exceed to be extremal.","The result resolves the spectral version (Problem 2 of [38]) for the whole family $B_{r,k}$ with $r\\ge 3$ and $k\\ge 1$, complementing the book case $r=2$ handled in [20]."],"supporting_citations":[{"why":"Supplies the edge-extremal baseline: $T_r(n)$ is the unique $K_{r+1}$-free graph maximizing edges.","marker":"[34]"},{"why":"Establishes the spectral analogue of Turán's theorem for color-critical $H$, giving $T_r(n)$ as the unique $H$-free spectral extremal.","marker":"[24]"},{"why":"Provides the spectral stability lemma (Lemma 2.1) showing every near-extremal graph is $O(\\varepsilon n^2)$ edges away from $T_r(n)$.","marker":"[35]"},{"why":"Supplies the edge-switch inequality (Lemma 2.6) used to increase spectral radius by moving edges toward larger Perron coordinates.","marker":"[37]"},{"why":"Provides Lemma 2.8, the comparison that bounds any graph of the $Y$-type by $\\rho(Y_r(n))$, and settles the $r\\ge 3$, $k=1$ case.","marker":"[17]"},{"why":"Settles the book case $r=2$, $k\\ge 2$, the closest predecessor that this paper extends to $r\\ge 3$.","marker":"[20]"},{"why":"The authors' earlier work that determined the exact Turán number for $B_{r,k}$ and posed the open problem whose spectral version is answered here.","marker":"[38]"}],"fun_headline_variants":["Spectral extremal for book-free non-r-partite graphs is unique","Unique winner in spectral Turan for non-r-partite book-free","Single graph maximizes spectral radius for book-free non-r-partite","Unique spectral extremal for generalized book-free graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing step in the local-structure proof assumes that deleting any vertex outside the neighbourhood of a chosen neighbour $u_s$ leaves the graph non-$r$-partite; this can fail when the deleted vertex is the other endpoint of the unique internal edge, because then the remaining graph becomes $r$-partite and the Perron-vector lower-bound lemma cannot be applied.","fun_headline_variants_meta":{"raw":{"variants":["Spectral extremal for book-free non-r-partite graphs is unique","Unique winner in spectral Turan for non-r-partite book-free","Single graph maximizes spectral radius for book-free non-r-partite","Unique spectral extremal for generalized book-free graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001552,"raw_usage":{"total_tokens":6353,"prompt_tokens":1241,"completion_tokens":5112,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":857,"completion_tokens_details":{"reasoning_tokens":5041}},"tokens_in":857,"tokens_out":5112,"duration_ms":40584,"temperature":1.0,"reasoning_tokens":5041,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:26:30.332064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $r=3$, $k=1$ and a moderately large $n$ (say $n=30$), compute the Perron vector of the candidate $Y_3(n)$, and check the Rayleigh-quotient inequality in Lemma 3.11 for a neighbour $u_s$ of the internal edge whose non-neighbour $w$ is the other endpoint $v$ of that edge: if deleting $v$ makes the graph 3-partite, the claimed positive gain $2x_{u_s}(x_w-x_u)/x^{\\top}x$ cannot be justified, exposing the missing case. A full exhaustive search over all non-3-partite $B_{3,1}$-free graphs at small $n$ would then show whether any graph with two internal edges actually beats $Y_3(n)$ in spectral radius.","supporting_citations":[{"cited_title":"Tur´ an, On an extremal problem in graph theory, Mat","cited_arxiv_id":null,"evidence_quote":"Supplies the edge-extremal baseline: $T_r(n)$ is the unique $K_{r+1}$-free graph maximizing edges."},{"cited_title":"Nikiforov, Spectral saturation: inverting the spectral Tur´ an theorem","cited_arxiv_id":null,"evidence_quote":"Establishes the spectral analogue of Turán's theorem for color-critical $H$, giving $T_r(n)$ as the unique $H$-free spectral extremal."},{"cited_title":"Wang, L.Y","cited_arxiv_id":null,"evidence_quote":"Provides the spectral stability lemma (Lemma 2.1) showing every near-extremal graph is $O(\\varepsilon n^2)$ edges away from $T_r(n)$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the edge-switch inequality (Lemma 2.6) used to increase spectral radius by moving edges toward larger Perron coordinates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Lemma 2.8, the comparison that bounds any graph of the $Y$-type by $\\rho(Y_r(n))$, and settles the $r\\ge 3$, $k=1$ case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Settles the book case $r=2$, $k\\ge 2$, the closest predecessor that this paper extends to $r\\ge 3$."},{"cited_title":"The exact Tur\\'an number of generalized book graph $B_{r,k}$ in non-$r$-partite graphs","cited_arxiv_id":"2508.07533","evidence_quote":"The authors' earlier work that determined the exact Turán number for $B_{r,k}$ and posed the open problem whose spectral version is answered here."}],"review_version":1}