trekIdeal -- the edge elimination ideal of a directed graph, or the trek separation ideal of a mixed graph

Synopsis

Usage:
I = trekIdeal(R,G) or I = trekIdeal(R,G,S)
Inputs:
- R, a ring, which should be a gaussianRing
- G, an object of class Digraph, a directed acyclic graph, or an object of class MixedGraph with directed and bidirected edges
- S, a list, trek separation statements that hold for a mixed graph G
Outputs:
- I, an ideal, the ideal attained by eliminating edge parameters for a directed graph G, or the trek separation ideal implied by statements S for a mixed graph G.

Description

For directed acyclic graphs, the covariance s_(i,j) can be expressed as the sum of all monomials corresponding to treks between vertices i and j. See gaussianParametrization for more information on treks. The trek ideal for a directed acyclic graph consists of polynomial relations between the covariances after eliminating parameters corresponding to the directed edges.

i1 : G = digraph {{a,{b,c}}, {b,{c,d}}, {c,{}}, {d,{}}}

o1 = Digraph{a => set {b, c}}
             b => set {c, d}
             c => set {}
             d => set {}

o1 : Digraph

i2 : R = gaussianRing G

o2 = R

o2 : PolynomialRing

i3 : trekIdeal(R,G)

o3 = ideal (s   s    - s   s   , s   s    - s   s   , s   s    - s   s   )
             b,c b,d    b,b c,d   a,d b,c    a,b c,d   a,d b,b    a,b b,d

o3 : Ideal of R

For mixed graphs, the ideal corresponding to a trek separation statement 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.

These ideals are described in more detail by Sullivant, Talaska and Draisma in "Trek Separation for Gaussian Graphical Models".

i4 : G = mixedGraph(digraph {{b,{c,d}},{c,{d}}},bigraph {{a,d}})

o4 = MixedGraph{Bigraph => Bigraph{a => set {d}}   }
                                   d => set {a}
                Digraph => Digraph{b => set {c, d}}
                                   c => set {d}
                                   d => set {}
                Graph => Graph{}

o4 : MixedGraph

i5 : R = gaussianRing G

o5 = R

o5 : PolynomialRing

i6 : T = trekIdeal(R,G)

o6 = ideal (s   , s   , s   s    - s   s   , - s   s    + s   s   , s   s   
             a,c   a,b   a,c b,b    a,b b,c     a,c b,b    a,b b,c   a,c b,c
     ------------------------------------------------------------------------
     - s   s   , s   s    - s   s   )
        a,b c,c   a,c b,d    a,b c,d

o6 : Ideal of R

i7 : ideal gens gb T

o7 = ideal (s   , s   )
             a,c   a,b

o7 : Ideal of R

Ways to use `trekIdeal` :

trekIdeal(Ring,Digraph)
trekIdeal(Ring,MixedGraph)
trekIdeal(Ring,MixedGraph,List)

trekIdeal -- the edge elimination ideal of a directed graph, or the trek separation ideal of a mixed graph

Synopsis

Description

See also

Ways to use trekIdeal :

Ways to use `trekIdeal` :