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

# inducedHyperGraph -- returns the induced subgraph of a (hyper)graph

- Usage:
    `h = inducedHyperGraph(H, L)`
- Inputs:
  - H, a hypergraph,
  - L, a list, of vertices (i.e. variables in the ring of H)
- Optional inputs:
  - OriginalRing => ..., default value false, use OriginalRing inside inducedGraph or inducedHyperGraph
- Outputs:
  - h, a hypergraph, the induced subgraph of H whose edges are contained in L

## Description

This function returns the induced subgraph of a (hyper)graph on a specified set of vertices. This function enables the user to create subgraphs of the original (hyper)graph.

The default option is for the ring of the induced subgraph to contain only variables in L. Then the current ring must be changed before working with the induced subgraph. We use this setup to avoid having a lot of isolated vertices in the induced (hyper)graph. However, one can set the option OriginalRing to true if one wants to give the induced (hyper)graph the same ring as the original (hyper)graph.

Note: Since Graph is a Type of HyperGraph, inducedHyperGraph can be used for graphs, but the output is a HyperGraph. If one prefers to have a graph returned instead, use inducedGraph.

    i1 : R = QQ[a,b,c,d,e];

    i2 : G = graph {a*b,b*c,c*d,d*e,e*a} -- graph of the 5-cycle

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

    o2 : Graph

    i3 : H1 = inducedHyperGraph(G,{b,c,d,e})

    o3 = HyperGraph{"edges" => {{b, c}, {c, d}, {d, e}}}
                    "ring" => QQ[b..e]
                    "vertices" => {b, c, d, e}

    o3 : HyperGraph

    i4 : H2 = inducedHyperGraph(G,{a,b,d,e})

    o4 = HyperGraph{"edges" => {{a, b}, {a, e}, {d, e}}}
                    "ring" => QQ[a..b, d..e]
                    "vertices" => {a, b, d, e}

    o4 : HyperGraph

    i5 : use ring H1

    o5 = QQ[b..e]

    o5 : PolynomialRing

    i6 : inducedHyperGraph(H1,{c,d,e})

    o6 = HyperGraph{"edges" => {{c, d}, {d, e}}}
                    "ring" => QQ[c..e]
                    "vertices" => {c, d, e}

    o6 : HyperGraph

    i7 : use ring G

    o7 = R

    o7 : PolynomialRing

    i8 : inducedHyperGraph(G,{b,c,d,e},OriginalRing=>true) --H1 but in bigger ring

    o8 = HyperGraph{"edges" => {{b, c}, {c, d}, {d, e}}}
                    "ring" => R
                    "vertices" => {a, b, c, d, e}

    o8 : HyperGraph

Equivalently, one can use changeRing to move the induced hypergraph back into the original ring.

    i9 : R = QQ[a,b,c,d,e];

    i10 : G = graph {a*b,b*c,c*d,d*e,e*a} -- graph of the 5-cycle

    o10 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}
                "ring" => R
                "vertices" => {a, b, c, d, e}

    o10 : Graph

    i11 : H = inducedHyperGraph(G,{b,c,d})

    o11 = HyperGraph{"edges" => {{b, c}, {c, d}}}
                     "ring" => QQ[b..d]
                     "vertices" => {b, c, d}

    o11 : HyperGraph

    i12 : changeRing(H,R,{b,c,d})

    o12 = HyperGraph{"edges" => {{c, d}, {b, c}}  }
                     "ring" => R
                     "vertices" => {a, b, c, d, e}

    o12 : HyperGraph

## See also

- changeRing -- replaces vertices with variables of a different ring
- deleteEdges -- returns the (hyper)graph with specified edges removed
- inducedGraph -- returns the induced subgraph of a graph

## Ways to use inducedHyperGraph:

- `inducedHyperGraph(HyperGraph,List)`

## For the programmer

The object inducedHyperGraph is a method function with options.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/EdgeIdeals.m2:3073:0.