hyperGraph -- constructor for HyperGraph

Synopsis

Usage:

H = hyperGraph(R,E)

H = hyperGraph(I)

H = hyperGraph(J)

H = hyperGraph(E)

H = hyperGraph(G)
Inputs:
- R, a polynomial ring, whose variables correspond to vertices of the hypergraph
- E, a list, a list of edges, which themselves are lists of vertices
- I, a monomial ideal, which must be square-free and whose generators become the edges of the hypergraph
- J, an ideal, which must be square-free monomial and whose generators become the edges of the hypergraph
- G, a graph, which is to be converted to a HyperGraph
Outputs:
- H, a hypergraph,

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 describing 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 possibility, the user inputs a polynomial ring, which specifies 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}, {d, e, 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

Ways to use hyperGraph:

hyperGraph(Graph)
hyperGraph(Ideal)
hyperGraph(List)
hyperGraph(MonomialIdeal)
hyperGraph(PolynomialRing,List)

For the programmer

The object hyperGraph is a method function.

hyperGraph -- constructor for HyperGraph

Synopsis

Description

See also

Ways to use hyperGraph:

For the programmer