Binomiality of colored Gaussian models

Technical Summary: Binomiality of Colored Gaussian Models

Problem Statement
This paper investigates the conditions under which the vanishing ideal $I_G$ of a colored, undirected Gaussian graphical model is generated by binomials. In algebraic statistics, such models are defined by a graph $G$ on $n$ vertices and a coloring map $\lambda$ that assigns colors to vertices and edges. The model corresponds to a linear subspace $L_G$ of symmetric matrices (concentration matrices) where entries are constrained by the graph structure and color equivalences. The vanishing ideal $I_G$ consists of all polynomials that vanish on the set of covariance matrices $\Sigma = K^{-1}$ for $K \in L_G$. The central question is: under what combinatorial conditions on the colored graph $(G, \lambda)$ is $I_G$ a binomial ideal (generated by polynomials of the form $\sigma^\alpha - \sigma^\beta$)?

Previous work by Coons–Maraj–Misra–Sorea (CMMS) and Misra–Sullivant established that if the color classes are orbits under the automorphism group of the colored graph (the RCOP condition), the ideal is binomial. However, it was conjectured that this RCOP condition might be necessary. This paper aims to provide a necessary and sufficient condition for binomiality without assuming linear coordinate changes and to test the validity of the RCOP necessity conjecture.

Methodology
The authors employ a combination of algebraic geometry, combinatorics, and representation theory.

1. Algebraic Framework: The ideal $I_G$ is studied as the kernel of a rational map $\rho_G$ from the polynomial ring of covariance entries to the fraction field of the concentration matrix ring. The authors utilize a formal power series expansion of $\rho_G(\sigma_{ij})$ in terms of edge and vertex variables, derived from the Neumann series expansion of $(I - \Psi)^{-1}$.
2. Combinatorial Characterization: The paper introduces and analyzes specific graph structures:
   • Block Graphs: Graphs where every 2-connected component is a clique.
   • Triangle-Regular Graphs: A generalization of RCOP graphs defined by regularity conditions on vertices, edges, and triangles (specifically, that vertices/edges of the same color are incident to the same multisets of colored triangles).
   • Jordan Schemes: The authors connect triangle-regular graphs to Jordan schemes, a structure in algebraic combinatorics, showing that the adjacency matrices of such graphs satisfy specific algebraic relations.
3. Proof Strategy for Necessity ($\Rightarrow$): The authors prove that if $G$ is not a triangle-regular block graph, $I_G$ is not binomial. This is done by contraposition: they construct specific polynomials in $I_G$ (often determinants of submatrices) and demonstrate that their images under $\rho_G$ contain monomials that cannot be paired to form binomials in the kernel, violating the definition of a binomial ideal. They utilize Talaska's theorem on weighted path matrices in directed graphs to analyze these minors.
4. Proof Strategy for Sufficiency ($\Leftarrow$): To prove that triangle-regular block graphs yield binomial ideals, the authors construct explicit generators. They define a "completion" $\hat{G}$ of the graph $G$ and utilize a map $\psi_G$ that sends covariance entries to products of variables representing the colors along shortest paths. They show that the kernel of $\psi_G$ is generated by linear binomials (from the completion) and quadratic binomials (from the underlying uncolored block graph structure).

Key Contributions and Results

• Theorem 1.1 (Main Characterization): For a connected colored graph $G$ with disjoint vertex and edge color sets, the vanishing ideal $I_G$ is generated by binomials if and only if $G$ is a block graph and triangle-regular.
  • This result generalizes previous findings where all colors were distinct (where triangle regularity is automatic) and extends the RCOP results.
• Refutation of the RCOP Conjecture: The paper explicitly refutes the conjecture by Coons–Maraj–Misra–Sorea that binomiality implies the color classes must be orbits under the automorphism group (RCOP).
  • Corollary 1.2: The authors demonstrate the existence of colorings of the complete graph $K_n$ (derived from strongly regular graphs like the Shrikhande graph) where the ideal is binomial, but the coloring is not RCOP because the automorphism group does not act transitively on edges. This is achieved by using association schemes without transitive group actions.
• Explicit Generators: Theorem 3.1 provides an explicit generating set for $I_G$ when the conditions are met. The generators are:
  • Linear binomials: $\sigma_{i,j} - \sigma_{k,l}$ where the shortest paths $i \leftrightarrow j$ and $k \leftrightarrow l$ have identical multisets of vertex and edge colors.
  • Quadratic binomials: $\sigma_{i,j}\sigma_{k,l} - \sigma_{i,k}\sigma_{j,l}$ where the union of edges in the shortest paths satisfies a specific exchange property.
• Combinatorial Structure of Triangle-Regular Graphs: The paper establishes that triangle-regular block graphs possess a hierarchical structure (Proposition 5.2) that allows for the definition of a "depth function" and "quasi-automorphisms." These structural properties are crucial for proving that combinatorially equivalent shortest paths are isomorphic (Lemma 5.14), which underpins the sufficiency proof.

Significance and Claims
The paper claims to provide a complete combinatorial characterization of binomiality for colored Gaussian graphical models without requiring linear coordinate changes. By identifying "triangle-regularity" as the precise condition, the authors broaden the scope of models known to have binomial ideals beyond the restrictive RCOP framework.

The significance lies in:

1. Resolving a Conjecture: It definitively answers the question of whether RCOP is necessary for binomiality, showing it is not.
2. Algorithmic Implications: By providing explicit generators, the work facilitates the computation of Markov bases and statistical testing for these models, as binomial ideals are computationally more tractable than general ideals.
3. Connection to Algebraic Combinatorics: The work bridges Gaussian graphical models with Jordan schemes and coherent configurations, suggesting that tools from algebraic combinatorics can be effectively applied to statistical model theory.

The authors note that their proofs in Section 6 utilize combinatorial shortcuts that avoid the reliance on transitive group actions, which was a limitation in previous approaches (e.g., [CMMS23]). The paper concludes that the generators found are the same as those in [CMMS23] but are now proven to be sufficient under the broader, necessary and sufficient condition of triangle-regularity.