Edge-Span Chern Algebras of Graphical Configuration Spaces

This repository is the reference implementation for the edge-span algebra associated with a finite simple graph.

For a graph G and an ambient vector-space dimension n, define the graphical configuration space

$$\mathsf{Conf}_G(\mathbb P^{n-1}) = \left\{(\ell_v)_{v\in V(G)} \mid uv\in E(G) \Longrightarrow \ell_u\ne\ell_v\right\}.$$

Every edge e = uv has a span map

$$\phi_e:\mathsf{Conf}_G(\mathbb P^{n-1})\longrightarrow \mathsf{Gr}(2,n),\qquad (\ell_v)\longmapsto\langle\ell_u,\ell_v\rangle.$$

Pulling back the Chern classes of the tautological rank-two bundle gives

$$a_{uv}=h_u+h_v,\qquad b_{uv}=h_uh_v.$$

The resulting edge-span algebra is

$$A_G^{(n)} = \mathbb Q[a_{uv},b_{uv}\mid uv\in E(G)] \subseteq H^*(\mathsf{Conf}_G(\mathbb P^{n-1});\mathbb Q).$$

A graph homomorphism G -> H induces an algebra homomorphism A_G^(n) -> A_H^(n). Thus G |-> A_G^(n) is a covariant functor, and the abstract graded-algebra type of A_G^(n) is a graph invariant.

Headline computations

The repository currently reproduces the following finite calculations.

computation	result
five vertices, n = 3	23 Hilbert series and 33 abstract algebra types among 34 graphs
five vertices, n = 4	24 Hilbert series among 34 graphs
four vertices, n = 2, ..., 8	1, 9, 10, 10, 10, 10, 10 Hilbert types
chromatic, Tutte, H_3, H_4 on five vertices	23, 25, 23, 24 values
six-vertex trees, n = 3	one common Hilbert series; degree(Z_5) = 16, 18, 20, 22, 24, 30

Here

$$H_n(G)=\mathsf{Hilb}(A_G^{(n)}).$$

The commands below regenerate every computational result reported in the paper. The mathematical proofs in the paper do not depend on these finite checks.

Requirements

Core computations

• Python 3.10 or later
• no third-party Python packages

The full test suite and the pure-Python algebra calculations run immediately after cloning.

Full paper reproduction

• SageMath, available through the sage command
• Macaulay2, available through the M2 command

The reported calculations were run with:

Python 3.14.6
SageMath 10.9
Macaulay2 1.26.06

SageMath supplies an optional exact linear-algebra backend. Macaulay2 computes quotient Hilbert functions, minimal free resolutions, and power-zero schemes. If Macaulay2 is absent, Hilbert-only commands using --hilbert-backend auto fall back to exact Python arithmetic.

Clone And Test

git clone https://github.com/jacksonwalters/graph-functor.git
cd graph-functor
python3 -B -m unittest -v

The suite currently contains 56 tests. It checks, among other things:

• functoriality, identities, composition, and a noninjective fold P_3 -> K_2;
• S_r-equivariance and invariance under graph relabeling;
• the deletion-contraction cospan for K_3;
• agreement of the graphical model with the complete-graph J-model;
• agreement of the full DGA, direct h-sector, and structural Hilbert models;
• the closed tree Hilbert formula against 18 independently constructed algebras;
• tensor decomposition over connected components;
• recursive NBC generation and exact sparse linear algebra;
• canonical algebra presentations and intrinsic power-zero loci;
• completeness and internal consistency of the 34-graph classification certificate;
• the complete chromatic, Tutte, H_3, and H_4 comparison certificate.
• direct construction of the cubic tree invariant, agreement with the full algebra through five vertices, and equivariance under tree relabeling.

Tests requiring Macaulay2 are skipped automatically when M2 is unavailable.

For a first explicit algebra:

python3 -B graphical_configuration.py \
  --points 3 --ambient 3 --h-sector --show-algebra \
  'P3=12,23'

This prints a homogeneous basis and every nonzero product in A_(P_3)^(3).

Reproduce The Paper

Run all commands from the repository root. Keep regenerated artifacts separate from the committed reference files:

mkdir -p reproduced-results

The JSON output contains only deterministic mathematical data. Runtime measurements are printed to the terminal but are not stored in the result files.

1. Mathematical And Regression Tests

python3 -B -m unittest -v

This is the quickest verification of the functorial maps, equivariance, complete-graph comparison, structural formulas, and model consistency.

2. Five-Vertex Algebra Classification At n = 3

The committed certificate can be checked without recomputing any algebra:

python3 -B classify_edge_algebras.py \
  --verify-certificate results/r5_n3_classification.json

It should print:

certificate_valid=True
graphs=34 hilbert_types=23 collision_fibers=7 collision_graphs=18 classification_groups=33

This check independently enumerates the 34 canonical S_5-orbits of graphs, matches them against the certificate's complete graph inventory, verifies the 23 Hilbert fibers and all seven non-singleton fibers, and checks that the recorded algebra classes form a 33-part partition with no unresolved cases.

To regenerate the principal finite algebra-isomorphism computation from scratch, run:

sage -python classify_edge_algebras.py \
  --points 5 \
  --ambient 3 \
  --backend sage \
  --macaulay2 \
  --power-loci \
  --json reproduced-results/r5_n3_classification.json

The final lines should include:

graphs=34 Hilbert_types=23
abstract_algebra_type_bounds=(33, 33)
certified_isomorphic_fibers=[['r5_e02_01_d21100', 'r5_e02_02_d11110']]
unresolved_change_of_basis_fibers=[]

Thus the computation certifies exactly 33 abstract graded-algebra types. The only repeated type is

$$\mathbb Q[x,y]/(x^3,y^3),$$

arising from the adjacent and disjoint two-edge graphs.

The JSON certificate records all 34 canonical graphs, not only the 18 graphs in colliding Hilbert fibers. It includes their canonical masks and edge sets, the seven Hilbert-collision fibers, the intrinsic signatures used to separate those fibers, and the resulting partition into 33 abstract algebra types.

The same exact classification can be run without SageMath by replacing sage -python with python3 -B and --backend sage with --backend python. If the optimized structural model leaves a comparison basis-dependent, this path recomputes only that unresolved fiber with the independent exact componentwise model.

Validate either regenerated artifact with:

python3 -B classify_edge_algebras.py \
  --verify-certificate reproduced-results/r5_n3_classification.json

With the Sage backend, the displayed relation bases are canonicalized exactly as in the committed artifact, so the files can also be compared byte-for-byte:

diff -u \
  results/r5_n3_classification.json \
  reproduced-results/r5_n3_classification.json

The pure-Python backend can choose different displayed bases for the same relation spaces; use the certificate verifier rather than a raw JSON diff for that backend.

3. Hilbert-Series Censuses

Five vertices in ambient dimension four:

python3 -B graphical_configuration.py \
  --suite r5 \
  --ambient 4 \
  --h-sector \
  --hilbert-backend macaulay2 \
  --json reproduced-results/r5_n4_hilbert.json

The command ends with:

graphs=34 Hilbert_types=24

Compare it with:

diff -u \
  results/r5_n4_hilbert.json \
  reproduced-results/r5_n4_hilbert.json

The complete four-vertex ambient-dimension scan is:

for n in 2 3 4 5 6 7 8; do
  python3 -B graphical_configuration.py \
    --suite r4 \
    --ambient "$n" \
    --h-sector \
    --hilbert-backend auto \
    --json "reproduced-results/r4_n${n}_hilbert.json"
done

The numbers of Hilbert types are:

ambient dimension n	2	3	4	5	6	7	8
Hilbert types	1	9	10	10	10	10	10

Compare all seven files with:

for n in 2 3 4 5 6 7 8; do
  diff -u \
    "results/r4_n${n}_hilbert.json" \
    "reproduced-results/r4_n${n}_hilbert.json"
done

4. Comparison With Chromatic And Tutte Polynomials

python3 -B paper_results.py classical \
  --hilbert-backend macaulay2 \
  --json reproduced-results/r5_classical_comparison.json

Expected summary:

chromatic: values=23 colliding_pairs=15 largest_fiber=3
tutte: values=25 colliding_pairs=12 largest_fiber=3
h3: values=23 colliding_pairs=16 largest_fiber=4
h4: values=24 colliding_pairs=15 largest_fiber=4
joint: (H4,chromatic)=28 (H4,Tutte)=28

The command also verifies both directions of incomparability:

• P_3 disjoint-union 2K_1 and 2K_2 disjoint-union K_1 have the same chromatic and Tutte polynomials but different H_4;
• a triangle with two pendants at one vertex and C_5 have the same H_3 and H_4 but different chromatic and Tutte polynomials.

Compare the complete table with:

diff -u \
  results/r5_classical_comparison.json \
  reproduced-results/r5_classical_comparison.json

5. Six-Vertex Tree Calculation

This command enumerates the six unlabeled trees from Prüfer sequences, constructs their full algebras A_T^(3), and asks Macaulay2 for the dimensions and degrees of the intrinsic schemes

$$Z_5(A_T^{(3)})=\{u\in A_T^1:u^5=0\}.$$

sage -python paper_results.py trees \
  --backend sage \
  --json reproduced-results/r6_n3_tree_summary.json

Expected summary:

trees=6
common_Hilbert=1 + 5t^2 + 15t^4 + 24t^6 + 25t^8 + 16t^10 + 6t^12 + t^14
degree_Z5=[16, 18, 20, 22, 24, 30]

Compare it with:

diff -u \
  results/r6_n3_tree_summary.json \
  reproduced-results/r6_n3_tree_summary.json

The paper proves for every finite tree T that the Hilbert series depends only on |V(T)| and n, while the abstract algebra A_T^(3) reconstructs T. The command above reproduces the finite six-vertex calculation that originally motivated those theorems.

6. Polynomial-Size Cubic Tree Invariant

For a tree T in ambient dimension three, the complete invariant used in the tree-reconstruction theorem is

$$(V_T,K_T),\qquad K_T=\ker\bigl(\mathrm{Sym}^3(V_T)\longrightarrow A_T^3\bigr).$$

The following command constructs this pair directly from degree-three relations, without constructing the full algebra:

python3 -B tree_cubic_invariant.py \
  --points 6 \
  --json reproduced-results/p6_cubic.json \
  'P6=12,23,34,45,56'

Expected summary:

graph=P6
dim_V=5
dim_Sym3=35
dim_A3=24
dim_K=11
stored_field_entries=385

The JSON file records the ordered edge basis, the monomial basis of Sym^3(V_T), and an exact rational row basis of K_T. The construction uses only polynomially many field operations and stores O(r^6) entries. To compare it with the older full-algebra route on a small example, add --verify-full; that verification is deliberately not part of the polynomial-size algorithm.

7. Complete-Graph Cross-Check

For G = K_r, the graphical configuration space is the ordinary ordered configuration space. This command compares the graphical DGA with the independent reduced J-model:

python3 -B graphical_configuration.py \
  --suite r3 \
  --ambient 3 \
  --compare-complete

The final comparison should report:

cohomology matches J-model: True
full A_G multiplication matches J-model: True

The unit tests perform the same comparison for (r,n) = (3,3), (4,3), (3,4), (4,4).

Everyday Usage

Graph syntax

Vertices are numbered from 1. An edge may be written as 12 or 1-2. A named graph is given as:

name=edge,edge,...

For example:

python3 -B graphical_configuration.py \
  --points 5 \
  --ambient 3 \
  --h-sector \
  'P5=12,23,34,45'

Hilbert series only

Use the direct structural model:

python3 -B graphical_configuration.py \
  --points 5 --ambient 4 --h-sector \
  'C5=12,23,34,45,15'

Full multiplication table

python3 -B graphical_configuration.py \
  --points 4 --ambient 3 --h-sector --show-algebra \
  'paw=12,13,23,14'

Use --full-algebra instead of --show-algebra to construct the table without printing it.

Full graphical cohomology model

Omit --h-sector:

python3 -B graphical_configuration.py \
  --points 3 --ambient 3 --show-algebra \
  'K3=12,13,23'

This constructs the graphical Kriz-Totaro DGA and computes H*(Conf_G(P^(n-1)); Q) before locating A_G^(n) inside it.

Run python3 -B graphical_configuration.py --help, python3 -B classify_edge_algebras.py --help, and python3 -B tree_cubic_invariant.py --help for all options.

Computational Models

Direct h-Sector Model

For computations involving only A_G^(n), the code works in

$$R_G^{(n)} = \frac{\mathbb Q[h_v\mid v\in V(G)]} {(h_v^n,\Delta_{uv}\mid uv\in E(G))}, \qquad \Delta_{uv}=\sum_{k=0}^{n-1}h_u^{n-1-k}h_v^k.$$

Then

$$A_G^{(n)} = \mathbb Q[h_u+h_v,h_uh_v\mid uv\in E(G)] \subseteq R_G^{(n)}.$$

This is the default model behind --h-sector.

• Forest quotient Hilbert series are inserted in closed form.
• Connected non-bipartite graphs satisfy A_G^(n) = R_G^(n).
• Connected bipartite graphs are recovered as a fiber-product kernel over the one-edge algebra.
• Disconnected graphs are computed as tensor products over their connected components.
• Non-forest quotient jobs are batched through Macaulay2 when appropriate.

Graphical Kriz-Totaro model

The full DGA has coefficient ring

$$\mathbb Q[h_v\mid v\in V(G)]/(h_v^n)$$

and one odd generator g_uv for each edge, with

$$|g_{uv}|=2n-3,\qquad d(g_{uv})=\Delta_{uv}.$$

The implementation uses a recursively generated no-broken-circuit forest basis and componentwise normal forms. This model computes the full cohomology, including odd collision classes that are not themselves in the edge-span algebra.

Repository Layout

file	purpose
graphical_configuration.py	graphical DGA, direct h-sector model, edge-span algebra, graph maps, and main CLI
classify_edge_algebras.py	canonical presentations, socles, resolutions, and power-zero schemes
paper_results.py	deterministic classical-invariant and tree-family reproduction commands
tree_cubic_invariant.py	direct polynomial-size construction of the complete cubic tree invariant
graded_action.py	minimal-generator action model and bounded intrinsic signatures
graph_families.py	nauty-backed graph-family enumeration for research experiments
research_experiments.py	computations beyond the scope of the current paper
cohomology_linalg.py	exact rational linear algebra
macaulay2_hilbert.py	batched Macaulay2 quotient Hilbert functions
sage_backend.py	optional SageMath exact linear algebra
j_model_projective.py	independent complete-graph J-model
test_*.py	mathematical and regression tests
results/*.json	committed deterministic reference outputs
results/experiments/*.json	certificates for additional research experiments

Additional Experiments

Research computations beyond the current manuscript are kept in this same repository but isolated from its reproduction path. See EXPERIMENTS.md for their status, additional requirements, and commands. They do not alter the v1.0.3 certificate, its verification commands, or any claim in the current paper.

The Hilbert series use cohomological grading: t^2 records a degree-two class. The canonical standard-graded presentations in classify_edge_algebras.py halve cohomological degrees, so (A_G^(3))^2 becomes standard degree one.

Scope And Performance

Hilbert-only calculations are substantially cheaper than constructing a full multiplication table. The full DGA and full algebra are necessarily output-sensitive: for a tree on r vertices, the graphical DGA normal basis has dimension

$$n(n+1)^{r-1}.$$

The code therefore keeps Hilbert censuses, explicit algebras, and full cohomology as separate modes. Exact runtimes depend strongly on the graph, ambient dimension, backend, and machine; the README records expected mathematical output instead of treating timings as reproducibility criteria.

For trees in ambient dimension three, tree_cubic_invariant.py avoids this exponential output by retaining only the subspace K_T in Sym^3(V_T). Its dense row-basis representation has O(r^6) field entries, and the current exact Gaussian-elimination implementation has the crude unit-cost arithmetic bound O(r^9). This constructs the invariant from a labeled tree; it does not assert a polynomial-time algorithm for testing equivalence of two resulting subspaces under GL(V_T).

License

Released under the MIT License. See LICENSE.

The current paper's reproducibility snapshot, version 1.0.3, is archived at https://doi.org/10.5281/zenodo.21538969. The latest research release, version 1.1.0, is archived at https://doi.org/10.5281/zenodo.21610790.