next | previous | forward | backward | up | top | index | toc | Macaulay2 web site

hyperGraph -- constructor for HyperGraph

Synopsis

Description

The function hyperGraph is a constructor for HyperGraph. The user can input a hypergraph in a number of different ways, which we describe below. The information decribing the hypergraph is stored in a hash table. We require that there be no inclusion relations between the edges of a hypergraph; that is, that it be a clutter. The reason is that this package is designed for edge ideals, which would lose any information about edges that are supersets of other edges.

For the first possiblity, the user inputs a polynomial ring, which specifices the vertices of graph, and a list of the edges of the graph. The edges are represented as lists.
i1 : R = QQ[a..f]

o1 = R

o1 : PolynomialRing
i2 : E = {{a,b,c},{b,c,d},{c,d,e},{e,d,f}}

o2 = {{a, b, c}, {b, c, d}, {c, d, e}, {e, d, f}}

o2 : List
i3 : h = hyperGraph (R,E)

o3 = HyperGraph{edges => {{a, b, c}, {b, c, d}, {c, d, e}, {e, d, f}}}
                ring => R
                vertices => {a, b, c, d, e, f}

o3 : HyperGraph
Alternatively, if the polynomial ring has already been defined, it suffices simply to enter the list of the edges.
i4 : S = QQ[z_1..z_8]

o4 = S

o4 : PolynomialRing
i5 : E1 = {{z_1,z_2,z_3},{z_2,z_4,z_5,z_6},{z_4,z_7,z_8},{z_5,z_7,z_8}}

o5 = {{z , z , z }, {z , z , z , z }, {z , z , z }, {z , z , z }}
        1   2   3     2   4   5   6     4   7   8     5   7   8

o5 : List
i6 : E2 = {{z_2,z_3,z_4},{z_4,z_5}}

o6 = {{z , z , z }, {z , z }}
        2   3   4     4   5

o6 : List
i7 : h1 = hyperGraph E1

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

o7 : HyperGraph
i8 : h2 = hyperGraph E2

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

o8 : HyperGraph
The list of edges could also be entered as a list of square-free monomials.
i9 : T = QQ[w,x,y,z]

o9 = T

o9 : PolynomialRing
i10 : e = {w*x*y,w*x*z,w*y*z,x*y*z}

o10 = {w*x*y, w*x*z, w*y*z, x*y*z}

o10 : List
i11 : h = hyperGraph e

o11 = HyperGraph{edges => {{w, x, y}, {w, x, z}, {w, y, z}, {x, y, z}}}
                 ring => T
                 vertices => {w, x, y, z}

o11 : HyperGraph
Another option for defining an hypergraph is to use an ideal or monomialIdeal.
i12 : C = QQ[p_1..p_6]

o12 = C

o12 : PolynomialRing
i13 : i = monomialIdeal (p_1*p_2*p_3,p_3*p_4*p_5,p_3*p_6)

o13 = monomialIdeal (p p p , p p p , p p )
                      1 2 3   3 4 5   3 6

o13 : MonomialIdeal of C
i14 : hyperGraph i

o14 = HyperGraph{edges => {{p , p , p }, {p , p , p }, {p , p }}}
                             1   2   3     3   4   5     3   6
                 ring => C
                 vertices => {p , p , p , p , p , p }
                               1   2   3   4   5   6

o14 : HyperGraph
i15 : j = ideal (p_1*p_2,p_3*p_4*p_5,p_6)

o15 = ideal (p p , p p p , p )
              1 2   3 4 5   6

o15 : Ideal of C
i16 : hyperGraph j

o16 = HyperGraph{edges => {{p , p }, {p , p , p }, {p }}}
                             1   2     3   4   5     6
                 ring => C
                 vertices => {p , p , p , p , p , p }
                               1   2   3   4   5   6

o16 : HyperGraph
From any graph we can make a hypergraph with the same edges.
i17 : D = QQ[r_1..r_5]

o17 = D

o17 : PolynomialRing
i18 : g = graph {r_1*r_2,r_2*r_4,r_3*r_5,r_5*r_4,r_1*r_5}

o18 = Graph{edges => {{r , r }, {r , r }, {r , r }, {r , r }, {r , r }}}
                        1   2     2   4     1   5     3   5     4   5
            ring => D
            vertices => {r , r , r , r , r }
                          1   2   3   4   5

o18 : Graph
i19 : h = hyperGraph g

o19 = HyperGraph{edges => {{r , r }, {r , r }, {r , r }, {r , r }, {r , r }}}
                             1   2     2   4     1   5     3   5     4   5
                 ring => D
                 vertices => {r , r , r , r , r }
                               1   2   3   4   5

o19 : HyperGraph
Not all hypergraph constructors are able to make the empty hypergraph, that is, the hypergraph with no edges. Specifically, the constructors that take only a list cannot make the empty hypergraph because the underlying ring is not given. To define the empty hypergraph, give an explicit polynomial ring or give the (monomial) ideal.
i20 : E = QQ[m,n,o,p]

o20 = E

o20 : PolynomialRing
i21 : hyperGraph(E, {})

o21 = HyperGraph{edges => {}             }
                 ring => E
                 vertices => {m, n, o, p}

o21 : HyperGraph
i22 : hyperGraph monomialIdeal(0_E)  -- the zero element of E (do not use 0)

o22 = HyperGraph{edges => {}             }
                 ring => E
                 vertices => {m, n, o, p}

o22 : HyperGraph
i23 : hyperGraph ideal (0_E)

o23 = HyperGraph{edges => {}             }
                 ring => E
                 vertices => {m, n, o, p}

o23 : HyperGraph

See also

Ways to use hyperGraph :