Multigraded commutative algebra of graph decompositions

algebraic statistics conditional independence ideal hierarchical model Markov basis multigraded ideals normality of ideals primary decomposition Segre product toric fiber product toric ideal

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25)

Abstract: The toric fiber product is a general procedure for gluing two ideals, homogeneous with respect to the same multigrading, to produce a new homogeneous ideal. Toric fiber products generalize familiar constructions in commutative algebra like adding monomial ideals and the Segre product. We describe how to obtain generating sets of toric fiber products in non-zero codimension and discuss persistence of normality and primary decompositions under toric fiber products. Several applications are discussed, including (a) the construction of Markov bases of hierarchical models in many new cases, (b) a new proof of the quartic generation of binary graph models associated to

K_{4}

-minor free graphs, and (c) the recursive computation of primary decompositions of conditional independence ideals.

Review text

The authors analyze the toric fiber product of ideals, which is a general procedure for gluing two ideals which are homogeneous with respect to the same multigrading. The toric fiber product arises frequently in applications of combinatorial commutative algebra, particularly in algebraic statistics [\textit{A. Engström} and \textit{P. Norén}, Ann. Comb. 17, No. 1, 71--103 (2013; Zbl 1263.05063); \textit{B. Sturmfels} and \textit{S. Sullivant}, Mich. Math. J. 57, 689--709 (2008; Zbl 1180.13040); \textit{B. Sturmfels} and \textit{V. Welker}, J. Algebra 361, 264--286 (2012; Zbl 1316.13042)]. In algebraic statistics, an ideal \(I_G\) is often associated to a combinatorial object \(G\) such as a graph, simplicial complex, or poset. A decomposition of \(G\) into simpler objects \(G_1\) and \(G_2\) may result in a corresponding decomposition of \(I_G\) into the ideals \(I_{G_1}\) and \(I_{G_2}\). Many times \(I_G\) may be identified as the toric fiber product of \(I_{G_1}\) and \(I_{G_2}\). The focus of this paper is twofold. First, the authors detect properties which can be lifted from two ideals to their toric fiber product. Second, the authors apply their results to a number of natural settings in algebraic statistics in which decompositions of the underlying combinatorial object leads to a toric fiber product. To give a more precise statement of the results of the paper, we describe the toric fiber product. Let \(r,d\) be positive integers, \(\mathcal{A}=\{a^1,\dots,a^r\}\subset\mathbb{Z}^d\) a set of integral vectors, and \(s,t\in \mathbb{Z}_{\geq 0}^r\) two vectors of positive integers. Furthermore, set \[ \begin{aligned} \mathbb{K}[x]&=\mathbb{K}[x^i_j:1\leq i\leq r, 1\leq j\leq s_i], \\ \mathbb{K}[y]&=\mathbb{K}[y^i_k: 1\leq i\leq r, 1\leq k\leq t_i], \\ \mathbb{K}[z]&=\mathbb{K}[z^i_{jk}: 1\leq i\leq r,1\leq j\leq s_i, 1\leq k\leq t_i], \end{aligned} \] and define \(\phi:\mathbb{K}[z]\rightarrow \mathbb{K}[x]\otimes_\mathbb{K}\mathbb{K}[y]=\mathbb{K}[x,y]\) by \(z^i_{jk}\rightarrow x^i_jy^i_k\). Given two \(\mathbb{N}\mathcal{A}\)-graded ideals \(I\subset\mathbb{K}[x]\) and \(J\subset\mathbb{K}[y]\), the toric fiber product \(I\times_\mathcal{A}J\) of \(I\) and \(J\) is defined by \(I\times_\mathcal{A}J:=\phi^{-1}(I+J)\). The toric fiber product visibly generalizes well-known procedures in commutative algebra such as addition of monomial ideals and the Segre product. Given the above setup, the authors address the following three problems. First, if \(\mathbb{K}[x]/I\) and \(\mathbb{K}[y]/J\) are normal, determine whether \(\mathbb{K}[z]/(I\times_\mathcal{A} J)\) is normal. Second, given primary decompositions for \(I\) and \(J\), construct the primary decomposition of \(I\times_\mathcal{A} J\). Third, given generating sets for \(I\) and \(J\), construct a generating set for \(I\times_\mathcal{A} J\). In Section~2, particularly in Theorem~2.5, the authors prove that if \(\mathbb{K}\) is a perfect field and \(I,J\) are geometrically prime, then normality of \(\mathbb{K}[z]/(I\times_\mathcal{A} J)\) is a consequence of normality of \(\mathbb{K}[x]/I\) and \(\mathbb{K}[y]/J\). Normality is important in algebraic statistics since it implies favorable properties of sampling algorithms for contingency tables [\textit{Y. Chen} et al., Ann. Stat. 34, No. 1, 523--545 (2006; Zbl 1091.62051); \textit{A. Takemura} et al., ``Holes in semigroups and their applications to the two-way common diagonal effect model, in: Proceedings of the 2008 International Conference on Information Theory and Statistical Learning. Las Vegas: CSREA Press. ITSL 2008, 67--72 (2008)]. In Section~3, the authors describe a natural lifting of primary decompositions of \(I,J\) to a primary decomposition of \(I\times_\mathcal{A} J\). According to Corollary~3.3, this lifting yields an irredundant primary decomposition of \(I\times_\mathcal{A} J\) when \(\mathcal{A}\) is linearly independent, \(I,J\) decompose as an intersection of geometrically primary ideals, and the primary decompositions of \(I,J\) satisfy some mild conditions with respect to the grading by \(\mathbb{N}\mathcal{A}\). In Section~4, building on previous work of \textit{S. Sullivant} in [J. Algebra 316, No. 2, 560--577 (2007; Zbl 1129.13030)], the authors describe a way to glue together generators for \(I\times_\mathcal{A} J\) from generators of \(I\) and \(J\), provided that the given generators of \(I\) and \(J\) satisfy the so-called compatible projection property. Although this property may be difficult to detect in general, the authors show that in codimension one it follows from the simpler slow-varying condition for a Markov basis. In Sections~5 and 6, the authors describe two applications of their methods. Section~5 is devoted to using the results of Section~4 to construct Markov bases for hierarchical models in many new cases (algebraically speaking, this is bounding the degree of generators of a binomial ideal). In particular, the authors recover the quartic generation of binary graph models associated to \(K_4\)-minor free graphs originally due to Král, Norine, and Pangrác [\textit{D. Král'} et al., J. Comb. Theory, Ser. A 117, No. 6, 759--765 (2010; Zbl 1215.05173)]. In Section~6, the authors apply the results of Section~3 to describe a recursive computation of primary decompositions of conditional independence ideals. Such primary decompositions contain a wealth of statistical information, such as connectivity of random walks using Markov subbases [\textit{T. Kahle} et al., J. Commut. Algebra 6, No. 2, 173--208 (2014; Zbl 1375.13047)].

Recommendations

Cites work

Cited in

(25)

Describes a project that uses

Uses Software

This page was built for publication: Multigraded commutative algebra of graph decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248919)