## Qt PiPi PivjPiAj i j CT i A j i

as the leading monomials, for example the degree-reverse lexicographic order. This monomial order is fixed for the rest of this chapter and underlies all subsequent results. Let

be the set of unknowns corresponding to the incompatible states. The sets Gt and Lt are defined by the lattice structure of C(T). Their union has a distinguished algebraic property with respect to the fixed term order.

Theorem 14.8 For any mutagenetic tree T, the set Gt U Lt is a reduced Grobner basis for the ideal (Gt) + (Lt) it generates.

Proof By Buchberger's criterion (Theorem 3.10) we need to show that all S-polynomials S(f,g) of elements f, g € Gt U Lt reduce to zero modulo the proposed Grobner basis. If the leading monomials of f and g are relatively prime, then S(f, g) reduces to zero according to [Cox et al., 1997, Prop. 2.9.4].

The remaining S-polynomials are of the form S(/j, with j = l and /j := PiPj — PiAjPiVj, and can be expressed as

= PiVj (/l,iAj + PiAjAlP(iAj) Vl) — PiVl (/j,iAl + PiAjAlP(iAl) Vj ) = PiVj /l,iAj — PiVl/j.iAl + PiAj Al (PiVj P(iAj)Vl — PiVlP(iAl)Vj) = PiVj fl — PiVlf ,iAl + piAjAl(/iVj,(iAj)Vl — /iVl,(iAl)Vj)- (14.4)

In expression (14.4) not all terms may appear because /ij = 0 whenever (iAj) = i or (i A j) = j. Since >- piVjpiAj we find that

LT(PiVj/l,iAj) = PlPiAjPiVj, LT(Pi A jAlfiVj,(iAj)Vl) ^ PlPiAjPiVj,

LT(PiVl/j,iAl) = PjPiAlPiVl, LT(PiAjAl/iVl,(iAl)Vj) ^ PjPiAlPiVl-

Thus, the multidegree of all four terms is smaller than or equal to the multide-gree of S(/ij, /il). Hence, S(/ij, /il) reduces to zero modulo Gt, and Gt U Lt is a Grobner basis [Cox et al., 1997, Thm. 2.9.3].

The Grobner basis is reduced, because for any / € Gt U Lt, no monomial of / lies in (LT((Gt U £t) \ {/})); compare (14.3). □

This result, based on the lattice structure of C(T), can also be derived from work on algebras with straightening laws on distributive lattices [Hibi, 1987]. However, there is an unexpected relation to mutagenetic tree models, which we will now explore.

The statistical model T is an algebraic variety in A. Let It C R be the ideal of polynomials vanishing on T and Ij the ideal generated by the homogeneous invariants in It. Clearly, Lt C Ij-. In addition, Lemma 14.6 implies that conditional independence statements induced by T yield polynomials in Ij. The global Markov property [Lauritzen, 1996, Sect. 3.2] on the mutagenetic tree T states that A_LB | C if and only if A is separated from B by C U {0} in T, i.e. if every path from a node u € A to a node v € B intersects CU {0}. Note that A is separated from B by C U {0} in T if and only if A is separated from B by C in the induced forest T[n]. According to Remark 1.26, an independence statement A_LB | C induces an ideal of invariants I^xB|c that is generated by the 2 x 2 minors

PiAiB iC PjAjBiC — PiAjBiC PjAiB iC = det I P P I , (14.5)

\PjAiBiC PjAjBiC J

for all (iA,iB, ic), (jA,jB, ic) € I. Let Igiobai(T) be the sum of the independence ideals I^xB|C over all statements A_LB | C induced by T. In fact, Iglobal(T) is already generated by the saturated independence statements, i.e. with AU B U C = [n] (see [Geiger et al., 2005]). The saturated independence statements translate into quadratic binomials in Ij. The following proposition connects the statistical ideal Iglobal(T) to the combinatorial ideal (Gt).

Proposition 14.9 Let T be a mutagenetic tree. Then

Proof Consider i, j e C(T), i = j. By Lemma 14.4, the induced subgraphs Ti and Tj are subbranchings of T. If we define A := Si \ Sj, B := Sj \ Si, and

C := [n] \ (AljB) = (Si n Sj) U([n] \ (Si U Sj)), then A and B are separated by C j {0} in T, hence A_LB | C. Setting

(iA,iB,iC) = (1A, 0B, 1SinSj , 0[ra]\(SiUSj)), (jA,jB,iC) = (0A, 1B, 1SinSj , 0[n]\(SiUSj)))

we find that pipj — piVjpiAj = pi^BicpJAJBic — piAJBicpjAiBic £ ^global(T) •

This establishes the inclusion (Gt) C Iglobal(T).

To prove the converse it suffices to consider a saturated conditional independence statement A_LB | C. Let g be a generator of xB|C, g = PiAiB ic PjAjB ic - PiAjB ic PjAiB ic > (iA > iB, iC ), (jA ,jB , iC ) £ J • First, note that

Pi^BicPjAjBic ^ (LT) ^-^ piAjBicPJAiBic £ (LT) •

Indeed, by Lemma 14.4, k £ C(T) if and only if there exists (u, v) e E(T) with v e V(Tk), but u £ V(Tk). Since A and B are separated by C j {0}, such an edge cannot connect A and B. Therefore, it must appear in both sets

E(TiA iB ic ) j E (TjA jB ic ) and E(TiA jB ic ) j E (TjAiB ic ).

Assume now that all four states defining g are compatible with T. Then Lemma 14.7 implies that their joins and meets are also compatible. Moreover, iAiBic V jAjBic = iAjBiC V jAiBiC =: i V j iAiBiC A jAjBiC = iAjBiC A jAiBiC =: i A j and we can write g = (piAiB ic PJAJB ic - PiVjPiAj ) + (PiVjPiAj - PiAjBicPjAiBic )

In order to characterize the ideal It of invariants of T we first draw on previous work on independence ideals in graphical models.

Proposition 14.10

Proof The claim can be derived from Theorem 14.6 and [Garcia et al., 2004,

0023320230003020 Invariant \ pa(T) 1300131030300100