Macaulay2 » Documentation
Packages » EdgeIdeals :: edgeIdeal
next | previous | forward | backward | up | index | toc

edgeIdeal -- creates the edge ideal of a (hyper)graph

Synopsis

Description

The edge ideal of a (hyper)graph is a square-free monomial ideal in which the minimal generators correspond to the edges of a (hyper)graph. Along with coverIdeal, the function edgeIdeal enables us to translate many graph theoretic properties into algebraic properties.

When the input is a finite simple graph, that is, a graph with no loops or multiple edges, then the edge ideal is a quadratic square-free monomial ideal generated by terms of the form $x_ix_j$ whenever $\{x_i,x_j\}$ is an edge of the graph.

i1 : S = QQ[a..e];
 
i2 : c5 = cycle S

o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {a, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o2 : Graph
 
i3 : edgeIdeal c5

o3 = monomialIdeal (a*b, b*c, c*d, a*e, d*e)

o3 : MonomialIdeal of S
 
i4 : graph flatten entries gens edgeIdeal c5 == c5

o4 = true
 
i5 : k5 = completeGraph S

o5 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b, e}, {c, d}, {c, e}, {d, e}}}
           "ring" => S
           "vertices" => {a, b, c, d, e}

o5 : Graph
 
i6 : edgeIdeal k5

o6 = monomialIdeal (a*b, a*c, b*c, a*d, b*d, c*d, a*e, b*e, c*e, d*e)

o6 : MonomialIdeal of S

When the input is a hypergraph, the edge ideal is a square-free monomial ideal generated by monomials of the form $x_{i_1}x_{i_2}...x_{i_s}$ whenever $\{x_{i_1},...,x_{i_s}\}$ is an edge of the hypergraph. Because all of our hypergraphs are clutters, that is, no edge is allowed to be a subset of another edge, we have a bijection between the minimal generators of the edge ideal of hypergraph and the edges of the hypergraph.

i7 : S = QQ[z_1..z_8];
 
i8 : h = hyperGraph {{z_1,z_2,z_3},{z_2,z_3,z_4,z_5},{z_4,z_5,z_6},{z_6,z_7,z_8}}

o8 = HyperGraph{"edges" => {{z , z , z }, {z , z , z , z }, {z , z , z }, {z , z , z }}}
                              1   2   3     2   3   4   5     4   5   6     6   7   8
                "ring" => S
                "vertices" => {z , z , z , z , z , z , z , z }
                                1   2   3   4   5   6   7   8

o8 : HyperGraph
 
i9 : edgeIdeal h

o9 = monomialIdeal (z z z , z z z z , z z z , z z z )
                     1 2 3   2 3 4 5   4 5 6   6 7 8

o9 : MonomialIdeal of S

See also

Ways to use edgeIdeal:

For the programmer

The object edgeIdeal is a method function.