{"id":"206b3211-a273-403a-9969-de7e9120d0ad","arxiv_id":"2505.08539","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For connected signed graphs, the negative inertia index is always at least ceil(g/2)-1, and all extremal graphs are classified.","lead":"A signed graph is a graph whose edges carry plus or minus signs, and its negative inertia index counts the negative eigenvalues of its adjacency matrix. This paper proves that this index is always at least roughly half the girth, and identifies every graph for which the bound is tight.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower bound is sound; the equality characterization hinges on an unproved classification lemma (Lemma 2.6) in the girth-3/4 case, so the paper's strongest claim is conditional on that external result.","rationale":"The reader's conditional verdict identifies the reliance on cited lemmas and unverified case checks. I agree that the external classification Lemma 2.6 is the most load-bearing dependency for the equality characterization in Theorem 3.1, and that the later theorems contain case checks that are asserted rather than fully demonstrated. I do not share equal concern about Lemma 2.4: those cycle and path inertia formulas are standard, easily verified directly, and the paper's use of them is consistent. The central inequality itself is well supported by interlacing and pendant-vertex arguments, and I found no internal inconsistency that would falsify the main bound. However, because the paper's advertised extremal characterization depends on a non-reproved classification and on several summarized 'simple operation' calculations, the conditional verdict is appropriate. A small exhaustive enumeration would directly test the critical girth-3/4 i_-=1 classification and would either expose a missing family or substantially de-risk the equality theorem.","tokens_in":16684,"tokens_out":25906,"duration_ms":253862,"concrete_test":"Enumerate all connected signed graphs on n <= 8 vertices with girth 3 or 4, up to switching equivalence, by generating underlying graphs and signings with nauty; compute i_- by exact diagonalization; then verify that i_- = 1 occurs exactly for (K_{n1,n2}, +) when girth is 4 and for complete multipartite graphs with only unbalanced triangles when girth is 3. Any counterexample would show that Theorem 3.1 condition (2) is incomplete; if none appears, the external classification is corroborated for all small cases relevant to the equality proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main inequality i_-(Gamma) >= ceil(g/2)-1 is solid: a shortest cycle is induced, Lemma 2.3 gives interlacing, and Lemma 2.4 provides the cycle values. The risk is in the equality half of Theorem 3.1. After Lemma 2.8, the non-cycle equality case forces g=3 or 4 and i_-(Gamma)=1, and the proof concludes by invoking Lemma 2.6, a classification of all signed graphs with negative inertia index 1 that is cited from [4] and not re-derived here. Theorem 3.1 condition (2) is exactly the connected specialization of that classification. If Lemma 2.6 has any overlooked connected exception with girth 3 or 4, the equality characterization is incomplete. The same external dependence propagates into Corollary 2.1 and Theorems 3.3 and 3.4, which also rely on several 'simple operation' inertia checks summarized without full derivations. One such check, in Theorem 3.4 Case 1 Subcase 2, contains a sign-counting sentence that is not literally consistent: after saying there is exactly one negative edge among the three outside edges, it calls the resulting 6-cycle balanced. A parity argument can repair the claim, but the printed proof is not self-contained at that point. Thus the lower bound is robust, while the extremal characterization is only as secure as Lemma 2.6 and the unexpanded case checks.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the relation between the girth g of a connected signed graph Gamma and its negative inertia index i_-(Gamma). It proves the lower bound i_-(Gamma) >= ceil(g/2) - 1, characterizes the equality cases in Theorem 3.1 as signed cycles of certain balance classes and as positive complete bipartite or complete multipartite signed graphs with only unbalanced triangles, and then gives classifications of connected signed graphs with i_-(Gamma) = ceil(g/2) for g >= 4, separating canonical signed unicyclic graphs from non-canonical ones. The same framework is applied to the positive inertia index by negation, and the paper concludes with characterizations of connected signed graphs with given nullity and given girth.","tokens_in":16934,"tokens_out":38608,"duration_ms":358520,"significance":"If the results are correct, the paper provides a natural signed analogue of known unsigned girth-inertia bounds and a useful extremal classification. The proof of the lower bound is clean and elegant: it uses interlacing (Lemma 2.3), the signed-cycle inertia formulas (Lemma 2.4), and the pendant-vertex reduction (Lemma 2.5). The paper also makes a reasonable structural split between canonical unicyclic graphs and the general case. However, the classification half rests on many unexpanded case checks and on an external classification lemma (Lemma 2.6 from [4]), so the extremal characterizations are currently under-verified even though they are plausible. No machine-checked proofs or reproducible code are supplied; verification depends entirely on the printed arguments and cited references.","major_comments":[{"comment":"The exclusion of the g = 6 unbalanced case is not self-contained. After stating that there is exactly one negative edge among x1y1, x1x2, and x2y2, the proof asserts that {x1,x2,y1,y2,y3,y4} induces a balanced 6-cycle, but it does not specify the vertex order of that cycle or compute its sign product. Because this assertion is what rules out the subcase, the parity computation must be written out explicitly; with the natural cycle x1-x2-y2-y3-y4-y1-x1, the sign product is -sigma(x1x2)sigma(x2y2)sigma(y1x1), which is indeed positive when exactly one of the three outside edges is negative, but the printed text leaves this to the reader.","section":"Theorem 3.4, Subcase 2"},{"comment":"Several crucial exclusions are asserted via 'by a simple operation' or 'by a simple observation' without displaying the relevant induced subgraphs or the inertia computations. For example, in the proof of Theorem 3.3, Case 1, the claim that a vertex x in N1(v,C5) can only be adjacent to y5, and the consequent lower bound i_-(Gamma[V(Gamma1) union {x}]) = 4, are not demonstrated. Similarly, in Theorem 3.4, Claim 2, the bound l <= floor(g/4) and the derived cycle bound are not justified. These steps are load-bearing for the classifications for g = 5 and g = 6; the authors should provide a table of the induced subgraphs with their inertia indices, or give full derivations for these claims.","section":"Theorem 3.3, Case 1 and Theorem 3.4, Claims 1-3"},{"comment":"The equality condition 'Gamma ~ (K^sigma_{n1,n2,...,nl}, +)' is ambiguous: the superscript sigma on K and the trailing '+', which in the paper's notation means the all-positive signature, are contradictory. The intended family is almost certainly the all-positive complete multipartite graph (K_{n1,...,nl}, +), with l = 2 allowed for girth 4 and l >= 3 for girth 3. The statement should specify the signature and the range of l explicitly; as printed, the theorem cannot be verified without guesswork.","section":"Theorem 4.1(2)"},{"comment":"The sentence 'Unfortunately, there exists no signed graphs satisfying these conditions' asserts a nonexistence result with no proof. This nonexistence is used to justify the case split that leads to Theorems 5.2 and 5.3. The claim should either be proved directly, or derived explicitly by intersecting the equality cases of Theorems 3.1 and 3.4 with those of Theorems 4.1 and 4.3. As written, the 'if and only if' characterizations in Section 5 are not fully justified.","section":"Section 5, first paragraph"}],"minor_comments":[{"comment":"The definition of a pendant star is hard to reconcile with the definition of a canonical signed unicyclic graph; the text should say explicitly that the center of the star is a cycle vertex and that the parameters l_i in Theorem 3.2 count the internal vertices of the cycle segments after removing the centers of the pendant stars.","section":"Section 3, definition of pendant star"},{"comment":"There are numerous typographical and grammatical errors, including 'it's girth', 'Denoted by g', 'a balance 6-cycle', and 'It suffice'; these should be corrected throughout.","section":"Global"},{"comment":"The graphs B(4,3,4), B(4,4,4), H_i, and Gamma_i are only described in figures; please add explicit adjacency or sign descriptions in the text or an appendix so that the 'simple operation' checks can be reproduced without interpreting the drawings.","section":"Figures 3-5"},{"comment":"The positive-inertia theorems are stated without proofs; a short paragraph explaining that they follow from the negation operation, including the modular-four parity changes, would significantly improve verifiability.","section":"Theorems 4.1-4.3"},{"comment":"The phrase 'exactly one path between any two major vertices of V(C_g) has even order' should be rephrased as 'among the k cycle segments between consecutive major vertices, exactly one has even order', to avoid the ambiguity caused by the two paths that exist between any two vertices on a cycle.","section":"Theorem 3.2(2)-(3)"},{"comment":"The typeset statement of Lemma 2.6 appears to be missing the switching-equivalence symbol; please check the PDF rendering so that the statement is unambiguous.","section":"Lemma 2.6"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the lower-bound part of the paper is sound and publishable. My main reservation is the volume of unstated verification in the classification theorems; I recommend asking the authors to expand the case checks or move them to an appendix with explicit inertia computations. The paper also leans heavily on the authors' own previous work [4,5]; this is not disqualifying, but the novelty relative to the unsigned case in [5] should be stated more explicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result here is real: for a connected signed graph with girth g, the inequality i_-(Γ) ≥ ceil(g/2) - 1, with the balanced/unbalanced cycle distinction baked in, is a genuine extension of the simple-graph result. The proof is pleasingly short: take a shortest cycle, use interlacing on it as an induced subgraph, invoke the known inertia formulas for signed cycles, and handle pendant vertices by the deletion lemma. That part is solid, and the extremal families in Theorem 3.1(1) and (2) are plausible and nicely signed-specific.\n\nWhat the paper does well is organize the whole program: lower bound, equality, next level i_- = ceil(g/2), and then the positive-inertia and nullity consequences. The signed case genuinely changes the congruence classes compared to ordinary graphs, and the paper is honest about where the inertia formulas come from.\n\nThe soft spots are all in the equality half. The girth 3 and 4 cases in Theorem 3.1 reduce directly to Lemma 2.6, which is a classification of i_- = 1 signed graphs quoted from the authors' own earlier paper and not re-derived. If that lemma has any connected exception with a 3- or 4-cycle, the characterization collapses. That is a real dependency, not a style complaint. The later theorems lean even harder on \"by a simple operation\" checks and on families defined only in figures. One specific spot: in Theorem 3.4, Subcase 2, after saying exactly one of three edges is negative, the text calls the induced 6-cycle balanced. That sentence does not parse as written; a parity argument could repair it, but the printed proof is not self-contained there. There is also an ambiguous notation in Theorem 4.1(2), where the sign function appears both in the abstract family and as a positive signature.\n\nNone of this threatens the main inequality. The lower bound is proved from standard inputs and is robust. The extremal classification, especially for g = 3, 4, is only as secure as Lemma 2.6 and the unexpanded case checks.\n\nI would send this to a serious referee. The right referee time is spent verifying the case analyses and asking the authors to either prove Lemma 2.6 or clearly state it as an external classification result with a full statement. The paper is for spectral graph theorists working on signed graphs and inertia; they will want the main inequality, and they should be able to trust it. I'd cite the lower bound myself.","headline":"The signed-graph lower bound on negative inertia in terms of girth is clean and correct; the equality characterizations are more conditional than the paper admits, leaning on an external classification and several unexpanded case checks.","tokens_in":17531,"tokens_out":1878,"would_cite":true,"duration_ms":19509,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every connected signed graph, the negative inertia index is at least half the girth minus one, and the paper classifies every graph that attains this bound.","keywords":["signed graphs","inertia indices","negative inertia index","positive inertia index","nullity","girth","complete multipartite signed graphs"],"falsifier":"Take a balanced $5$-cycle and attach one leaf to a cycle vertex. Lemma 2.5 together with Lemma 2.4 predicts negative inertia index $\\lfloor 4/2\\rfloor + 1 = 3$, which exceeds the Theorem 3.1 lower bound of $2$ for girth $5$. Directly diagonalizing the adjacency matrix of this six-vertex signed graph either confirms $3$, supporting the equality classification, or returns $2$, which would falsify it.","tokens_in":16415,"feed_emoji":"📐","tokens_out":7906,"duration_ms":74676,"temperature":0.7,"pith_summary":"For any connected signed graph whose shortest cycle has length $g$, the paper proves that the number of negative eigenvalues of the adjacency matrix is at least $\\lceil g/2\\rceil - 1$. It then lists exactly which signed graphs achieve this lower bound: signed cycles of certain balance types determined by $g \\bmod 4$, positive complete bipartite graphs, and signed complete multipartite graphs whose signed triangles are all unbalanced. The paper also classifies the next level, $i_-(\\Gamma) = \\lceil g/2\\rceil$ for $g \\ge 4$, and uses sign reversal to obtain matching statements for the positive inertia index and for the nullity. The upshot is that a signed graph's shortest cycle forces a minimal amount of negative spectral content, and the extremal graphs are rigid enough to be enumerated.","feed_headline":"Girth forces a floor on signed graphs' negative eigenvalue count","feed_subtitle":"The bound is sharp, and the extremal graphs are exactly signed cycles of prescribed type and complete multipartite graphs.","key_machinery":"The argument turns on three tools. Lemma 2.4 supplies explicit formulas for the negative inertia index of a signed cycle and path in terms of length modulo $4$ and whether the cycle is balanced; Lemma 2.3 transfers that bound from a shortest cycle to the entire graph by interlacing; Lemma 2.5 says deleting a pendant vertex together with its neighbor lowers both inertia indices by exactly $1$, which forces any extra structure to contribute too many negative eigenvalues. For the equality cases, Lemma 2.6, the classification of signed graphs with $i_- = 1$, is what identifies the complete bipartite and complete multipartite graphs appearing in Theorem 3.1.","core_discovery":"The central result is Theorem 3.1: if $\\Gamma$ is connected, has at least one cycle, and $g$ is its girth, then $i_-(\\Gamma) \\ge \\lceil g/2\\rceil - 1$. Equality holds exactly when $\\Gamma$ is switching-equivalent to a signed cycle $C_g^{\\sigma}$ that is balanced for $g \\equiv 0,1 \\pmod 4$ or unbalanced for $g \\equiv 2,3 \\pmod 4$, or to a positive complete bipartite graph $(K_{n_1,n_2},+)$, or to a signed complete multipartite graph $K^{\\sigma}_{n_1,\\ldots,n_l}$ with $l \\ge 3$ whose signed triangles are all unbalanced. The proof restricts attention to a shortest cycle, uses interlacing to lift the cycle's negative-inertia bound to the whole graph, and then rules out extra vertices unless the graph is one of the listed multipartite forms. The same machinery, with the sign reversed, yields the analogous positive-inertia statements, and combining the two gives the nullity bound $\\eta(\\Gamma) \\le n - g + 2$ with equality characterized.","pith_inferences":["The mod-$4$ dependence of the equality cases mirrors the eigenvalue interlacing of cycles, so a natural test is whether the same lower bound survives for weighted signed graphs when the weighted cycle formulas obey the same congruence pattern.","The classification could serve as a fast certificate for minimal negative inertia: verify the girth and check the local extremal forms instead of computing the full spectrum.","A natural next step is to push the same two-step argument, shortest-cycle interlacing plus pendant-vertex deletion, to higher values of $i_-(\\Gamma)$, expecting finite extremal families for each fixed excess above the lower bound.","The nonexistence of signed graphs with the mixed inertia pair $(\\lceil g/2\\rceil - 1, \\lceil g/2\\rceil)$ noted in Section 5 may reflect a parity obstruction worth isolating for girth $3$ separately."],"forward_implications":["The lower bound is sharp for every girth: for each $g$ there are signed cycles and complete multipartite examples attaining $i_-(\\Gamma) = \\lceil g/2\\rceil - 1$.","For girth at least $4$, the paper enumerates all connected signed graphs with $i_-(\\Gamma) = \\lceil g/2\\rceil$, so the two smallest possible negative inertia values are completely understood.","Because negating all edge signs swaps positive and negative inertia, the identical classification holds for the positive inertia index $i_+(\\Gamma)$.","The nullity of a connected signed graph of order $n$ and girth $g$ is at most $n - g + 2$, and equality is characterized by balanced or unbalanced shortest cycles of certain lengths or by positive complete bipartite graphs.","The equality dichotomy, either a shortest cycle alone or a complete multipartite graph, shows that minimal negative inertia is a strong structural constraint."],"supporting_citations":[{"why":"Provides the formula for the negative inertia index of balanced and unbalanced signed cycles and paths used in Lemma 2.4.","marker":"[14]"},{"why":"Also supplies the signed-cycle and signed-path inertia formulas together with the pendant-vertex deletion rule used as Lemma 2.5.","marker":"[15]"},{"why":"One of the sources cited for the signed-cycle inertia formulas in Lemma 2.4.","marker":"[16]"},{"why":"Gives the interlacing theorem from which the induced-subgraph monotonicity of inertia indices in Lemma 2.3 follows.","marker":"[3]"},{"why":"Classifies signed graphs with $i_- = 1$ and triangle-free reduced signed graphs with $i_- = 2$, identifying the multipartite equality cases and the girth-$4$ family.","marker":"[4]"},{"why":"Provides the unsigned-graph counterpart whose method for girth-and-inertia classification is adapted to signed unicyclic graphs.","marker":"[5]"},{"why":"Supplies the switching lemma for unbalanced signed unicyclic graphs used to normalize signs on shortest cycles.","marker":"[7]"}],"fun_headline_variants":["Girth sets hard floor for signed negative inertia","Shortest cycle bounds negative eigenvalues in signed graphs","Negative inertia index can't dip below girth-based limit","Girth dictates negative inertia floor in signed graphs","Signed graph's negative eigenvalue count pinned by girth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole bound rests on the quoted formulas for the negative inertia index of signed cycles and paths in Lemma 2.4; if those congruence-dependent formulas were off by one in some residue class, the lower bound and every listed equality case would have to be reworked.","fun_headline_variants_meta":{"raw":{"variants":["Girth sets hard floor for signed negative inertia","Shortest cycle bounds negative eigenvalues in signed graphs","Negative inertia index can't dip below girth-based limit","Girth dictates negative inertia floor in signed graphs","Signed graph's negative eigenvalue count pinned by girth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000422,"raw_usage":{"total_tokens":2189,"prompt_tokens":986,"completion_tokens":1203,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":602,"completion_tokens_details":{"reasoning_tokens":1129}},"tokens_in":602,"tokens_out":1203,"duration_ms":10027,"temperature":1.0,"reasoning_tokens":1129,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:53:27.619137+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a balanced $5$-cycle and attach one leaf to a cycle vertex. Lemma 2.5 together with Lemma 2.4 predicts negative inertia index $\\lfloor 4/2\\rfloor + 1 = 3$, which exceeds the Theorem 3.1 lower bound of $2$ for girth $5$. Directly diagonalizing the adjacency matrix of this six-vertex signed graph either confirms $3$, supporting the equality classification, or returns $2$, which would falsify it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the formula for the negative inertia index of balanced and unbalanced signed cycles and paths used in Lemma 2.4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"One of the sources cited for the signed-cycle inertia formulas in Lemma 2.4."},{"cited_title":"Cvetkovi ´c, M","cited_arxiv_id":null,"evidence_quote":"Gives the interlacing theorem from which the induced-subgraph monotonicity of inertia indices in Lemma 2.3 follows."}],"review_version":1}