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
|
The object edgeIdeal is a method function.