pith. sign in

arxiv: 2604.10719 · v1 · submitted 2026-04-12 · 🧮 math.CO

Black-white polynomials of graphs and generating functions

Kenneth Goodenough , Paul E. Gunnells This is my paper

Pith reviewed 2026-05-10 15:59 UTC · model grok-4.3

classification 🧮 math.CO
keywords black-white polynomialsgraph coloringsgenerating functionsmatrix modelsloop numberexponential generating functionsquantum entanglementcombinatorics
0
0 comments X

The pith

Black-white polynomials of graphs admit rational generating functions for certain families and exponential generating functions via a matrix model for all graphs and a Wright generalization for fixed loop number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops generating function techniques to compute the black-white polynomial W_G(t) of a graph G, which counts two-colorings of vertices with black and white while tracking white vertices that have an even number of black neighbors. For some families X of graphs, the authors establish constructions that produce a rational generating function. They introduce a matrix model that yields the exponential generating function summing W_G(t) over all graphs, and they extend Wright's earlier construction to obtain exponential generating functions for the subclass of graphs with a prescribed loop number. These methods matter because the polynomials encode entanglement features of quantum states associated to graphs, turning enumeration into a tool for systematic study of infinite families rather than isolated cases.

Core claim

The black-white polynomial W_G(t) enumerates two-colorings of the vertices of G, with the exponent of t recording white vertices of even black degree. Constructions exist under which certain families X of graphs produce a rational generating function in the variable that marks the graphs. A matrix model yields the exponential generating function that sums W_G(t) over all graphs. Wright's construction is generalized to produce exponential generating functions that sum W_G(t) over graphs of any fixed loop number.

What carries the argument

The matrix model that assembles the exponential generating function for black-white polynomials over all graphs, together with the rationality constructions for specified families and the Wright-style extension for fixed loop number.

If this is right

  • Rational generating functions supply closed-form expressions for the black-white polynomials of the corresponding infinite graph families.
  • The matrix model supplies a uniform exponential series whose coefficients recover W_G(t) for every individual graph.
  • The generalized Wright construction classifies the polynomials according to loop number and yields a separate exponential series for each fixed value.
  • These generating functions convert the study of entanglement properties in graph states into a combinatorial enumeration problem over infinite classes rather than single graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same matrix-model technique might adapt to other two-variable graph polynomials that arise in statistical mechanics or quantum information.
  • One could verify the model by extracting low-order coefficients and comparing them to exhaustive enumeration on all graphs with a small number of edges.
  • The rationality constructions may extend to additional natural families such as trees, planar graphs, or graphs of bounded degree.

Load-bearing premise

The matrix model and the described constructions correctly enumerate the colorings counted by the black-white polynomials for the stated families and loop numbers.

What would settle it

Compute W_G(t) directly for a small graph belonging to one of the families claimed to have a rational generating function and check whether its coefficients match those obtained by expanding the purported rational function.

Figures

Figures reproduced from arXiv: 2604.10719 by Kenneth Goodenough, Paul E. Gunnells.

Figure 1
Figure 1. Figure 1: Examples of G-cylinders and subdivisions Sn(G, e). 2.2. We now define some families of graphs. In each case, we fix a graph G and indicate the set Gn. (GC) The G-cylinder of length n is the product G × Pn. We let Gn = {G × Pn}. (GX) More generally let iH : H → G be the inclusion of H as a subgraph. Then the length n extrusion of G along H is the quotient of Xn(G, H) = G a(H × Pn), where we identify iH(H) ⊂… view at source ↗
Figure 2
Figure 2. Figure 2: The back and front of a state. Proof. We consider each family in turn, beginning with the G-cylinders (GC). Thus each set Gn consists of the single graph G × Pn, n ≥ 1. Let S be the set of all G-cylinders of length 2 equipped with all possible col￾orings, and similarly let S˜ be the set of G-cylinders of length 3 equipped with all possible colorings. Thus |S | = 4|G| and |S˜| = 8|G| . Each S˜ ∈ S˜ determin… view at source ↗
Figure 3
Figure 3. Figure 3: The matrix A and the vector v0 for the path graph family. expression (14) is of the same type as those in Theorem 2.5, so is a rational function in x. This completes the proof of the theorem. 2.7. Example. We illustrate the theorem by giving the matrix A and the vector v0 for the path graph family Gn = Pn. This is the case of the G-cylinder (GC) with G an isolated vertex. The set S consists of the four dif… view at source ↗
Figure 4
Figure 4. Figure 4: Some flowers [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Gluing flowers into a graph G with profile n = (0, 1, 2, 1, 0, . . .). We have |n| = 1 · 2 + 2 · 3 + 1 · 4 = 12. The graph has Aut G ≃ Z/2Z × Z/2Z, coming from flipping the two loops. The corresponding term in the sum log [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: An example depicting a possible pairing of a black flower E4 and a white flower F6. The formal measure [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A loop number g = 2 example: reducing a graph H ∈ Γ(2) to G ∈ Γ≥3. Finally, the loop number 1 case is exceptional. A connected graph G with loop number 1 consists of a unique k-cycle Ck and with rooted trees attached to its vertices. One can show that this leads to the expression (28) A1(x) = 1 2 X k≥1 L k k = 1 2 log 1 1 − L  . Thus all the series Ag can be built in a simple way from L . 4.4. Our goal i… view at source ↗
Figure 8
Figure 8. Figure 8: Trees giving the initial vector (30). The roots are circled. Here we use cosh x = (e x+e −x )/2 since it is the even part of the exponential function. • To make a tree in T − w , again we make the new root white, attach trees arbitrarily from T + w and T − w , but we now must attach an odd number of trees from Tb. This time the polynomial of the new tree does not get multiplied by t (because the new root i… view at source ↗
Figure 9
Figure 9. Figure 9: The graphs in Γ≥3(2). and let XG(x) ∈ Q[t][[x]] be the result. Then we have Wg(x) = X G∈Γ≥3(g) XG(x). We compute a few terms of the series W2(x) to illustrate the result. In this case Γ≥3(2) consists of the three graphs G1, G2, G3 shown in [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
read the original abstract

Let G be a graph. The black-white polynomial W_G(t) enumerates colorings of the vertices of G with two colors (black and white), where the power of t keeps track of how many white vertices have an even number of black neighbors. Such polynomials appear in quantum information theory, where they are used to capture properties of the entanglement in certain quantum states described by graphs. In this paper we describe how to use generating functions to compute these polynomials for various families X of graphs. Our main results are the following: (i) we describe some constructions under which X leads to a rational generating function; (ii) we use a matrix model to construct the exponential generating function of the black-white polynomials of all graphs; and (iii) we generalize a construction of Wright to build exponential generating functions of black-white polynomials for graphs of a given loop number.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 4 minor

Summary. The paper defines the black-white polynomial W_G(t) of a graph G, which enumerates 2-colorings of the vertices (black and white) with the exponent of t tracking the number of white vertices having an even number of black neighbors. It presents three main results: constructions under which certain families X of graphs yield rational generating functions for their black-white polynomials; a matrix model that produces the exponential generating function summing W_G(t) over all graphs; and a generalization of Wright's construction that yields exponential generating functions for the black-white polynomials of graphs with a fixed loop number. These are motivated by applications in quantum information theory for graph states.

Significance. If the constructions hold, the work supplies explicit enumerative tools for black-white polynomials via generating functions, including rational forms for specific families, a matrix-based EGF over all graphs, and a generalized Wright EGF for fixed loop number. These are strengths because they are direct constructions rather than parameter-fitted or self-referential, enabling systematic computation for infinite classes of graphs. The approach aligns with standard combinatorial enumeration techniques and could facilitate further study of these invariants.

major comments (1)
  1. The matrix model section: the construction of the exponential generating function via matrices requires an explicit statement of the matrix entries (or operators) and the extraction mechanism (e.g., trace, permanent, or determinant) that sums W_G(t) over all graphs; without this or a small-graph verification (such as for K_1 or P_2), it is difficult to confirm the model reproduces the claimed EGF.
minor comments (4)
  1. Introduction: the definition of W_G(t) should be given as a formal sum or equation immediately after the verbal description, for precision.
  2. The abstract refers to 'some constructions' for rational generating functions; the introduction or §2 should explicitly list the families X to which they apply.
  3. The generalization of Wright's construction would benefit from a brief recall of the original Wright result (with citation) before stating the extension.
  4. Include at least one or two computed examples of W_G(t) for small graphs (e.g., cycles or complete graphs) to illustrate the polynomial and the generating-function claims.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation of our work and the constructive comment, which will help improve the clarity of the matrix model section. We address the point below and will incorporate the suggested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: The matrix model section: the construction of the exponential generating function via matrices requires an explicit statement of the matrix entries (or operators) and the extraction mechanism (e.g., trace, permanent, or determinant) that sums W_G(t) over all graphs; without this or a small-graph verification (such as for K_1 or P_2), it is difficult to confirm the model reproduces the claimed EGF.

    Authors: We agree that greater explicitness in this section will strengthen the presentation. In the revised manuscript we will add a precise definition of the matrix entries (including their dependence on the graph structure, the variable t, and the black-white coloring rules), together with a clear statement of the extraction operator that yields the exponential generating function summing W_G(t) over all graphs. We will also include direct verification for the smallest graphs K_1 and P_2, computing both the explicit black-white polynomials and the corresponding low-order terms of the EGF to confirm agreement with the model. revision: yes

Circularity Check

0 steps flagged

No significant circularity; constructions are direct and self-contained

full rationale

The paper defines the black-white polynomial W_G(t) from first principles as a vertex 2-coloring enumerator tracking even black-neighbor parity on white vertices. It then presents explicit constructions yielding rational generating functions for specified graph families, a matrix model that directly assembles the EGF over all graphs, and a generalization of Wright's construction for fixed loop number. None of these steps reduce a claimed prediction or uniqueness result to a fitted parameter, self-definition, or load-bearing self-citation; each is an enumerative construction whose validity rests on the combinatorial definition rather than on prior outputs of the same paper. The derivation chain is therefore independent of its own results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on standard combinatorial definitions of graphs, colorings, and generating functions; no free parameters, ad-hoc axioms, or new entities are mentioned in the abstract.

axioms (1)
  • standard math Standard definitions of graphs, vertex colorings, and ordinary/exponential generating functions from enumerative combinatorics
    The black-white polynomial and all generating-function constructions presuppose these background notions.

pith-pipeline@v0.9.0 · 5437 in / 1168 out tokens · 54712 ms · 2026-05-10T15:59:30.022568+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Mohsen Bahramgiri and Salman Beigi, An efficient algorithm to recognize locally equivalent graphs in non-binary case , arXiv preprint cs/0702057 (2007)

    work page arXiv 2007

  2. [2]

    1, 19–26

    Hans J Briegel, David E Browne, W olfgang D¨ ur, Robert Raus sendorf, and Maarten Van den Nest, Measurement-based quantum computation, Nature Physics 5 (2009), no. 1, 19–26

    work page 2009

  3. [3]

    3, 030313

    ChunJun Cao, Michael J Gullans, Brad Lackey, and Zitao W an g, Quantum lego expansion pack: Enumerators from tensor networks , PRX Quantum 5 (2024), no. 3, 030313

    work page 2024

  4. [4]

    Reidel Publishing Co., Dordrecht, 1974, The art of finite and infinite expansions

    Louis Comtet, Advanced combinatorics, enlarged ed., D. Reidel Publishing Co., Dordrecht, 1974, The art of finite and infinite expansions. MR 460128

    work page 1974

  5. [5]

    7, 1351–1367

    Lars Eirik Danielsen and Matthew G Parker, On the classification of all self-dual additive codes over gf (4) of length up to 12 , Journal of Combinatorial Theory, Series A 113 (2006), no. 7, 1351–1367. BLACK-WHITE GRAPHS 27

    work page 2006

  6. [6]

    Gunnells, Hypergraph matrix models , Mosc

    Mario Defranco and Paul E. Gunnells, Hypergraph matrix models , Mosc. Math. J. 21 (2021), no. 4, 737–766. MR 4322910

    work page 2021

  7. [7]

    Boris Dubrovin, Di Yang, and Don Zagier, Classical Hurwitz numbers and related combina- torics, Mosc. Math. J. 17 (2017), no. 4, 601–633. MR 3734655

    work page 2017

  8. [8]

    Christopher Eltschka and Jens Siewert, Maximum n-body correlations do not in general imply genuine multipartite entanglement , Quantum 4 (2020), 229

    work page 2020

  9. [9]

    Etingof, Mathematical ideas and notions of quantum field theory , available from www-math.mit.edu/∼ etingof/, 2002

    P. Etingof, Mathematical ideas and notions of quantum field theory , available from www-math.mit.edu/∼ etingof/, 2002

    work page 2002

  10. [10]

    MR 2483235

    Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235

    work page 2009

  11. [11]

    Knuth, Tomasz /suppress Luczak, and Boris Pittel, The birth of the giant component, Random Structures Algorithms 4 (1993), no

    Svante Janson, Donald E. Knuth, Tomasz /suppress Luczak, and Boris Pittel, The birth of the giant component, Random Structures Algorithms 4 (1993), no. 3, 231–358, With an introduction by the editors. MR 1220220

    work page 1993

  12. [12]

    Quantum Inform ation Processing-From Theory to Experiment 199 (2006), 137–158

    Richard Jozsa, An introduction to measurement based quantum computation , NATO Science Series, III: Computer and Systems Sciences. Quantum Inform ation Processing-From Theory to Experiment 199 (2006), 137–158

    work page 2006

  13. [13]

    33, 335303

    Daniel Miller, Daniel Loss, Ivano Tavernelli, Hermann K ampermann, Dagmar Bruß, and Nikolai Wyderka, Shor–laflamme distributions of graph states and noise robus tness of entan- glement, Journal of Physics A: Mathematical and Theoretical 56 (2023), no. 33, 335303

    work page 2023

  14. [14]

    Stanley, Enumerative combinatorics

    Richard P. Stanley, Enumerative combinatorics. Vol. 1 , Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambrid ge, 1997, With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. MR 1442260

    work page 1997

  15. [15]

    Gunnells, Tim Coopmans, and Jordi Tura, Sec- tor length distributions of recursively definable graph sta tes through analytic combinatorics , preprint, 2026

    Elo ¨ ıc Vall´ ee, Kenneth Goodenough, Paul E. Gunnells, Tim Coopmans, and Jordi Tura, Sec- tor length distributions of recursively definable graph sta tes through analytic combinatorics , preprint, 2026

    work page 2026

  16. [16]

    E. M. W right, The number of connected sparsely edged graphs , J. Graph Theory 1 (1977), no. 4, 317–330. MR 463026 Naturwissenschaftlich-Technische F akult¨at, Universit ¨at Siegen, W alter-Flex-Straße 3, 57068 Siegen, Germany Department of Mathematics and Statistics, University of Mas sachusetts Amherst, Amherst, MA 01003, USA

    work page 1977