{"id":"9b93a267-b86c-4674-b8d5-76f4e373b788","arxiv_id":"2411.14238","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For 4k-intercyclic bipartite graphs, the permanental polynomial is the modified characteristic polynomial plus 4 times the sum of modified characteristic polynomials of all 4k-cycle deletions.","lead":"This paper proves a formula that computes the permanental polynomial of a class of bipartite graphs using easier characteristic polynomials of subgraphs. The formula extends earlier results to graphs where 4-cycles, 8-cycles, and longer cycles may overlap, and it avoids the Pfaffian orientation method.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"I reviewed the full proof line by line. Lemma 2.2 correctly computes f_i via the sign difference between characteristic and permanental coefficients; the congruence s+t+r ≡ i/2+s (mod 2) is valid, so only odd numbers of 4k-cycles survive with weight 2^{s+1}2^t. In a 4k-intercyclic graph only s=1 is possible, giving the factor 4. The bijection with Sachs subgraphs of G\\R is exact, and the replacement of π(G\\R) by φp(G\\R) follows from Lemma 2.2 without invoking Theorem 2.1, so the proof is not circular. I checked the formula on C4, C8, and K_{2,3} by direct enumeration and all coefficients matched. The reader's weakest assumption is indeed the definitional property that Sachs subgraphs contain at most one 4k-cycle; I agree that this is the load-bearing assumption and it holds. Therefore the ACCEPT verdict should stand unchanged.","tokens_in":7670,"tokens_out":39937,"duration_ms":336163,"concrete_test":"Verify the identity on a non-trivial graph by direct Sachs enumeration: for K_{2,3} (three C4s, no other cycles), Theorem 2.1 gives π = x^5 + 6x^3 + 12x; enumerate Sachs subgraphs to confirm b_2 = 6 and b_4 = 12, and check that the factor 4 arises from each C4 contributing 4φp(K1) = 4x. Repeat the enumeration on a graph containing a C4 and a C8 sharing vertices, where the sum over both cycles is active, and compare coefficient-by-coefficient.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find the central argument of Theorem 2.1 sound. The key step—that 4k-intercyclicity forces every Sachs subgraph to contain at most one 4k-cycle—is correct because components of a Sachs subgraph are vertex-disjoint, so two 4k-cycle components would be two vertex-disjoint 4k-cycles, contradicting the definition. The one-to-one correspondence between Sachs subgraphs of G containing R and Sachs subgraphs of G\\R is valid: G\\R is C4k-free by definition, and adding R back to any Sachs subgraph of G\\R gives a Sachs subgraph of G with R as its unique 4k-cycle. The final replacement of π(G\\R) by φp(G\\R) is justified by Lemma 2.2 (a C4k-free bipartite graph has f ≡ 0), not by the theorem itself, so there is no circularity. The only slightly compressed passage is the last sentence of the proof of Theorem 2.1, but the intended application to the 4k-intercyclic subgraph G\\R is legitimate. I could not construct a counterexample or locate an internally inconsistent step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript defines a modified characteristic polynomial φp(G,x) = Σ_{i even} (−1)^{i/2} a_i x^{n−i} for bipartite G and the difference polynomial f(G,x) = π(G,x) − φp(G,x). It then proves (Theorem 2.1) that if G is a 4k-intercyclic bipartite graph, i.e., one in which the deletion of the vertices of any 4k-cycle leaves a C4k-free graph, then π(G,x) = φp(G,x) + 4 Σ_{R∈C4k(G)} φp(G\\R,x). The proof uses the Sachs coefficient formulas (1.1), a lemma computing f_i in terms of Sachs subgraphs with an odd number of 4k-cycles, and a one-to-one correspondence between Sachs subgraphs of G containing a fixed cycle R and Sachs subgraphs of G\\R. The paper also reformulates the Zhang–Li Pfaffian-orientation theorem, derives Borowiecki's C4k-free characterization as a corollary, gives a worked example, and discusses applications to constructing cospectral/per-cospectral pairs.","tokens_in":7804,"tokens_out":39497,"duration_ms":351137,"significance":"If correct, Theorem 2.1 extends determinant-based computation of the permanental polynomial to a class of bipartite graphs that may contain K2,3 and hence lies outside the Pfaffian-orientation class of Zhang and Li; the example in Section 2 demonstrates this. The proof is elementary and self-contained: the coefficient computation in Lemma 2.2 is sound, the use of 4k-intercyclicity to guarantee that every Sachs subgraph contains at most one 4k-cycle is correct, and the bijection of Sachs subgraphs is valid because G\\R is C4k-free. The paper is honest about the complexity of listing 4k-cycles and does not overclaim the scope of the formula relative to prior work.","major_comments":[],"minor_comments":[{"comment":"The last sentence of the proof, 'the application of this expression to it leads to π(G\\R,x)=φp(G\\R,x)', creates an appearance of circularity because the expression is exactly the identity being proved. The intended argument is legitimate, but it should be stated directly: since G\\R is C4k-free, Lemma 2.2 gives f(G\\R,x)=0, and therefore π(G\\R,x)=φp(G\\R,x).","section":"Section 2, proof of Theorem 2.1"},{"comment":"The inference 'by Proposition 1.1, G is bipartite' is imprecise: Proposition 1.1 requires both a_k and b_k to vanish for odd k, whereas the argument establishes only b_k=0. The conclusion is nevertheless true because all Sachs contributions to b_k are positive, so b_k=0 for all odd k rules out odd cycles; please add a sentence making this explicit.","section":"Section 1, proof of Theorem 1.5"},{"comment":"The notation C4k(G) is overloaded because k is also the variable in '4k-intercyclic'. In the statement of Theorem 2.1, C4k(G) denotes the set of all cycles whose length is divisible by 4, not the set of cycles of one fixed length; please define this explicitly, for instance with a symbol such as C_{4Z}(G).","section":"Throughout, especially Theorem 2.1"},{"comment":"The claim that 'all cycles of length up to log n can be found in polynomial time using the color coding method' is not justified as written: the number of cycles of length O(log n) can be superpolynomial, and color-coding is typically a detection technique rather than an enumeration technique. Please qualify the statement, for example by using output-sensitive listing or by explicitly bounding the number of cycles.","section":"Section 2, complexity paragraph"},{"comment":"The sentence 'corresponding to p, we define a class of 4k-intercyclic bipartite graphs Gp = {G | f(G,x)=p}' is imprecise because f is defined for every bipartite graph, not only for 4k-intercyclic ones; the set-builder description should be restricted to 4k-intercyclic bipartite graphs.","section":"Section 2, definition of Gp"},{"comment":"Example 2.3 refers to Figure 1, but the figure is not reproduced in the arXiv text, so the reader cannot independently verify the listed cycles and subgraphs; the final version should include the figure or otherwise specify the graph.","section":"Section 2, Example 2.3"}],"recommendation":"minor_revision","confidential_remarks":"This is a solid research note: the main theorem is correct, the combinatorial proof is transparent, and the claimed class of graphs genuinely extends the setting in which the permanental polynomial can be expressed through modified characteristic polynomials. The issues I raise are local and do not affect the validity of Theorem 2.1; I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look. The paper proves Theorem 2.1: for a 4k-intercyclic bipartite graph G, π(G,x)=φp(G,x)+4Σ_{R∈C4k(G)} φp(G\\R,x). The class is defined by forbidding two vertex-disjoint cycles of lengths divisible by 4, equivalently deleting any 4k-cycle leaves a C4k-free graph. That is a real extension of Borowiecki's C4k-free result (π=φp), and it is incomparable with the Pfaffian-orientable class (no even subdivision of K2,3), so the formula covers graphs the orientation method cannot touch.\n\nWhat I like: the proof is elementary and transparent. It uses Sachs coefficient formulas, works out the contribution of Sachs subgraphs with an odd number of 4k-cycles, and the 4k-intercyclic condition forces at most one such cycle per Sachs subgraph. The one-to-one correspondence between Sachs subgraphs containing a fixed cycle R and Sachs subgraphs of G\\R is valid because G\\R is C4k-free. The final step, replacing π(G\\R) by φp(G\\R), is justified by Corollary 2.4 applied to the C4k-free graph G\\R, not by circular use of the theorem. I checked the parity identities in Lemma 2.2; they hold. The example in the paper verifies the formula on a graph containing K2,3, where the orientation theorems do not apply. No free parameters, no fitted constants.\n\nSoft spots are modest. The class is still restricted: 4k-intercyclic forbids two vertex-disjoint 4k-cycles, so it is a fairly thin slice of bipartite graphs. The computational gain is conditional—polynomial time only if the number of 4k-cycles or the largest cycle length is polynomially bounded. The application section (cospectral/per-cospectral pairs) is a minor observation: the equivalence holds for graphs with the same f(G,x), which is a bit tautological. Also, the paper is a research note; it does not attempt a structural characterization of the class, which might be the more interesting question.\n\nThe citation pattern is appropriate: Borowiecki, Yan–Zhang, Zhang–Li, and the Galluccio–Loebl connection are all relevant and correctly used. No citation inflation.\n\nBottom line: a clean, correct, modest result in algebraic graph theory. It deserves peer review and would be a fine contribution to a combinatorics journal. I would cite it if I work on permanental polynomials; for a general reading group, it is a maybe.","headline":"Solid combinatorial formula for permanental polynomial of 4k-intercyclic bipartite graphs; proof is checkable and the result is a genuine extension of the C4k-free case.","tokens_in":8409,"tokens_out":1835,"would_cite":true,"duration_ms":14732,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C31","05C50","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"The permanental polynomial of every 4k-intercyclic bipartite graph equals a modified characteristic polynomial plus four times the sum of modified characteristic polynomials of its 4k-cycle-deleted subgraphs.","keywords":["permanental polynomial","characteristic polynomial","modified characteristic polynomial","4k-intercyclic bipartite graph","C4k-free graph","Sachs subgraph","Pfaffian orientation","cospectral graphs"],"falsifier":"Enumerate all small 4k-intercyclic bipartite graphs, compute both sides of Theorem 2.1—the left side by direct permanent expansion and the right side from the characteristic polynomials of the cycle-deleted graphs—and compare coefficients. The first graph for which the coefficient of any $x^{n-i}$ differs would refute the theorem, and the paper's own worked example with three 4-cycles and two 8-cycles is the natural starting place.","tokens_in":7417,"feed_emoji":"🧮","tokens_out":10973,"duration_ms":106832,"temperature":0.7,"pith_summary":"This paper proves a formula that computes the permanental polynomial $\\pi(G,x)$ of a bipartite graph $G$ from determinant-style data, for every graph in which no two cycles whose lengths are multiples of four are vertex-disjoint. The formula is $\\pi(G,x)=\\varphi_p(G,x)+4\\sum_{R\\in C_{4k}(G)}\\varphi_p(G\\setminus R,x)$, where $\\varphi_p$ is the modified characteristic polynomial obtained from $\\det(xI-A(G))$ by changing the signs of selected coefficients. The proof counts Sachs subgraphs directly and does not use Pfaffian orientations, which apply only to a different class of bipartite graphs. For graphs with no cycle of length divisible by four, the sum is empty and the formula reduces to the known identity $\\pi(G,x)=\\varphi_p(G,x)$. The result matters because the permanental polynomial is a stronger graph invariant than the characteristic polynomial in practice, yet it is normally much harder to compute.","feed_headline":"A sum of determinants gives the permanental polynomial","feed_subtitle":"For bipartite graphs whose 4k-cycles are pairwise disjoint, the permanental polynomial follows from characteristic data.","key_machinery":"The load-bearing object is the modified characteristic polynomial $\\varphi_p(G,x)=\\sum_{i\\text{ even}}(-1)^{i/2}a_i x^{n-i}$, where $a_i$ are the coefficients of $\\phi(G,x)=\\det(xI-A(G))$. The mechanism that carries the argument is the Sachs coefficient expansion: the coefficients of $\\phi$ and $\\pi$ are signed and unsigned counts of Sachs subgraphs, so subtracting the appropriately signed characteristic coefficients cancels every Sachs subgraph containing an even number of cycles whose length is a multiple of four. The $4k$-intercyclic condition turns the surviving odd contribution into a sum over cycles, and the one-to-one correspondence between Sachs subgraphs containing a fixed cycle $R$ and Sachs subgraphs of $G\\setminus R$ converts that sum into $\\varphi_p(G\\setminus R)$; the factor $4$ is the factor $2^{s(U)+1}$ that appears when a Sachs subgraph contains exactly one $4k$-cycle.","core_discovery":"On the paper's own terms, the central discovery is a coefficient identity. For a bipartite graph, the difference $f(G,x)=\\pi(G,x)-\\varphi_p(G,x)$ expands over Sachs subgraphs—subgraphs whose components are edges or cycles—and only Sachs subgraphs containing an odd number of cycles of length divisible by four contribute. The $4k$-intercyclic hypothesis guarantees that every Sachs subgraph contains at most one such cycle, so the correction breaks into a sum over the cycles $R$ of $G$. Deleting a fixed $R$ sets up a one-to-one correspondence between Sachs subgraphs of $G$ containing $R$ and Sachs subgraphs of $G\\setminus R$, and because $G\\setminus R$ has no cycle of length divisible by four, its permanental polynomial is exactly its modified characteristic polynomial. The theorem $\\pi(G,x)=\\varphi_p(G,x)+4\\sum_{R\\in C_{4k}(G)}\\varphi_p(G\\setminus R,x)$ is the resulting identity.","pith_inferences":["Beyond the paper, the same cancellation argument should apply to the difference between a permanent-style and a determinant-style polynomial whenever every Sachs subgraph contains at most one cycle from a prescribed distinguished family; the coefficient $4$ is specific to cycles of length divisible by four in bipartite graphs.","The formula also suggests a hierarchy of corrections for graphs that violate the condition: Sachs subgraphs with three, five, or more distinguished cycles would generate further terms, as the odd-cardinality condition in Lemma 2.2 indicates.","The cost of the formula is dominated by listing $4k$-cycles, so the real algorithmic question opened by the paper is how quickly those cycles can be enumerated in large sparse graphs."],"forward_implications":["For every $4k$-intercyclic bipartite graph, the permanental polynomial can be written as a linear combination of modified characteristic polynomials, so the computation needs no Pfaffian orientation and no permanent evaluation.","Graphs with no cycles of length divisible by four satisfy the stronger equality $\\pi(G,x)=\\varphi_p(G,x)$, recovering the known characterization as the empty-sum case of the theorem.","If the graph has only polynomially many cycles, or only $4k$-cycles of length $O(\\log n)$, the formula gives a polynomial-time route to $\\pi(G,x)$ because those cycle lists can be generated efficiently.","The identity can be used to design families of $4k$-intercyclic bipartite graphs with a prescribed correction polynomial $f(G,x)$; inside each such family, two graphs are cospectral exactly when they are per-cospectral."],"supporting_citations":[{"why":"Supplies the characterization of C4k-free bipartite graphs by equality of the two polynomials, the base case that Theorem 2.1 extends.","marker":"[5]"},{"why":"Provides the unsigned Sachs-subgraph expansion of the permanental polynomial coefficients, used to define the coefficients $b_i$.","marker":"[14]"},{"why":"Provides the signed Sachs-subgraph expansion of the characteristic polynomial coefficients, used to define the coefficients $a_i$.","marker":"[16]"},{"why":"Gives the orientation method for permanental polynomials of bipartite graphs without even subdivisions of $K_{2,3}$, the prior approach the paper contrasts with.","marker":"[20]"},{"why":"Proves the converse orientation result, establishing the boundary of the Pfaffian method and motivating a different combinatorial route.","marker":"[21]"}],"fun_headline_variants":["A cycle sum turns characteristic into permanental","Permanental polynomial from modified characteristic sums","For 4k-intercyclic graphs, a compact permanental formula","Sachs subgraphs link permanental and characteristic polynomials"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof relies on the defining property that no two cycles of length divisible by four are vertex-disjoint; if a Sachs subgraph could contain two such cycles, the correction term $4\\sum_R\\varphi_p(G\\setminus R,x)$ would not count it correctly and the identity would collapse.","fun_headline_variants_meta":{"raw":{"variants":["A cycle sum turns characteristic into permanental","Permanental polynomial from modified characteristic sums","For 4k-intercyclic graphs, a compact permanental formula","Sachs subgraphs link permanental and characteristic polynomials"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1497,"prompt_tokens":904,"completion_tokens":593,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":531}},"tokens_in":520,"tokens_out":593,"duration_ms":6199,"temperature":1.0,"reasoning_tokens":531,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:24:39.230797+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all small 4k-intercyclic bipartite graphs, compute both sides of Theorem 2.1—the left side by direct permanent expansion and the right side from the characteristic polynomials of the cycle-deleted graphs—and compare coefficients. The first graph for which the coefficient of any $x^{n-i}$ differs would refute the theorem, and the paper's own worked example with three 4-cycles and two 8-cycles is the natural starting place.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the characterization of C4k-free bipartite graphs by equality of the two polynomials, the base case that Theorem 2.1 extends."},{"cited_title":"Rebman, and William Watkins, Permanental polynomials of graphs, Linear Algebra and Its Applications 38 (1981) 273–288","cited_arxiv_id":null,"evidence_quote":"Provides the unsigned Sachs-subgraph expansion of the permanental polynomial coefficients, used to define the coefficients $b_i$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the signed Sachs-subgraph expansion of the characteristic polynomial coefficients, used to define the coefficients $a_i$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the orientation method for permanental polynomials of bipartite graphs without even subdivisions of $K_{2,3}$, the prior approach the paper contrasts with."},{"cited_title":"Contact Information Ravindra B","cited_arxiv_id":null,"evidence_quote":"Proves the converse orientation result, establishing the boundary of the Pfaffian method and motivating a different combinatorial route."}],"review_version":1}