{"id":"763f8fe9-8125-43a0-9cc0-19da903a5a72","arxiv_id":"1908.11231","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The reciprocal of the independence polynomial is Horn hypergeometric if and only if the graph is chordal.","lead":"This paper proves that a graph's independence polynomial has a reciprocal whose power series is Horn hypergeometric exactly when the graph is chordal. It connects a classic graph class to special-function theory, with consequences for statistical mechanics and algebraic geometry.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"After independent review, the central claim of Theorem 1.2 is correct. The forward direction via perfect elimination orderings and Lagrange inversion is explicit and verifiable; Corollary 3.2 gives nonzero coefficients for s not in Z_{<=0} because a_j(m) >= m_j. The reverse direction reduces to an induced cycle and needs only the fact that the main diagonal coefficients of the C_n reciprocal tend in ratio to (2 cos(pi/2n))^{2n}. I checked the exact small-n cases (n=2: S(2,k)=binom(2k,k), ratio tending to 4; n=3: S(3,k)=(3k)!/(k!^3), ratio tending to 27), which match the stated kappa_n. The rationality obstruction for kappa_n via real cyclotomic conjugates is sound. The reader's concern about diagonal preservation is resolved by the definition: the ratio a_{(k+1,...,k+1)}/a_{(k,...,k)} is a product of n Horn ratios at shifted arguments, hence rational in k. Zero-specialization preservation is immediate because Horn ratios specialize as rational functions and nonzero coefficients remain nonzero. No step in the argument appears circular or dependent on an unjustified assumption.","tokens_in":13937,"tokens_out":51469,"duration_ms":440198,"concrete_test":"Compute S(4,k) for k up to 1000 using exact integer arithmetic and verify that c_{k+1}/c_k converges to (2 cos(pi/8))^8, approximately 135.88; if the limit differs or fails to exist, Proposition 5.3 collapses. A cheaper check is to confirm that the early ratios (14, 786/14, 61340/786, 5562130/61340) move toward this limit.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence is well-supported. The only potentially load-bearing external input is the de Bruijn asymptotic in Proposition 5.3, cited from [7] for the limiting ratio of the cycle diagonal coefficients c_k = S(n,k). This is a standard result and is consistent with exact small cases (n=2: S(2,k) = binom(2k,k), ratio tending to 4; n=3: S(3,k) = (3k)!/(k!^3), ratio tending to 27); the proof only needs that the limit is irrational for n >= 4, which the cyclotomic-degree argument establishes. The other flagged assumption, that Horn hypergeometricity passes to the main diagonal, follows directly from the definition: the diagonal ratio a_{(k+1,...,k+1)}/a_{(k,...,k)} is a product of n adjacent Horn ratios evaluated at shifted integer vectors, hence rational in k. Zero-specialization preservation is likewise immediate because Horn ratios specialize as rational functions and nonzero coefficients remain nonzero. No internal inconsistency or unproven critical step was found.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a characterization of chordal graphs in terms of Horn hypergeometricity of the reciprocal independence polynomial. Theorem 1.2 states that for a simple graph Γ the following are equivalent: (1) Γ is chordal; (2) the power series expansion of 1/I_Γ(x) is Horn hypergeometric; (3) the power series expansion of I_Γ(x)^{-s} is Horn hypergeometric for every s not in Z_{≤0}. The forward direction is proved via perfect elimination orderings and Lagrange inversion, using an upper-triangular Nahm system to obtain explicit binomial-type expansions. The reverse direction is proved by specializing to induced cycles and showing, from the explicit coefficient formula for I_{C_n}(x)^{-1}, that the main diagonal coefficients (the de Bruijn numbers) have limiting ratio κ_n = (2 cos(π/2n))^{2n}, which is irrational for n ≥ 4.","tokens_in":14119,"tokens_out":21589,"duration_ms":198798,"significance":"This is a clean and surprising bridge between combinatorial graph theory and the analytic theory of multivariate hypergeometric series. The proof is constructive in one direction and gives an explicit number-theoretic obstruction in the other. It is not circular and relies on standard external tools: Lagrange inversion, the perfect-elimination characterization of chordal graphs, and de Bruijn's asymptotic estimates. No parameters are fitted, and the non-chordal obstruction is concrete and falsifiable. If correct, the result gives a definitive characterization of chordality in terms of Horn hypergeometricity.","major_comments":[],"minor_comments":[{"comment":"The definition of a_j(m) contains a typo: it should be a_j(m) = sum_{i=1}^n a_{i,j} m_i, not sum_{i=1}^n a_{i,j} m_j. As written, the formula is inconsistent with the line-graph expansion in §3 and with the recursion in Proposition 2.1.","section":"§2, Eq. (6)"},{"comment":"Corollary 2.2 is false as stated. For n=2 and A = [[1,1],[0,1]], the corresponding D is 1/(1+x_1+x_2), whose denominator is not a product of powers of (1+x_i). Since this corollary is not used in the proof of the main theorem, the central result is unaffected, but the statement and its proof should be corrected or removed.","section":"§2, Corollary 2.2"},{"comment":"The reduction to the main diagonal should be made explicit. If the multivariate series is Horn, then the diagonal coefficients d_k = c_{(k,...,k)} are nonzero and d_{k+1}/d_k = product_{i=1}^n c_{(k,...,k)+e_i}/c_{(k,...,k)} is a rational function of k; this justifies the 'it is enough' claim in the proof.","section":"§5, Proposition 5.3"},{"comment":"The asymptotic ratio c_{k+1}/c_k → κ_n is quoted from [7] without a precise statement or page reference. Since this ratio is the crucial numerical input in the contradiction, it would help to state the exact asymptotic form of the de Bruijn numbers or give a precise pointer to the relevant result in [7].","section":"§5, Proposition 5.3"}],"recommendation":"minor_revision","confidential_remarks":"The false Corollary 2.2 and the implicit diagonal-preservation argument are the only substantive issues; both are local and do not affect the main theorem. With those fixed, the paper is suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Radchenko–Rodriguez Villegas prove that a graph is chordal iff the power series expansion of 1/I_Γ(x) is Horn hypergeometric (and iff I_Γ^{-s} is for all s not in nonpositive integers). This is genuinely new and not a routine consequence of prior work. The constructive direction uses perfect elimination orderings, the associated Nahm system, and multivariate Lagrange inversion to write the reciprocal as a hypergeometric-like series. The converse reduces to cycles and uses the fact that the diagonal coefficients of the cycle reciprocal are de Bruijn numbers; de Bruijn's asymptotics force the ratio to tend to κ_n = (2cos(π/2n))^{2n}, which is irrational for n≥4, while Horn hypergeometricity would make the ratio rational. The argument is sound.\n\nThe paper is well written. The use of Nahm systems to package the inversion is elegant, and the transfer-matrix computation of the cycle independence polynomial is a nice piece of reasoning. The authors credit Cartier–Foata for the positivity interpretation of coefficients and Carlitz for the expansion. No circularity, no fitted parameters. The citations look appropriate.\n\nSoft spots are minor. Proposition 2.1 leaves a computation to the reader; fine, it's elementary. The assumption that Horn hypergeometricity is preserved by taking the main diagonal is not explicitly stated in the proof of Prop 5.3, but it follows immediately from the definition, so not a real gap. Section 6 is a sketch of future work; that's clearly marked and doesn't affect the main theorem. The de Bruijn asymptotics is cited from [7] (de Bruijn's book) and the paper gives a short argument for why κ_n irrational for n≥4, so the load-bearing step is in good shape.\n\nI have no substantive objection. This deserves a serious referee and likely acceptance. It will be of interest to algebraic combinators, special functions people, and anyone working on independence polynomials. I'd bring it to a reading group.","headline":"A clean equivalence between chordal graphs and Horn hypergeometricity of the reciprocal independence polynomial; the proof is honest and the soft spots are minor.","tokens_in":14564,"tokens_out":1674,"would_cite":true,"duration_ms":14933,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C31","33C70","05C17","05A19"],"pacs":[],"model":"deepseek-v4-flash","headline":"For a simple graph, the reciprocal of its independence polynomial is a Horn hypergeometric series exactly when the graph is chordal.","keywords":["independence polynomial","chordal graph","Horn hypergeometric series","perfect elimination ordering","cycle graph","diagonal coefficients","Lagrange inversion"],"falsifier":"Enumerate all simple non-chordal graphs on up to six vertices, compute enough coefficients of 1/IΓ to test whether every ratio c_{m+e_i}/c_m is a rational function of the multi-index m, and look for a graph where all observed ratios are rational; a single such graph would refute the main theorem.","tokens_in":13771,"feed_emoji":"🔗","tokens_out":17164,"duration_ms":152782,"temperature":0.7,"pith_summary":"This paper establishes an exact equivalence between a classical graph-theoretic property and a classical analytic property of power series. For any simple graph Γ, the reciprocal of its independence polynomial, 1/IΓ(x), has a power series expansion whose successive coefficient ratios are rational functions of the exponents precisely when Γ is chordal, i.e., has no induced cycle of length four or more. The same holds for the power series expansion of IΓ(x)^{-s} for every s not a non-positive integer. If this is correct, chordality—a purely combinatorial notion—can be read off from the generating function of independent sets, and non-chordal graphs are exactly the ones for which this hypergeometricity fails. This connects the independence polynomial of statistical mechanics and the Lovász local lemma to the classical theory of hypergeometric series.","feed_headline":"Chordality equals hypergeometricity for reciprocal independence series","feed_subtitle":"The independent-set reciprocal is Horn hypergeometric exactly for chordal graphs, bridging combinatorics and analysis.","key_machinery":"The central object is the multivariate independence polynomial IΓ(x)=Σ_{I independent} ∏_{i∈I} x_i and its reciprocal power series. The argument is carried by three mechanisms: the commutation algebra [5] that interprets the coefficients of 1/IΓ(-x) as counts of monomial rearrangements; the association to a system of algebraic equations built from an upper-triangular matrix with 1s on the diagonal, which yields the coefficient formula via multivariate Lagrange inversion and shows that a perfect elimination ordering makes the ratios rational; and, for cycles, a 2×2 matrix product M whose trace is I_n(x) and whose discriminant equals $I_n^{2}$ - (-1)^n 4x_1...x_n, leading to the explicit coefficient formula S(n,k)=Σ_{j=-k}^{k} (-1)^j (2k choose k+j)^n on the diagonal and the limiting ratio κ_n=(2cos(π/2n))^{2n}. Horn hypergeometricity is the property that c_{m+e_i}/c_m is a rational function of m for each variable; the diagonal specialization of the cycle series shows this would force a rational limiting ratio, contradicting the irrational κ_n for n ≥ 4.","core_discovery":"The paper's central discovery is Theorem 1.2: for a simple graph Γ, the following are equivalent: (1) Γ is chordal; (2) the power series expansion of 1/IΓ(x) is Horn hypergeometric—meaning every ratio c_{m+e_i}/c_m of consecutive coefficients is a rational function of the multi-index m; (3) the expansion of IΓ(x)^{-s} is Horn hypergeometric for all s not a non-positive integer. The forward direction is proved via a perfect elimination ordering, which turns the reciprocal independence polynomial into the D-series of an upper-triangular system of algebraic equations whose coefficients are products of binomial coefficients. The reverse direction is proved by showing that any non-chordal graph contains an induced cycle C_n with n ≥ 4, and that the reciprocal series of the cycle independence polynomial is not Horn hypergeometric: its main diagonal coefficients, given explicitly as S(n,k) = Σ_{j=-k}^{k} (-1)^j (2k choose k+j)^n, have consecutive ratios tending to the irrational number (2cos(π/2n))^{2n}, whereas Horn hypergeometricity would force a rational limit. This yields the full equivalence and identifies the cycle reciprocals as the minimal non-hypergeometric obstructions.","pith_inferences":["Because Horn hypergeometricity implies every consecutive coefficient ratio is rational, a finite computation of ratios for a candidate graph could certify non-chordality if any ratio is non-rational, though no finite computation can certify chordality.","The irrational limiting ratio (2cos(π/2n))^{2n} for a minimal induced cycle might serve as a quantitative index of how far a non-chordal graph is from being chordal.","The appearance of classical varieties (Cayley cubic, Igusa quartic) as discriminants suggests a possible interpretation of chordality in terms of the geometry of the associated holomorphic map, a direction the paper leaves open.","One could test whether the Horn property fails already for the induced cycle of minimal length in a non-chordal graph, which would give a bound on the degree of the rational functions describing the coefficients."],"forward_implications":["A graph is chordal if and only if the reciprocal independence series is Horn hypergeometric, giving a generating-function characterization of chordality.","For chordal graphs, IΓ^{-s} has an explicit binomial-product expansion for every s not a non-positive integer, generalizing the classical expansion for complete graphs.","Cycle graphs C_n, n ≥ 4, are the minimal obstructions: their reciprocal series are never Horn hypergeometric, and the obstruction is already visible on the main diagonal through the limiting ratio (2cos(π/2n))^{2n}.","The cycle identity D^{-2} = I_n^2 - (-1)^n 4x_1...x_n leads to explicit rational formulas for the generating series of the coefficients, with Corollary 5.2 giving the full expansion of I_n^{-1}.","The discriminant varieties I_n^2 - (-1)^n 4x_1...x_n = 0 for small n are identified with classical algebraic varieties (the Cayley cubic for n=3 and the Igusa/Castelnuovo-Richmond quartic for n=4), connecting the theorem to algebraic geometry."],"supporting_citations":[{"why":"Supplies the asymptotic estimate for the diagonal coefficients of the cycle reciprocal, yielding the limiting ratio κ_n=(2cos(π/2n))^{2n}.","marker":"[7]"},{"why":"Establishes that a graph is chordal if and only if it has a perfect elimination ordering, which drives the forward direction.","marker":"[10]"},{"why":"Provides the multivariate Lagrange inversion formula used to express IΓ^{-s} as a binomial-coefficient series.","marker":"[16]"},{"why":"Earlier proof of the binomial identity for the cycle expansion, which the paper generalizes and recovers through its matrix product.","marker":"[4]"}],"fun_headline_variants":["Chordal graphs are the only ones with hypergeometric reciprocal independence series","Hypergeometric reciprocal independence series: exactly the chordal graphs","Chordality and hypergeometricity coincide for reciprocal independence series","Reciprocal independence series hypergeometric iff chordal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The non-chordal direction hinges on the asymptotic estimate that the consecutive diagonal coefficients of the cycle reciprocal tend to (2cos(π/2n))^{2n}; if that estimate were wrong, the irrationality obstruction would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Chordal graphs are the only ones with hypergeometric reciprocal independence series","Hypergeometric reciprocal independence series: exactly the chordal graphs","Chordality and hypergeometricity coincide for reciprocal independence series","Reciprocal independence series hypergeometric iff chordal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000675,"raw_usage":{"total_tokens":3018,"prompt_tokens":837,"completion_tokens":2181,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":453,"completion_tokens_details":{"reasoning_tokens":2109}},"tokens_in":453,"tokens_out":2181,"duration_ms":16371,"temperature":1.0,"reasoning_tokens":2109,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:20:46.471152+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all simple non-chordal graphs on up to six vertices, compute enough coefficients of 1/IΓ to test whether every ratio c_{m+e_i}/c_m is a rational function of the multi-index m, and look for a graph where all observed ratios are rational; a single such graph would refute the main theorem.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the asymptotic estimate for the diagonal coefficients of the cycle reciprocal, yielding the limiting ratio κ_n=(2cos(π/2n))^{2n}."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that a graph is chordal if and only if it has a perfect elimination ordering, which drives the forward direction."},{"cited_title":"Carlitz A binomial identity arising from a sorting problem , SIAM Rev","cited_arxiv_id":null,"evidence_quote":"Earlier proof of the binomial identity for the cycle expansion, which the paper generalizes and recovers through its matrix product."}],"review_version":1}