trekIdeal -- trek separation ideal of a mixed graph

Synopsis

Usage:

I = trekIdeal(R,G)
Inputs:
- R, a ring, which should be a gaussianRing
- G, a graph, a graph, or a digraph 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.

Ways to use trekIdeal :

trekIdeal(Ring,Digraph)
trekIdeal(Ring,Graph)
trekIdeal(Ring,MixedGraph)

For the programmer