Bizonotopal Graphical Algebras

Technical Summary: Bizonotopal Graphical Algebras

Problem Statement
The paper addresses the combinatorial and algebraic properties of graphs through the lens of commutative graded algebras. While classical zonotopal algebras (external, central, and internal) associated with a graph $G$ are well-studied and encode information such as the number of spanning forests and trees via their Hilbert series (which are specializations of the Tutte polynomial), these algebras depend only on the graphical matroid of $G$. Consequently, they fail to distinguish between non-isomorphic graphs that share the same matroid. The authors seek to construct a new family of algebras that retain a connection to zonotopal structures but encode richer graph invariants, specifically distinguishing graphs that classical zonotopal algebras cannot.

Methodology
The authors introduce bizonotopal algebras by doubling the edge set of a graph $G = (V, E)$. The construction proceeds as follows:

1. Partial Orientation Algebra: Instead of the standard edge algebra $k[E]/(x_e^2)$, the authors define a "partial orientation algebra" $\mathfrak{b}E_G$. This algebra is generated by variables corresponding to oriented edges (arrows) in a set $\vec{E}$, subject to relations $x_e^2 = 0$ and $x_e x_{e'} = 0$ for opposite orientations of the same edge.
2. Generators: For each vertex $v$, a generator $y_v$ is defined as the sum of arrow variables originating from $v$.
3. Algebra Definition: The external bizonotopal algebra $B^e_G$ is the subalgebra of $\mathfrak{b}E_G$ generated by $\{y_v\}_{v \in V}$.
4. Generalization ($r$-bizonotopal): The authors generalize this to a family $B^{(r)}_G$ defined as quotients of the polynomial ring $k[V]$ by monomial ideals generated by powers of linear forms. The exponent depends on a parameter $r$ and the cut size $\kappa_S$ of vertex subsets.
   • $r=1$: External bizonotopal algebra ($B^e_G$).
   • $r=0$: Central bizonotopal algebra ($B^c_G$).
   • $r=-1$: Internal bizonotopal algebra ($B^i_G$).
5. Combinatorial Analysis: The authors characterize the monomial bases of these algebras using partial score vectors and weak parking functions. They establish that the basis elements correspond to lattice points in a specific convex polytope (the score vector polytope).
6. Recursive Relations: The paper investigates the Hilbert series of these algebras using a "loopy deletion–contraction" operation, where contracting an edge turns it into a loop rather than removing it.

Key Contributions and Results

• Complete Graph Invariants:

  • The external bizonotopal algebra $B^e_G$ is proven to be a complete invariant for graphs without isolated vertices. Two such graphs $G_1$ and $G_2$ are isomorphic if and only if their algebras $B^e_{G_1}$ and $B^e_{G_2}$ are isomorphic. This contrasts with classical external zonotopal algebras, which are only matroid invariants.
  • Superexternal algebras ($r \ge 2$) are complete invariants even for graphs with isolated vertices.
  • The central bizonotopal algebra distinguishes graphs where all vertices have degree at least two.

• Combinatorial Interpretations:

  • The dimension of $B^e_G$ equals the number of lattice points in the convex hull of the set of weak $G$-parking functions.
  • For the complete graph $K_n$, $\dim(B^e_{K_n})$ corresponds to the number of lattice points in the parking function polytope.
  • The dimension of the top-degree component of the central algebra $B^c_G$ equals the number of spanning trees of $G$.
  • The dimension of the top-degree component of the internal algebra $B^i_{K_n}$ (for $n \ge 4$) is explicitly calculated as $\binom{n-2}{2} n^{n-4}$, interpreted as the difference between the number of spanning trees and the number of two-component spanning forests in $K_n$.

• Algebraic Structure:

  • Unlike classical zonotopal algebras, bizonotopal algebras are monomial algebras (isomorphic to quotients of polynomial rings by monomial ideals).
  • The Hilbert series of the external and central bizonotopal algebras satisfy a loopy deletion–contraction relation: $h_G(t) = h_{G/e}(t) + t \cdot h_{G-e}(t)$. This relation differs from the standard Tutte polynomial recursion because the contraction operation $G/e$ preserves the edge as a loop rather than deleting it.
  • The authors provide a "categorification" of this relation for the external case via a short exact sequence of graded vector spaces involving the algebras of $G$, $G-e$, and $G/e$.

• Limitations and Weak Invariants:

  • The internal bizonotopal algebra $B^i_G$ is shown to be a much weaker invariant. For example, the Hilbert series of $B^i_G$ for any 3-regular graph is simply $(1+t)^n$, and for certain 4-regular graphs, it follows a specific polynomial form independent of the specific graph structure beyond degree and connectivity.
  • The Hilbert series of bizonotopal algebras are not specializations of the Tutte polynomial, indicating they capture information beyond the graphical matroid.

Significance
The paper establishes that by doubling the edge set and utilizing partial orientations, one can construct algebras that are strictly stronger invariants than classical zonotopal algebras. The external bizonotopal algebra successfully distinguishes non-isomorphic graphs with identical matroids, a property previously unattained by zonotopal constructions. Furthermore, the introduction of the "loopy deletion–contraction" relation opens a new avenue for computing these invariants recursively, distinct from the Tutte polynomial framework. The work connects algebraic structures to the combinatorics of parking functions and polytopes, suggesting a deeper relationship between integrable systems (via Dunkl elements) and graph theory. The authors note that while the internal algebras are weaker, the external and central cases offer a robust new class of graph invariants with rich combinatorial interpretations.