# trekIdeal -- trek separation ideal of a mixed graph

## Synopsis

• Usage:
I = trekIdeal(R,G)
• Inputs:
• R, a ring, which should be a gaussianRing
• G, , , or with no cycles, or an instance of the type MixedGraph with directed and bidirected edges
• Outputs:
• I, an ideal, the ideal of determinantal trek separation statements implied by the graph $G$.

## Description

For mixed graphs, the ideal corresponding to all trek separation statements {A,B,CA,CB} (where A,B,CA,CB are disjoint lists of vertices of G) is generated by the r+1 x r+1 minors of the submatrix of the covariance matrix M = (s_{(i,j)}), whose rows are in A, and whose columns are in B, and where r = #CA+#CB.

This function is not yet implemented for mixed graphs with undirected edges.

These ideals are described in more detail by Sullivant, Talaska and Draisma in "Trek Separation for Gaussian Graphical Models" Annals of Statistics 38 no.3 (2010) 1665–1685 and give all determinantal constraints on the covariance matrix of a Gaussian graphical model.

 i1 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}}) o1 = MixedGraph{Bigraph => Bigraph{a => {d}} } d => {a} Digraph => Digraph{b => {c, d}} c => {d} d => {} Graph => Graph{} o1 : MixedGraph i2 : R = gaussianRing G o2 = R o2 : PolynomialRing i3 : T = trekIdeal(R,G) o3 = ideal (s , s , - s s + s s , - s s + s s , - a,b a,c a,c b,b a,b b,c a,c b,b a,b b,c ------------------------------------------------------------------------ s s + s s , s s - s s ) a,c b,c a,b c,c a,c b,d a,b c,d o3 : Ideal of R i4 : ideal gens gb T o4 = ideal (s , s ) a,c a,b o4 : Ideal of R

For undirected graphs $G$, the trekIdeal(R,G) is the same as conditionalIndependenceIdeal(R,globalMarkov(G)). For directed graphs $G$, trekIdeal(R,G) is generally larger than conditionalIndependenceIdeal(R,globalMarkov(G)).

 i5 : G = graph{{a,b},{b,c},{c,d},{a,d}} o5 = Graph{a => {b, d}} b => {a, c} c => {b, d} d => {a, c} o5 : Graph i6 : R = gaussianRing G o6 = R o6 : PolynomialRing i7 : T = trekIdeal(R,G); o7 : Ideal of R i8 : CI = conditionalIndependenceIdeal(R,globalMarkov(G)); o8 : Ideal of R i9 : T == CI o9 = true i10 : H = digraph{{1,{4}},{2,{4}},{3,{4,5}},{4,{5}}} o10 = Digraph{1 => {4} } 2 => {4} 3 => {4, 5} 4 => {5} 5 => {} o10 : Digraph i11 : R = gaussianRing H o11 = R o11 : PolynomialRing i12 : T = trekIdeal(R,H); o12 : Ideal of R i13 : CI = conditionalIndependenceIdeal(R,globalMarkov(H)); o13 : Ideal of R i14 : T == CI o14 = false

## Caveat

trekSeparation is currently only implemented with mixedGraphs that have directed and bidirected edges.