This is EdgeIdeals.info, produced by Macaulay2, version 1.25.05

EdgeIdeals -- A package for working with the edge ideals of (hyper)graphs
*************************************************************************

Description
===========

EdgeIdeals is a package to work with the edge ideals of (hyper)graphs.

An edge ideal is a square-free monomial ideal where the generators of the
monomial ideal correspond to the edges of the (hyper)graph.  An edge ideal
complements the Stanley-Reisner correspondence (see SimplicialComplexes)
by providing an alternative combinatorial
interpretation of the monomial generators.

This package exploits the correspondence between square-free monomial ideals
and the combinatorial objects, by using commutative algebra routines to derive
information about (hyper)graphs. For some of the mathematical background on
this material, see Chapter 6 of the textbook Monomial Algebras by R. Villarreal
and the survey paper of T. Ha and A. Van Tuyl ("Resolutions of square-free
monomial ideals via facet ideals: a survey," Contemporary Mathematics. 448
(2007) 91-117).

See the Constructor Overview, and the
Extended Example, for some illustrations of ways to use this
package.

Note: We require all hypergraphs to be clutters, which are hypergraphs in which
no edge is a subset of another. If $H$ is a hypergraph that is not a clutter,
then the edge ideal of $H$ is indistinguishable from the edge ideal of the
clutter of minimal edges in $H$. (Edges of $H$ that are supersets of other
edges would not appear as minimal generators of the edge ideal of $H$.) The
edge ideal of a hypergraph is similar to the facet ideal of a simplicial
complex, as defined by S. Faridi in  "The facet ideal of a simplicial complex,"
Manuscripta Mathematica 109, 159-174 (2002).

Authors
=======

  * Chris Francisco (see http://www.math.okstate.edu/~chris/ )
    <chris@math.okstate.edu>
  * Andrew Hoefel (see http://www.mathstat.dal.ca/~handrew/ )
    <handrew@mathstat.dal.ca>
  * Adam Van Tuyl (see http://flash.lakeheadu.ca/~avantuyl/ )
    <avantuyl@lakeheadu.ca>

Certification a gold star
=========================

Version 1.0.0 of this package was accepted for publication in volume 1 (see
https://msp.org/jsag/2009/1-1/ ) of The Journal of Software for Algebra and
Geometry: Macaulay2 (see https://msp.org/jsag/ ) on 2009-06-27, in the article
EdgeIdeals: a package for (hyper)graphs (see
https://msp.org/jsag/2009/1-1/p01.xhtml ) (DOI: 10.2140/jsag.2009.1.1 (see
https://doi.org/10.2140/jsag.2009.1.1 )). That version can be obtained from the
journal (see https://msp.org/jsag/2009/1-1/jsag-v1-n1-x01-code.zip ).

Version
=======

This documentation describes version 1.0.2 of EdgeIdeals.

Citation
========

If you have used this package in your research, please cite it as follows:

+----------------------------------------------------------------------------+
|@misc{EdgeIdealsSource,                                                     |
|  title = {{EdgeIdeals: A \emph{Macaulay2} package. Version~1.0.2}},        |
|  author = {Chris Francisco and Andrew Hoefel and Adam Van Tuyl},           |
|  howpublished = {A \emph{Macaulay2} package available at                   |
|    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages}}|
|}                                                                           |
|                                                                            |
|@article{EdgeIdealsArticle,                                                 |
|  title = {{EdgeIdeals: a package for (hyper)graphs}},                      |
|  author = {Chris Francisco and Andrew Hoefel and Adam Van Tuyl},           |
|  journal = {The Journal of Software for Algebra and Geometry: Macaulay2},  |
|  volume = {1},                                                             |
|  year = {2009},                                                            |
|}                                                                           |
|                                                                            |
+----------------------------------------------------------------------------+

Exports
=======

  * Types
      * Graph -- a class for graphs
      * HyperGraph -- a class for hypergraphs
  * Functions and commands
      * adjacencyMatrix -- returns the adjacency Matrix
        of a graph
      * allEvenHoles -- returns all even holes in a graph
      * allOddHoles -- returns all odd holes in a graph
      * antiCycle -- returns a graph of an anticycle
      * changeRing -- replaces vertices with variables of a
        different ring
      * chromaticNumber -- computes the chromatic
        number of a hypergraph
      * cliqueComplex -- returns the clique complex of a
        graph
      * cliqueNumber -- computes the clique number of a
        graph
      * complementGraph -- returns the complement of a
        graph or hypergraph
      * completeGraph -- returns a complete graph
      * completeMultiPartite -- returns a complete
        multipartite graph
      * connectedGraphComponents -- returns
        the connected components of a graph
      * coverIdeal -- creates the cover ideal of a
        (hyper)graph
      * cycle -- returns a graph cycle
      * degreeVertex -- returns the degree of a vertex
      * deleteEdges -- returns the (hyper)graph with
        specified edges removed
      * edgeIdeal -- creates the edge ideal of a (hyper)graph
      * edges -- gets the edges of a (hyper)graph
      * getCliques -- returns cliques in a graph
      * getEdge -- gets the n-th edge in a (hyper)graph
      * getEdgeIndex -- finds the index of an edge in a
        HyperGraph
      * getGoodLeaf -- returns an edge that is a good leaf
      * getGoodLeafIndex -- returns the index of an
        edge that is a good leaf
      * getMaxCliques -- returns maximal cliques in a
        graph
      * graph -- constructor for Graph
      * hasGoodLeaf -- determines if a HyperGraph contains
        a good leaf
      * hasOddHole -- tells whether a graph contains an odd
        hole
      * hyperGraph -- constructor for HyperGraph
      * hyperGraphToSimplicialComplex, --
        makes a simplicial complex from a (hyper)graph
      * incidenceMatrix -- returns the incidence matrix
        of a hypergraph
      * independenceComplex -- returns the
        independence complex of a (hyper)graph
      * independenceNumber -- determines the
        independence number of a graph
      * inducedGraph -- returns the induced subgraph of a
        graph
      * inducedHyperGraph -- returns the induced
        subgraph of a (hyper)graph
      * isBipartite -- determines if a graph is bipartite
      * isChordal -- determines if a graph is chordal
      * isCM -- determines if a (hyper)graph is Cohen-Macaulay
      * isConnected -- determines if a (hyper)graph is
        connected
      * isConnectedGraph -- determines if a graph is
        connected
      * isEdge -- determines if an edge is in a (hyper)graph
      * isForest -- determines whether a (hyper)graph is a
        forest
      * isGoodLeaf -- determines if an edge is a good leaf
      * isGraph -- determines if a hypergraph is a graph
      * isLeaf -- determines if an edge (or vertex) is a leaf of
        a (hyper)graph
      * isolatedVertices -- returns all vertices not
        contained in any edge
      * isPerfect -- determines whether a graph is perfect
      * isSCM -- determines if a (hyper)graph is sequentially
        Cohen-Macaulay
      * lineGraph -- returns the line graph of a (hyper)graph
      * neighbors -- returns the neighbors of a vertex or
        list of vertices
      * numConnectedComponents -- returns the
        number of connected components in a (hyper)graph
      * numConnectedGraphComponents, --
        returns the number of connected components in a graph
      * numTriangles -- returns the number of triangles in
        a graph
      * randomGraph -- returns a random graph
      * randomHyperGraph -- returns a random
        hypergraph
      * randomUniformHyperGraph -- returns a
        random uniform hypergraph
      * simplicialComplexToHyperGraph, --
        makes a (hyper)graph from a simplicial complex
      * smallestCycleSize -- returns the size of the
        smallest induced cycle of a graph
      * spanningTree -- returns a spanning tree of a graph
      * vertexCoverNumber -- find the vertex covering
        number of a (hyper)graph
      * vertexCovers -- list the minimal vertex covers of
        a (hyper)graph
  * Methods
      * "adjacencyMatrix(Graph)" -- see adjacencyMatrix,
        -- returns the adjacency Matrix of a graph
      * "allEvenHoles(Graph)" -- see allEvenHoles, --
        returns all even holes in a graph
      * "allOddHoles(Graph)" -- see allOddHoles, -- returns
        all odd holes in a graph
      * "antiCycle(List)" -- see antiCycle, -- returns a graph
        of an anticycle
      * "antiCycle(Ring)" -- see antiCycle, -- returns a graph
        of an anticycle
      * "antiCycle(Ring,ZZ)" -- see antiCycle, -- returns a
        graph of an anticycle
      * "changeRing(HyperGraph,PolynomialRing,List)" -- see changeRing,
        -- replaces vertices with variables of a different ring
      * "chromaticNumber(HyperGraph)" -- see chromaticNumber,
        -- computes the chromatic number of a hypergraph
      * "cliqueComplex(Graph)" -- see cliqueComplex, --
        returns the clique complex of a graph
      * "cliqueNumber(Graph)" -- see cliqueNumber, --
        computes the clique number of a graph
      * "complementGraph(Graph)" -- see complementGraph,
        -- returns the complement of a graph or hypergraph
      * "complementGraph(HyperGraph)" -- see complementGraph,
        -- returns the complement of a graph or hypergraph
      * "completeGraph(List)" -- see completeGraph, --
        returns a complete graph
      * "completeGraph(Ring)" -- see completeGraph, --
        returns a complete graph
      * "completeGraph(Ring,ZZ)" -- see completeGraph, --
        returns a complete graph
      * "completeMultiPartite(Ring,List)" -- see completeMultiPartite,
        -- returns a complete multipartite graph
      * "completeMultiPartite(Ring,ZZ,ZZ)" -- see completeMultiPartite,
        -- returns a complete multipartite graph
      * "connectedComponents(HyperGraph)" -- see connectedComponents,
        -- returns the connected components of a
        hypergraph
      * "connectedGraphComponents(HyperGraph)" -- see
        connectedGraphComponents, -- returns the
        connected components of a graph
      * "coverIdeal(HyperGraph)" -- see coverIdeal, --
        creates the cover ideal of a (hyper)graph
      * "cycle(List)" -- see cycle, -- returns a graph cycle
      * "cycle(Ring)" -- see cycle, -- returns a graph cycle
      * "cycle(Ring,ZZ)" -- see cycle, -- returns a graph cycle
      * "degreeVertex(HyperGraph,RingElement)" -- see degreeVertex,
        -- returns the degree of a vertex
      * "degreeVertex(HyperGraph,ZZ)" -- see degreeVertex,
        -- returns the degree of a vertex
      * "deleteEdges(HyperGraph,List)" -- see deleteEdges,
        -- returns the (hyper)graph with specified edges removed
      * "edgeIdeal(HyperGraph)" -- see edgeIdeal, -- creates
        the edge ideal of a (hyper)graph
      * "edges(HyperGraph)" -- see edges, -- gets the edges of a
        (hyper)graph
      * "getCliques(Graph)" -- see getCliques, -- returns
        cliques in a graph
      * "getCliques(Graph,ZZ)" -- see getCliques, -- returns
        cliques in a graph
      * "getEdge(HyperGraph,ZZ)" -- see getEdge, -- gets the
        n-th edge in a (hyper)graph
      * "getEdgeIndex(HyperGraph,List)" -- see getEdgeIndex,
        -- finds the index of an edge in a HyperGraph
      * "getEdgeIndex(HyperGraph,RingElement)" -- see getEdgeIndex,
        -- finds the index of an edge in a HyperGraph
      * "getGoodLeaf(HyperGraph)" -- see getGoodLeaf, --
        returns an edge that is a good leaf
      * "getGoodLeafIndex(HyperGraph)" -- see getGoodLeafIndex,
        -- returns the index of an edge that is a good leaf
      * "getMaxCliques(Graph)" -- see getMaxCliques, --
        returns maximal cliques in a graph
      * "graph(HyperGraph)" -- see graph, -- constructor for Graph
      * "graph(Ideal)" -- see graph, -- constructor for Graph
      * "graph(List)" -- see graph, -- constructor for Graph
      * "graph(MonomialIdeal)" -- see graph, -- constructor for
        Graph
      * "graph(PolynomialRing,List)" -- see graph, -- constructor
        for Graph
      * "hasGoodLeaf(HyperGraph)" -- see hasGoodLeaf, --
        determines if a HyperGraph contains a good leaf
      * "hasOddHole(Graph)" -- see hasOddHole, -- tells
        whether a graph contains an odd hole
      * "hyperGraph(Graph)" -- see hyperGraph, -- constructor
        for HyperGraph
      * "hyperGraph(Ideal)" -- see hyperGraph, -- constructor
        for HyperGraph
      * "hyperGraph(List)" -- see hyperGraph, -- constructor
        for HyperGraph
      * "hyperGraph(MonomialIdeal)" -- see hyperGraph, --
        constructor for HyperGraph
      * "hyperGraph(PolynomialRing,List)" -- see hyperGraph,
        -- constructor for HyperGraph
      * HyperGraph == HyperGraph -- equality
      * "hyperGraphToSimplicialComplex(HyperGraph)" -- see
        hyperGraphToSimplicialComplex, -- makes
        a simplicial complex from a (hyper)graph
      * "incidenceMatrix(HyperGraph)" -- see incidenceMatrix,
        -- returns the incidence matrix of a hypergraph
      * "independenceComplex(HyperGraph)" -- see independenceComplex,
        -- returns the independence complex of a
        (hyper)graph
      * "independenceNumber(Graph)" -- see independenceNumber,
        -- determines the independence number of a graph
      * "inducedGraph(Graph,List)" -- see inducedGraph, --
        returns the induced subgraph of a graph
      * "inducedHyperGraph(HyperGraph,List)" -- see inducedHyperGraph,
        -- returns the induced subgraph of a (hyper)graph
      * "isBipartite(Graph)" -- see isBipartite, --
        determines if a graph is bipartite
      * "isChordal(Graph)" -- see isChordal, -- determines if
        a graph is chordal
      * "isCM(HyperGraph)" -- see isCM, -- determines if a
        (hyper)graph is Cohen-Macaulay
      * "isConnected(HyperGraph)" -- see isConnected, --
        determines if a (hyper)graph is connected
      * "isConnectedGraph(HyperGraph)" -- see isConnectedGraph,
        -- determines if a graph is connected
      * "isEdge(HyperGraph,List)" -- see isEdge, -- determines if
        an edge is in a (hyper)graph
      * "isEdge(HyperGraph,RingElement)" -- see isEdge, --
        determines if an edge is in a (hyper)graph
      * "isForest(Graph)" -- see isForest, -- determines
        whether a (hyper)graph is a forest
      * "isForest(HyperGraph)" -- see isForest, -- determines
        whether a (hyper)graph is a forest
      * "isGoodLeaf(HyperGraph,ZZ)" -- see isGoodLeaf, --
        determines if an edge is a good leaf
      * "isGraph(HyperGraph)" -- see isGraph, -- determines if a
        hypergraph is a graph
      * "isLeaf(Graph,ZZ)" -- see isLeaf, -- determines if an
        edge (or vertex) is a leaf of a (hyper)graph
      * "isLeaf(HyperGraph,RingElement)" -- see isLeaf, --
        determines if an edge (or vertex) is a leaf of a (hyper)graph
      * "isLeaf(HyperGraph,ZZ)" -- see isLeaf, -- determines if
        an edge (or vertex) is a leaf of a (hyper)graph
      * "isolatedVertices(HyperGraph)" -- see isolatedVertices,
        -- returns all vertices not contained in any edge
      * "isPerfect(Graph)" -- see isPerfect, -- determines
        whether a graph is perfect
      * "isSCM(HyperGraph)" -- see isSCM, -- determines if a
        (hyper)graph is sequentially Cohen-Macaulay
      * "lineGraph(HyperGraph)" -- see lineGraph, -- returns
        the line graph of a (hyper)graph
      * "neighbors(HyperGraph,List)" -- see neighbors, --
        returns the neighbors of a vertex or list of vertices
      * "neighbors(HyperGraph,RingElement)" -- see neighbors,
        -- returns the neighbors of a vertex or list of vertices
      * "neighbors(HyperGraph,ZZ)" -- see neighbors, --
        returns the neighbors of a vertex or list of vertices
      * "numConnectedComponents(HyperGraph)" -- see
        numConnectedComponents, -- returns the number
        of connected components in a (hyper)graph
      * "numConnectedGraphComponents(HyperGraph)" -- see
        numConnectedGraphComponents, -- returns
        the number of connected components in a graph
      * "numTriangles(Graph)" -- see numTriangles, --
        returns the number of triangles in a graph
      * "randomGraph(PolynomialRing,ZZ)" -- see randomGraph,
        -- returns a random graph
      * "randomHyperGraph(PolynomialRing,List)" -- see randomHyperGraph,
        -- returns a random hypergraph
      * "randomUniformHyperGraph(PolynomialRing,ZZ,ZZ)" -- see
        randomUniformHyperGraph, -- returns a random
        uniform hypergraph
      * ring(HyperGraph) -- gives the ring of a
        (hyper)graph
      * "simplicialComplexToHyperGraph(SimplicialComplex)" -- see
        simplicialComplexToHyperGraph, -- makes
        a (hyper)graph from a simplicial complex
      * "smallestCycleSize(Graph)" -- see smallestCycleSize,
        -- returns the size of the smallest induced cycle of
        a graph
      * "spanningTree(Graph)" -- see spanningTree, --
        returns a spanning tree of a graph
      * "vertexCoverNumber(HyperGraph)" -- see vertexCoverNumber,
        -- find the vertex covering number of a (hyper)graph
      * "vertexCovers(HyperGraph)" -- see vertexCovers, --
        list the minimal vertex covers of a (hyper)graph
      * vertices(HyperGraph) -- gets the
        vertices of a (hyper)graph
  * Symbols
      * BranchLimit -- optional argument for
        randomHyperGraph
      * Gins -- optional argument for isSCM
      * MaximalEdges -- optional argument for changeRing
      * OriginalRing -- optional argument for
        inducedHyperGraph
      * TimeLimit -- optional argument for randomHyperGraph

For the programmer
==================

The object EdgeIdeals, is a package (Macaulay2Doc),
defined in EdgeIdeals.m2.

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1241:0.

adjacencyMatrix -- returns the adjacency Matrix of a graph
**********************************************************

  * Usage:
        M = adjacencyMatrix G
  * Inputs:
      * G, a graph,
  * Outputs:
      * M, a matrix (Macaulay2Doc), the adjacency matrix of the
        graph

Description
===========

This function returns the adjacency matrix of the given graph G.  The
(i,j)^{th} position of the matrix is 1 if there is an edge between the i^{th}
vertex and j^{th} vertex, and 0 otherwise.  The rows and columns are indexed by
the variables of the ring and use the ordering of the variables for determining
the order of the rows and columns.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = graph {a*b,a*c,b*c,c*d,d*e,e*f,f*a,a*d}                             |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {a, d}, {c, d}, {d, e}, {a,   |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|f}, {e, f}}}                                                                 |
+-----------------------------------------------------------------------------+
|i3 : t = adjacencyMatrix G                                                   |
|                                                                             |
|o3 = | 0 1 1 1 0 1 |                                                         |
|     | 1 0 1 0 0 0 |                                                         |
|     | 1 1 0 1 0 0 |                                                         |
|     | 1 0 1 0 1 0 |                                                         |
|     | 0 0 0 1 0 1 |                                                         |
|     | 1 0 0 0 1 0 |                                                         |
|                                                                             |
|              6       6                                                      |
|o3 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+
|i4 : T = QQ[f,e,d,c,b,a];                                                    |
+-----------------------------------------------------------------------------+
|i5 : G = graph {a*b,a*c,b*c,c*d,d*e,e*f,f*a,a*d}                             |
|                                                                             |
|o5 = Graph{"edges" => {{f, e}, {e, d}, {d, c}, {c, b}, {f, a}, {d, a}, {c,   |
|           "ring" => T                                                       |
|           "vertices" => {f, e, d, c, b, a}                                  |
|                                                                             |
|o5 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|a}, {b, a}}}                                                                 |
+-----------------------------------------------------------------------------+
|i6 : t = adjacencyMatrix G -- although the same graph, matrix is different   |
|                                                                             |
|o6 = | 0 1 0 0 0 1 |                                                         |
|     | 1 0 1 0 0 0 |                                                         |
|     | 0 1 0 1 0 1 |                                                         |
|     | 0 0 1 0 1 1 |                                                         |
|     | 0 0 0 1 0 1 |                                                         |
|     | 1 0 1 1 1 0 |                                                         |
|                                                                             |
|              6       6                                                      |
|o6 : Matrix ZZ  <-- ZZ                                                       |
|-----------------------------------------------------------------------------|
|since variables have different ordering                                      |
+-----------------------------------------------------------------------------+

See also
========

  * incidenceMatrix -- returns the incidence matrix of
    a hypergraph
  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

Ways to use adjacencyMatrix:
============================

  * "adjacencyMatrix(Graph)"

For the programmer
==================

The object adjacencyMatrix, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1744:0.

allEvenHoles -- returns all even holes in a graph
*************************************************

  * Usage:
        L = allEvenHoles G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a list (Macaulay2Doc), returns all even holes contained
        in G.

Description
===========

The method is based on work of Francisco-Ha-Van Tuyl, looking at the associated
primes of the square of the Alexander dual of the edge ideal. An even hole is
an even induced cycle (necessarily of length at least four). The algorithm for
allEvenHoles uses an observation of Mermin. Fix an edge, and split this edge
into two different edges, introducing a new vertex. Find all the odd holes in
that graph. Do that for each edge in the graph, one at a time, and pick out all
the odd holes containing the additional vertex. Dropping this vertex from each
of the odd holes gives all the even holes in the original graph.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd
holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = cycle(R,6);                                                         |
+-----------------------------------------------------------------------------+
|i3 : allEvenHoles G                                                          |
|                                                                             |
|o3 = {{a, b, c, d, e, f}}                                                    |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : H = graph(monomialIdeal(a*b,b*c,c*d,d*e,e*f,a*f,a*d))                   |
|                                                                             |
|o4 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}, {d,                   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|--6-cycle with a chord                                                       |
|                                                                             |
|e}, {a, f}, {e, f}}}                                                         |
+-----------------------------------------------------------------------------+
|i5 : allEvenHoles H --two 4-cycles                                           |
|                                                                             |
|o5 = {{a, b, c, d}, {a, d, e, f}}                                            |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * allOddHoles -- returns all odd holes in a graph
  * hasOddHole -- tells whether a graph contains an odd hole

Ways to use allEvenHoles:
=========================

  * "allEvenHoles(Graph)"

For the programmer
==================

The object allEvenHoles, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1785:0.

allOddHoles -- returns all odd holes in a graph
***********************************************

  * Usage:
        L = allOddHoles G
  * Inputs:
      * G, a graph,
  * Outputs:
      * L, a list (Macaulay2Doc), returns all odd holes contained
        in G.

Description
===========

An odd hole is an odd induced cycle of length at least 5. The method is based
on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the
square of the Alexander dual of the edge ideal.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd
holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_6];                                                       |
+-----------------------------------------------------------------------------+
|i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5|
|                                                                             |
|o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     1   5     4   5     1 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|-cycle and a triangle                                                        |
|                                                                             |
| x }, {x , x }}}                                                             |
|  6     5   6                                                                |
+-----------------------------------------------------------------------------+
|i3 : allOddHoles G --only the 5-cycle should appear                          |
|                                                                             |
|o3 = {{x , x , x , x , x }}                                                  |
|        1   2   3   4   5                                                    |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : H = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6,x_1*x|
|                                                                             |
|o4 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     1   4     3   4     1   5     4 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|_4}) --no odd holes                                                          |
|                                                                             |
| x }, {x , x }, {x , x }}}                                                   |
|  5     1   6     5   6                                                      |
+-----------------------------------------------------------------------------+
|i5 : allOddHoles H                                                           |
|                                                                             |
|o5 = {}                                                                      |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * allEvenHoles -- returns all even holes in a graph
  * hasOddHole -- tells whether a graph contains an odd hole

Ways to use allOddHoles:
========================

  * "allOddHoles(Graph)"

For the programmer
==================

The object allOddHoles, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1821:0.

antiCycle -- returns a graph of an anticycle
********************************************

  * Usage:
        C = antiCycle R
        C = antiCycle(R,N)
        C = antiCycle L
  * Inputs:
      * R, a ring (Macaulay2Doc),
      * N, an integer (Macaulay2Doc), length of anticycle
      * L, a list (Macaulay2Doc), of vertices to make into the
        complement of a cycle in the order provided
  * Outputs:
      * C, a graph, an anticycle on the vertices in L or on the
        variables of R.

Description
===========

This function returns the graph that is the complement of the cycle obtained
from L by applying the function cycle.

+---------------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e];                                        |
+---------------------------------------------------------------+
|i2 : antiCycle R                                               |
|                                                               |
|o2 = Graph{"edges" => {{a, c}, {a, d}, {b, d}, {b, e}, {c, e}}}|
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o2 : Graph                                                     |
+---------------------------------------------------------------+
|i3 : antiCycle(R,4)                                            |
|                                                               |
|o3 = Graph{"edges" => {{a, c}, {b, d}}  }                      |
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o3 : Graph                                                     |
+---------------------------------------------------------------+
|i4 : antiCycle {e,c,d,b}                                       |
|                                                               |
|o4 = Graph{"edges" => {{d, e}, {b, c}}  }                      |
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o4 : Graph                                                     |
+---------------------------------------------------------------+
|i5 : complementGraph antiCycle R == cycle R                    |
|                                                               |
|o5 = true                                                      |
+---------------------------------------------------------------+

See also
========

  * cycle -- returns a graph cycle
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use antiCycle:
======================

  * "antiCycle(List)"
  * "antiCycle(Ring)"
  * "antiCycle(Ring,ZZ)"

For the programmer
==================

The object antiCycle, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1862:0.

BranchLimit -- optional argument for randomHyperGraph
*****************************************************

Description
===========

The randomHyperGraph, method follows a backtracking
algorithm to generate edges with no inclusions between them. At each step in
the recursive tree,  see randomHyperGraph, will make
BranchLimit attempts to complete its list of edges. Thus, if a hypergraph with
N edges is required, see randomHyperGraph, may take
BranchLimit^N steps before terminating. To be more precise, the method is
implemented so that it makes BranchLimit + L attempts at level L of the
recursion. The default value is 3.

See also
========

  * TimeLimit -- optional argument for randomHyperGraph
  * randomHyperGraph -- returns a random hypergraph

Functions with optional argument named BranchLimit:
===================================================

  * randomHyperGraph(...,BranchLimit=>...)
    -- limit
    recursive branching in randomHyperGraph

For the programmer
==================

The object BranchLimit, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4241:0.

changeRing -- replaces vertices with variables of a different ring
******************************************************************

  * Usage:
        G = changeRing(H,R,L)
        G = changeRing(H,R,L, MaximalEdges => B)
  * Inputs:
      * H, a hypergraph,
      * R, a polynomial ring (Macaulay2Doc), containing
        the new vertices as variables
      * L, a list (Macaulay2Doc), of substitutions, one variable in
        R for each vertex of H
      * B, a Boolean value (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * MaximalEdges,
        => ..., default value false, optional argument for changeRing
  * Outputs:
      * G, a hypergraph, over the ring R with edges obtained
        by making substitutions into the edges of H

Description
===========

This method is meant for moving a HyperGraph, that is defined
over one ring to another ring R. The parameter L must be a list containing
variables of R that should replace the vertices of H. For the most basic way to
use this method, see the first example:

+--------------------------------------------+
|i1 : P = QQ[a,b,c];                         |
+--------------------------------------------+
|i2 : H = hyperGraph({a*b,b*c});             |
+--------------------------------------------+
|i3 : S = QQ[x,y,z,w];                       |
+--------------------------------------------+
|i4 : changeRing(H,S,{x,z,y})                |
|                                            |
|o4 = HyperGraph{"edges" => {{y, z}, {x, z}}}|
|                "ring" => S                 |
|                "vertices" => {x, y, z, w}  |
|                                            |
|o4 : HyperGraph                             |
+--------------------------------------------+

In the example above, a is replaced with x, b is replaced with z, and c is
replaced with y. A more complex situation arises when two vertices of H are
replaced by the same variable.

+--------------------------------------------+
|i5 : P = QQ[a,b,c];                         |
+--------------------------------------------+
|i6 : H = hyperGraph({a*b*c});               |
+--------------------------------------------+
|i7 : G = hyperGraph({a*b,b*c});             |
+--------------------------------------------+
|i8 : S = QQ[x,y,z,w];                       |
+--------------------------------------------+
|i9 : changeRing(H,S,{x,y,x})                |
|                                            |
|o9 = HyperGraph{"edges" => {{x, y}}       } |
|                "ring" => S                 |
|                "vertices" => {x, y, z, w}  |
|                                            |
|o9 : HyperGraph                             |
+--------------------------------------------+
|i10 : changeRing(G,S,{x,y,x})               |
|                                            |
|o10 = HyperGraph{"edges" => {{x, y}}       }|
|                 "ring" => S                |
|                 "vertices" => {x, y, z, w} |
|                                            |
|o10 : HyperGraph                            |
+--------------------------------------------+

Note that duplicate variables are removed from edges after substitution.
Duplicate edges are also reduced to a single edge. As all HyperGraphs in this
package have the property that no edge is a subset of any other edge, some
edges may need to be dropped after substitution. This happens in the next
example.

+------------------------------------------------+
|i11 : P = QQ[a,b,c];                            |
+------------------------------------------------+
|i12 : H = hyperGraph({a*b,b*c});                |
+------------------------------------------------+
|i13 : S = QQ[x,y];                              |
+------------------------------------------------+
|i14 : changeRing(H,S,{x,y,y})                   |
|                                                |
|o14 = HyperGraph{"edges" => {{y}}    }          |
|                 "ring" => S                    |
|                 "vertices" => {x, y}           |
|                                                |
|o14 : HyperGraph                                |
+------------------------------------------------+
|i15 : changeRing(H,S,{x,y,y},MaximalEdges=>true)|
|                                                |
|o15 = HyperGraph{"edges" => {{x, y}} }          |
|                 "ring" => S                    |
|                 "vertices" => {x, y}           |
|                                                |
|o15 : HyperGraph                                |
+------------------------------------------------+

By default, changeRing uses minimal edges that appear after substitution to
construct its output. The optional argument MaximalEdges,
allows one to get the maximal edges instead.

See also
========

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

Ways to use changeRing:
=======================

  * "changeRing(HyperGraph,PolynomialRing,List)"

For the programmer
==================

The object changeRing, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1927:0.

changeRing(...,MaximalEdges=>...) -- optional argument for changeRing
*********************************************************************

  * Usage:
        G = changeRing(H,R,L,MaximalEdges=>true)

Description
===========

This is an option to tell changeRing, whether to make a
hypergraph using maximal or minimal edges after substitution for the variables.

Functions with optional argument named MaximalEdges:
====================================================

  * changeRing(...,MaximalEdges=>...)
    -- optional argument
    for changeRing

Further information
===================

  * Default value: false (Macaulay2Doc),
  * Function: changeRing, -- replaces vertices with variables
    of a different ring
  * Option key: MaximalEdges, -- optional argument for
    changeRing
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4296:0.

chromaticNumber -- computes the chromatic number of a hypergraph
****************************************************************

  * Usage:
        c = chromaticNumber H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * c, an integer (Macaulay2Doc), the chromatic number of H

Description
===========

Returns the chromatic number, the smallest number of colors needed to color the
vertices of a graph.  This method is based upon a result of Francisco-Ha-Van
Tuyl that relates the chromatic number to an ideal membership problem.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : c4 = cycle(S,4) -- 4-cycle; chromatic number = 2                        |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, d}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : c5 = cycle(S,5) -- 5-cycle; chromatic number = 3                        |
|                                                                             |
|o3 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {a, e}}}              |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o3 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i4 : k6 = completeGraph S  -- complete graph on 6 vertices; chromatic number |
|                                                                             |
|o4 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {b, c}, {b, d |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
| = 6                                                                         |
|                                                                             |
|}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}, {d, e}, {d, f}, {e, f}}}          |
+-----------------------------------------------------------------------------+
|i5 : chromaticNumber c4                                                      |
|                                                                             |
|o5 = 2                                                                       |
+-----------------------------------------------------------------------------+
|i6 : chromaticNumber c5                                                      |
|                                                                             |
|o6 = 3                                                                       |
+-----------------------------------------------------------------------------+
|i7 : chromaticNumber k6                                                      |
|                                                                             |
|o7 = 6                                                                       |
+-----------------------------------------------------------------------------+

Caveat
======

This method should not be used with a hypergraph that has an edge of
cardinality one since no coloring is possible.

Ways to use chromaticNumber:
============================

  * "chromaticNumber(HyperGraph)"

For the programmer
==================

The object chromaticNumber, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1963:0.

cliqueComplex -- returns the clique complex of a graph
******************************************************

  * Usage:
        D = cliqueComplex G
  * Inputs:
      * G, a graph,
  * Outputs:
      * D, an abstract simplicial complex (SimplicialComplexes),
        the clique complex of G

Description
===========

This function returns the clique complex of a graph $G$.  This is the
simplicial complex whose faces correspond to the cliques in the graph.  That
is, $F = \{x_{i_1},...,x_{i_s}\}$ is a face of the clique complex of $G$ if and
only if the induced graph on $\{x_{i_1},...,x_{i_s}\}$ is a clique of $G$.

+-----------------------------------------------------------------------+
|i1 : R = QQ[w,x,y,z];                                                  |
+-----------------------------------------------------------------------+
|i2 : e = graph {w*x,w*y,x*y,y*z}  -- clique on {w,x,y} and {y,z}       |
|                                                                       |
|o2 = Graph{"edges" => {{w, x}, {w, y}, {x, y}, {y, z}}}                |
|           "ring" => R                                                 |
|           "vertices" => {w, x, y, z}                                  |
|                                                                       |
|o2 : Graph                                                             |
+-----------------------------------------------------------------------+
|i3 : cliqueComplex e  -- max facets {w,x,y} and {y,z}                  |
|                                                                       |
|o3 = simplicialComplex | yz wxy |                                      |
|                                                                       |
|o3 : SimplicialComplex                                                 |
+-----------------------------------------------------------------------+
|i4 : g = completeGraph R                                               |
|                                                                       |
|o4 = Graph{"edges" => {{w, x}, {w, y}, {w, z}, {x, y}, {x, z}, {y, z}}}|
|           "ring" => R                                                 |
|           "vertices" => {w, x, y, z}                                  |
|                                                                       |
|o4 : Graph                                                             |
+-----------------------------------------------------------------------+
|i5 : cliqueComplex g                                                   |
|                                                                       |
|o5 = simplicialComplex | wxyz |                                        |
|                                                                       |
|o5 : SimplicialComplex                                                 |
+-----------------------------------------------------------------------+

See also
========

  * cliqueNumber -- computes the clique number of a graph
  * getCliques -- returns cliques in a graph
  * getMaxCliques -- returns maximal cliques in a graph

Ways to use cliqueComplex:
==========================

  * "cliqueComplex(Graph)"

For the programmer
==================

The object cliqueComplex, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2000:0.

cliqueNumber -- computes the clique number of a graph
*****************************************************

  * Usage:
        c = cliqueNumber G
  * Inputs:
      * G, a graph,
  * Outputs:
      * c, an integer (Macaulay2Doc), the clique number of G

Description
===========

cliqueNumber returns the clique number of a graph, the size of the largest
clique contained in the graph.  This number is also related to the dimension of
the clique complex of the graph.

+-------------------------------------------------------+
|i1 : R = QQ[a..d];                                     |
+-------------------------------------------------------+
|i2 : cliqueNumber completeGraph R                      |
|                                                       |
|o2 = 4                                                 |
+-------------------------------------------------------+
|i3 : G = graph({a*b,b*c,a*c,a*d})                      |
|                                                       |
|o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {a, d}}}|
|           "ring" => R                                 |
|           "vertices" => {a, b, c, d}                  |
|                                                       |
|o3 : Graph                                             |
+-------------------------------------------------------+
|i4 : cliqueNumber G                                    |
|                                                       |
|o4 = 3                                                 |
+-------------------------------------------------------+
|i5 : dim cliqueComplex G + 1 == cliqueNumber G         |
|                                                       |
|o5 = true                                              |
+-------------------------------------------------------+

See also
========

  * cliqueComplex -- returns the clique complex of a
    graph
  * getCliques -- returns cliques in a graph
  * getMaxCliques -- returns maximal cliques in a graph

Ways to use cliqueNumber:
=========================

  * "cliqueNumber(Graph)"

For the programmer
==================

The object cliqueNumber, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2037:0.

complementGraph -- returns the complement of a graph or hypergraph
******************************************************************

  * Usage:
        g = complementGraph G
        h = complementGraph H
  * Inputs:
      * G, a graph,
      * H, a hypergraph,
  * Outputs:
      * g, a graph, the complement of G, whose edges are the set
        of edges not in G
      * h, a hypergraph, the complement of H, whose edge set
        is found by taking the complement of each edge of H in the vertex set

Description
===========

The function complementGraph finds the complement of a graph and hypergraph.
Note that this function behaves differently depending upon the type of input.
When applied to a graph, complementGraph returns the graph whose edge set is
the set of edges not in G. When applied to a hypergraph, the edge set is found
by taking the complement of each edge of H in the vertex set.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e];                                                      |
+-----------------------------------------------------------------------------+
|i2 : c5 = graph {a*b,b*c,c*d,d*e,e*a}; -- graph of the 5-cycle               |
+-----------------------------------------------------------------------------+
|i3 : complementGraph c5 -- the graph complement of the 5-cycle               |
|                                                                             |
|o3 = Graph{"edges" => {{a, c}, {b, e}, {b, d}, {c, e}, {a, d}}}              |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o3 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i4 : c5hypergraph = hyperGraph c5 -- the 5-cycle, but viewed as a hypergraph |
|                                                                             |
|o4 = HyperGraph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}         |
|                "ring" => R                                                  |
|                "vertices" => {a, b, c, d, e}                                |
|                                                                             |
|o4 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i5 : complementGraph c5hypergraph                                            |
|                                                                             |
|o5 = HyperGraph{"edges" => {{c, d, e}, {a, d, e}, {a, b, e}, {b, c, d}, {a,  |
|                "ring" => R                                                  |
|                "vertices" => {a, b, c, d, e}                                |
|                                                                             |
|o5 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|b, c}}}                                                                      |
+-----------------------------------------------------------------------------+

Caveat
======

Notice that complementGraph works differently on graphs versus hypergraphs.

Ways to use complementGraph:
============================

  * "complementGraph(Graph)"
  * "complementGraph(HyperGraph)"

For the programmer
==================

The object complementGraph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2079:0.

completeGraph -- returns a complete graph
*****************************************

  * Usage:
        K = completeGraph R
        K = completeGraph(R,n)
        K = completeGraph L
  * Inputs:
      * R, a ring (Macaulay2Doc),
      * n, an integer (Macaulay2Doc), number of variables to use
      * L, a list (Macaulay2Doc), of vertices to make into a
        complete graph
  * Outputs:
      * K, a graph, a complete graph on the vertices in L or on
        the variables of R

Description
===========

This function returns a special graph, the complete graph.  The input specifies
a set of vertices that will have the property that every vertex is adjacent to
every other vertex.  Non-specified vertices are treated as isolated vertices.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e];                                                      |
+-----------------------------------------------------------------------------+
|i2 : completeGraph R                                                         |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|e}, {c, d}, {c, e}, {d, e}}}                                                 |
+-----------------------------------------------------------------------------+
|i3 : completeGraph(R,3)                                                      |
|                                                                             |
|o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}}}                              |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o3 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i4 : completeGraph {a,c,e}                                                   |
|                                                                             |
|o4 = Graph{"edges" => {{a, c}, {a, e}, {c, e}}}                              |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o4 : Graph                                                                   |
+-----------------------------------------------------------------------------+

See also
========

  * completeMultiPartite -- returns a complete
    multipartite graph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use completeGraph:
==========================

  * "completeGraph(List)"
  * "completeGraph(Ring)"
  * "completeGraph(Ring,ZZ)"

For the programmer
==================

The object completeGraph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2119:0.

completeMultiPartite -- returns a complete multipartite graph
*************************************************************

  * Usage:
        K = completeMultiPartite(R,n,m)
        K = completeMultiPartite(R,L)
  * Inputs:
      * R, a ring (Macaulay2Doc),
      * n, an integer (Macaulay2Doc), number of partitions
      * m, an integer (Macaulay2Doc), size of each partition
      * L, a list (Macaulay2Doc), of integers giving the size of
        each partition, or a list of partitions that are lists of variables
  * Outputs:
      * K, a graph, the complete multipartite graph on the given
        partitions

Description
===========

A complete multipartite graph is a graph with a partition of the vertices such
that every pair of vertices, not both from the same partition, is an edge of
the graph. The partitions can be specified by their number and size, by a list
of sizes, or by an explicit partition of the variables. Not all variables of
the ring need to be used.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a,b,c,x,y,z];                                                    |
+-----------------------------------------------------------------------------+
|i2 : completeMultiPartite(R,2,3)                                             |
|                                                                             |
|o2 = Graph{"edges" => {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}, {c,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, x, y, z}                                  |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|x}, {c, y}, {c, z}}}                                                         |
+-----------------------------------------------------------------------------+
|i3 : completeMultiPartite(R,{2,4})                                           |
|                                                                             |
|o3 = Graph{"edges" => {{a, c}, {a, x}, {a, y}, {a, z}, {b, c}, {b, x}, {b,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, x, y, z}                                  |
|                                                                             |
|o3 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|y}, {b, z}}}                                                                 |
+-----------------------------------------------------------------------------+
|i4 : completeMultiPartite(R,{{a,b,c,x},{y,z}})                               |
|                                                                             |
|o4 = Graph{"edges" => {{a, y}, {a, z}, {b, y}, {b, z}, {c, y}, {c, z}, {x,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, x, y, z}                                  |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|y}, {x, z}}}                                                                 |
+-----------------------------------------------------------------------------+

When n is the number of variables and M = 1, we recover the complete graph.

+-----------------------------------------------------------------------------+
|i5 : R = QQ[a,b,c,d,e];                                                      |
+-----------------------------------------------------------------------------+
|i6 : t1 = completeMultiPartite(R,5,1)                                        |
|                                                                             |
|o6 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o6 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|e}, {c, d}, {c, e}, {d, e}}}                                                 |
+-----------------------------------------------------------------------------+
|i7 : t2 = completeGraph R                                                    |
|                                                                             |
|o7 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o7 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|e}, {c, d}, {c, e}, {d, e}}}                                                 |
+-----------------------------------------------------------------------------+
|i8 : t1 == t2                                                                |
|                                                                             |
|o8 = true                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * completeGraph -- returns a complete graph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use completeMultiPartite:
=================================

  * "completeMultiPartite(Ring,List)"
  * "completeMultiPartite(Ring,ZZ,ZZ)"

For the programmer
==================

The object completeMultiPartite, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2168:0.

Connected Components Tutorial -- clarifying the difference between graph and hypergraph components
**************************************************************************************************

In this tutorial, we discuss the various methods that deal with connected
components of graphs and hypergraphs. Our main objective is to make a
distinction between the two different definitions of connected components that
are used in the EdgeIdeals, package.

A vertex of a (hyper)graph H said to be an isolated vertex if it is not
contained in any edge of H. In particular, if a vertex of H is contained in a
edge of size one then it is not considered isolated.

+---------------------------------+
|i1 : R = QQ[u,v,x,y,z];          |
+---------------------------------+
|i2 : H = hyperGraph({{u,v},{x}});|
+---------------------------------+
|i3 : isolatedVertices H          |
|                                 |
|o3 = {y, z}                      |
|                                 |
|o3 : List                        |
+---------------------------------+

Graph Components. A connected component of a graph is any maximal set of
vertices which are pairwise connected by a (possibly trivial) path. The most
important part of this definition is that isolated vertices count as connected
components.

The following methods use this definition of a connected component:
connectedGraphComponents,
numConnectedGraphComponents, and
isConnectedGraph.

Hypergraph Components. A connected component of a hypergraph is any maximal set
of vertices which are pairwise connected by a non-trivial path. Here isolated
vertices do not count as connected components.

The following methods use the hypergraph definition of a connected component:
connectedComponents (SimplicialComplexes),
see
numConnectedComponents, and isConnected.

The next example uses all of these methods on a graph to illustrate the
difference between the two definitions.

+----------------------------------+
|i4 : R = QQ[u,v,x,y,z];           |
+----------------------------------+
|i5 : G = graph({{x,y},{y,z}});    |
+----------------------------------+
|i6 : isolatedVertices G           |
|                                  |
|o6 = {u, v}                       |
|                                  |
|o6 : List                         |
+----------------------------------+
|i7 : connectedGraphComponents G   |
|                                  |
|o7 = {{u}, {v}, {x, y, z}}        |
|                                  |
|o7 : List                         |
+----------------------------------+
|i8 : numConnectedGraphComponents G|
|                                  |
|o8 = 3                            |
+----------------------------------+
|i9 : isConnectedGraph G           |
|                                  |
|o9 = false                        |
+----------------------------------+
|i10 : connectedComponents G       |
|                                  |
|o10 = {{x, y, z}}                 |
|                                  |
|o10 : List                        |
+----------------------------------+
|i11 : numConnectedComponents G    |
|                                  |
|o11 = 1                           |
+----------------------------------+
|i12 : isConnected G               |
|                                  |
|o12 = true                        |
+----------------------------------+

See also
========

  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex
  * connectedGraphComponents -- returns the
    connected components of a graph
  * isConnected -- determines if a (hyper)graph is
    connected
  * isConnectedGraph -- determines if a graph is
    connected
  * isolatedVertices -- returns all vertices not
    contained in any edge
  * numConnectedComponents -- returns the number
    of connected components in a (hyper)graph
  * numConnectedGraphComponents -- returns
    the number of connected components in a graph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1422:0.

connectedComponents -- returns the connected components of a hypergraph
***********************************************************************

  * Usage:
        L = connectedComponents H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * L, a list (Macaulay2Doc), of lists of vertices. Each list
        of vertices is a connected component of H.

Description
===========

This function returns the connected components of a hypergraph. A connected
component of a hypergraph is any maximal set of vertices which are pairwise
connected by a non-trivial path. Isolated vertices, which are those not
appearing in any edge, do not appear in any connected components. This is in
contrast to connectedGraphComponents, in which
isolated vertices form their own connected components. See the Connected Components Tutorial,
for more information.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..l];                                                           |
+-----------------------------------------------------------------------------+
|i2 : H = hyperGraph {a*b*c, c*d, d*e*f, h*i, i*j, l}                         |
|                                                                             |
|o2 = HyperGraph{"edges" => {{a, b, c}, {c, d}, {d, e, f}, {h, i}, {i, j},    |
|                "ring" => R                                                  |
|                "vertices" => {a, b, c, d, e, f, g, h, i, j, k, l}           |
|                                                                             |
|o2 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|{l}}}                                                                        |
+-----------------------------------------------------------------------------+
|i3 : L = connectedComponents H                                               |
|                                                                             |
|o3 = {{a, b, c, d, e, f}, {h, i, j}, {l}}                                    |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : apply(L, C -> inducedHyperGraph(H,C))                                   |
|                                                                             |
|o4 = {HyperGraph{"edges" => {{a, b, c}, {c, d}, {d, e, f}}},                 |
|                 "ring" => QQ[a..f]                                          |
|                 "vertices" => {a, b, c, d, e, f}                            |
|     ------------------------------------------------------------------------|
|     HyperGraph{"edges" => {{h, i}, {i, j}}}, HyperGraph{"edges" => {{l}} }} |
|                "ring" => QQ[h..j]                       "ring" => QQ[l]     |
|                "vertices" => {h, i, j}                  "vertices" => {l}   |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+

In the following example, hypergraph H contains the isolated vertex d and the
vertex c which is in an edge of size one. Notice that d does not appear in any
connected component while c does.

+-------------------------------------------+
|i5 : R = QQ[a,b,c,d];                      |
+-------------------------------------------+
|i6 : H = hyperGraph {a*b, c}               |
|                                           |
|o6 = HyperGraph{"edges" => {{a, b}, {c}}  }|
|                "ring" => R                |
|                "vertices" => {a, b, c, d} |
|                                           |
|o6 : HyperGraph                            |
+-------------------------------------------+
|i7 : connectedComponents H                 |
|                                           |
|o7 = {{a, b}, {c}}                         |
|                                           |
|o7 : List                                  |
+-------------------------------------------+
|i8 : isolatedVertices H                    |
|                                           |
|o8 = {d}                                   |
|                                           |
|o8 : List                                  |
+-------------------------------------------+

See also
========

  * Connected Components Tutorial, --
    clarifying the difference between graph and hypergraph components
  * connectedGraphComponents -- returns the
    connected components of a graph
  * isConnected -- determines if a (hyper)graph is
    connected
  * numConnectedComponents -- returns the number
    of connected components in a (hyper)graph
  * isolatedVertices -- returns all vertices not
    contained in any edge

Ways to use connectedComponents:
================================

  * "connectedComponents(HyperGraph)"
  * connectedComponents(SimplicialComplex) (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex

For the programmer
==================

The object connectedComponents (SimplicialComplexes),
is a
method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2219:0.

connectedGraphComponents -- returns the connected components of a graph
***********************************************************************

  * Usage:
        L = connectedGraphComponents G
  * Inputs:
      * G, a hypergraph,
  * Outputs:
      * L, a list (Macaulay2Doc), of lists of vertices. Each list
        of vertices is a connected component of G.

Description
===========

This function returns the connected components of a graph. A connected
component of a graph is any maximal set of vertices which are pairwise
connected by a (possibly trivial) path. Isolated vertices, which are those not
appearing in any edge, form their own connected components. This is in contrast
to connectedComponents (SimplicialComplexes),
in which
isolated vertices do not appear in any connected components. See the
Connected Components Tutorial, for more
information.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..k];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = graph {a*b,b*c,c*d,a*d,f*g,h*i,j*k,h*k}                             |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}, {f, g}, {h, i}, {h,   |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d, e, f, g, h, i, j, k}                   |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|k}, {j, k}}}                                                                 |
+-----------------------------------------------------------------------------+
|i3 : L = connectedGraphComponents G                                          |
|                                                                             |
|o3 = {{e}, {a, b, c, d}, {f, g}, {h, i, j, k}}                               |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+

In the following example, graph G contains the isolated vertex d. Notice that d
appears in its own connected component and hence G is not connected.

+---------------------------------------+
|i4 : R = QQ[a,b,c,d];                  |
+---------------------------------------+
|i5 : G = graph {a*b, b*c}              |
|                                       |
|o5 = Graph{"edges" => {{a, b}, {b, c}}}|
|           "ring" => R                 |
|           "vertices" => {a, b, c, d}  |
|                                       |
|o5 : Graph                             |
+---------------------------------------+
|i6 : connectedGraphComponents G        |
|                                       |
|o6 = {{d}, {a, b, c}}                  |
|                                       |
|o6 : List                              |
+---------------------------------------+
|i7 : isolatedVertices G                |
|                                       |
|o7 = {d}                               |
|                                       |
|o7 : List                              |
+---------------------------------------+
|i8 : isConnectedGraph G                |
|                                       |
|o8 = false                             |
+---------------------------------------+

See also
========

  * Connected Components Tutorial, --
    clarifying the difference between graph and hypergraph components
  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex
  * isConnectedGraph -- determines if a graph is
    connected
  * numConnectedGraphComponents -- returns
    the number of connected components in a graph
  * isolatedVertices -- returns all vertices not
    contained in any edge

Ways to use connectedGraphComponents:
=====================================

  * "connectedGraphComponents(HyperGraph)"

For the programmer
==================

The object connectedGraphComponents, is a
method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2270:0.

Constructor Overview -- a summary of the many ways of making graphs and hypergraphs
***********************************************************************************

The following is separated into four sections:

  * Basic Constructors
  * Converting Types
  * Special Graphs
  * Random (Hyper)Graphs

Basic Constructors
==================

The main way of constructing Graph, and HyperGraph,
objects is to use the graph, and hyperGraph,
methods. These methods are overridden to provide many ways of
specifying edges.

For the purposes of the EdgeIdeals package, every graph and hypergraph is
associated to a ring whose variables correspond to the vertices of the
(hyper)graph. Thus, the most explicit way to make a graph or hypergraph is by
graph(PolynomialRing,List), and
hyperGraph(PolynomialRing,List).The list parameter must contain
edges which themselves are lists of variables in the ring.

+-------------------------------------------------------+
|i1 : R = QQ[x,y,z,w];                                  |
+-------------------------------------------------------+
|i2 : G = graph(R, {{x,y},{x,z},{y,z},{x,w}})           |
|                                                       |
|o2 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}|
|           "ring" => R                                 |
|           "vertices" => {x, y, z, w}                  |
|                                                       |
|o2 : Graph                                             |
+-------------------------------------------------------+
|i3 : H = hyperGraph(R, {{x,y,z},{x,w}})                |
|                                                       |
|o3 = HyperGraph{"edges" => {{x, y, z}, {x, w}}}        |
|                "ring" => R                            |
|                "vertices" => {x, y, z, w}             |
|                                                       |
|o3 : HyperGraph                                        |
+-------------------------------------------------------+

Probably the most convenient way of specifying edges is as a list of monomials.
Using the graph(List), and hyperGraph(List),
methods implicitly defines the ring of the (hyper)graph to be the ring
containing the monomials  in the List (Macaulay2Doc). The following
example gives the same hypergraphs as before.

+-------------------------------------------------------+
|i4 : R = QQ[x,y,z,w];                                  |
+-------------------------------------------------------+
|i5 : G = graph {x*y, x*z, y*z, x*w}                    |
|                                                       |
|o5 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}|
|           "ring" => R                                 |
|           "vertices" => {x, y, z, w}                  |
|                                                       |
|o5 : Graph                                             |
+-------------------------------------------------------+
|i6 : H = hyperGraph {x*y*z, x*w}                       |
|                                                       |
|o6 = HyperGraph{"edges" => {{x, y, z}, {x, w}}}        |
|                "ring" => R                            |
|                "vertices" => {x, y, z, w}             |
|                                                       |
|o6 : HyperGraph                                        |
+-------------------------------------------------------+

The graph, and hyperGraph, constructors can also
be used to make (hyper)graphs from square-free monomial ideals.The minimal
generators of the ideal become the edges of the (hyper)graph. The ideal must be
generated by quadratics if the graph, constructor is used.

+-------------------------------------------------------+
|i7 : G = graph ideal(x*y, x*z, y*z, x*w)               |
|                                                       |
|o7 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}|
|           "ring" => R                                 |
|           "vertices" => {x, y, z, w}                  |
|                                                       |
|o7 : Graph                                             |
+-------------------------------------------------------+

Converting Types
================

In this section, we will see how to convert between SimplicialComplex (SimplicialComplexes),
es and HyperGraph,s,
as well as between Graph,s and HyperGraph,s.

The methods simplicialComplexToHyperGraph,
and hyperGraphToSimplicialComplex,
accomplish the former conversion in the following way. In
simplicialComplexToHyperGraph, facets of the
simplicial complex become the edges of the hypergraph, while in
hyperGraphToSimplicialComplex, the edges of the
hypergraph become the facets of the new simplicial complex.

+------------------------------------------------+
|i8 : R = QQ[x,y,z,w];                           |
+------------------------------------------------+
|i9 : H = hyperGraph {x*y*z,x*w};                |
+------------------------------------------------+
|i10 : D = hyperGraphToSimplicialComplex H       |
|                                                |
|o10 = simplicialComplex | xw xyz |              |
|                                                |
|o10 : SimplicialComplex                         |
+------------------------------------------------+
|i11 : simplicialComplexToHyperGraph D           |
|                                                |
|o11 = HyperGraph{"edges" => {{x, y, z}, {x, w}}}|
|                 "ring" => R                    |
|                 "vertices" => {x, y, z, w}     |
|                                                |
|o11 : HyperGraph                                |
+------------------------------------------------+

The conversion of a graph into a hypergraph and vice versa use the constructors
graph, and hyperGraph. Any graph can be
converted to a hyperGraph, but when a hyperGraph is converted into a graph, a
check is run to ensure that the edges are all of size two. An error will be
produced if this is not the case.

+-------------------------------------------------------------+
|i12 : R = QQ[x,y,z,w];                                       |
+-------------------------------------------------------------+
|i13 : G = graph {x*y, x*z, y*z, x*w};                        |
+-------------------------------------------------------------+
|i14 : H = hyperGraph G                                       |
|                                                             |
|o14 = HyperGraph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}|
|                 "ring" => R                                 |
|                 "vertices" => {x, y, z, w}                  |
|                                                             |
|o14 : HyperGraph                                             |
+-------------------------------------------------------------+
|i15 : graph H                                                |
|                                                             |
|o15 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}     |
|            "ring" => R                                      |
|            "vertices" => {x, y, z, w}                       |
|                                                             |
|o15 : Graph                                                  |
+-------------------------------------------------------------+

Since the Graph, type is a subclass of HyperGraph,
any method that takes a HyperGraph, will also
work on Graph,s. So the conversion from graph to hypergraph is
seldom needed; it is only needed when a method works differently on graphs than
on hypergraphs (see complementGraph, for an example).

On the other hand, the conversion from hypergraph to graph is very important as
many methods are only defined on graphs. In the following example, we use the
isChordal, method which only applies to graphs and hence
necessitates a conversion of types.

+-------------------------------------------------------------+
|i16 : R = QQ[x,y,z,w];                                       |
+-------------------------------------------------------------+
|i17 : D = simplicialComplex {x*y, x*z, y*z, x*w};            |
+-------------------------------------------------------------+
|i18 : H = simplicialComplexToHyperGraph D                    |
|                                                             |
|o18 = HyperGraph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}|
|                 "ring" => R                                 |
|                 "vertices" => {x, y, z, w}                  |
|                                                             |
|o18 : HyperGraph                                             |
+-------------------------------------------------------------+
|i19 : G = graph H                                            |
|                                                             |
|o19 = Graph{"edges" => {{x, y}, {x, z}, {y, z}, {x, w}}}     |
|            "ring" => R                                      |
|            "vertices" => {x, y, z, w}                       |
|                                                             |
|o19 : Graph                                                  |
+-------------------------------------------------------------+
|i20 : isChordal G                                            |
|                                                             |
|o20 = true                                                   |
+-------------------------------------------------------------+

Special Graphs
==============

In addition to the more general constructors, there a number of methods which
produce certain special graphs.

Cycles can be constructed using cycle, which, depending on the
parameters, uses all or some of the variables in the ring to define a graph
cycle.

+--------------------------------------------------------+
|i21 : R = QQ[x,y,z,w];                                  |
+--------------------------------------------------------+
|i22 : cycle R                                           |
|                                                        |
|o22 = Graph{"edges" => {{x, y}, {y, z}, {z, w}, {x, w}}}|
|            "ring" => R                                 |
|            "vertices" => {x, y, z, w}                  |
|                                                        |
|o22 : Graph                                             |
+--------------------------------------------------------+
|i23 : cycle(R,3)                                        |
|                                                        |
|o23 = Graph{"edges" => {{x, y}, {y, z}, {x, z}}}        |
|            "ring" => R                                 |
|            "vertices" => {x, y, z, w}                  |
|                                                        |
|o23 : Graph                                             |
+--------------------------------------------------------+
|i24 : cycle {x,y,w}                                     |
|                                                        |
|o24 = Graph{"edges" => {{x, y}, {y, w}, {x, w}}}        |
|            "ring" => R                                 |
|            "vertices" => {x, y, z, w}                  |
|                                                        |
|o24 : Graph                                             |
+--------------------------------------------------------+

Anti-Cycles, the graph complements of cycles, can be constructed using
antiCycle, which takes parameters similar to those of cycle.

+----------------------------------------+
|i25 : R = QQ[x,y,z,w];                  |
+----------------------------------------+
|i26 : antiCycle R                       |
|                                        |
|o26 = Graph{"edges" => {{x, z}, {y, w}}}|
|            "ring" => R                 |
|            "vertices" => {x, y, z, w}  |
|                                        |
|o26 : Graph                             |
+----------------------------------------+

Complete graphs can be constructed using completeGraph,
which defines a graph with every possible edge between a given set a vertices.

+------------------------------------------------------------------------+
|i27 : R = QQ[x,y,z,w];                                                  |
+------------------------------------------------------------------------+
|i28 : completeGraph R                                                   |
|                                                                        |
|o28 = Graph{"edges" => {{x, y}, {x, z}, {x, w}, {y, z}, {y, w}, {z, w}}}|
|            "ring" => R                                                 |
|            "vertices" => {x, y, z, w}                                  |
|                                                                        |
|o28 : Graph                                                             |
+------------------------------------------------------------------------+
|i29 : completeGraph(R,3)                                                |
|                                                                        |
|o29 = Graph{"edges" => {{x, y}, {x, z}, {y, z}}}                        |
|            "ring" => R                                                 |
|            "vertices" => {x, y, z, w}                                  |
|                                                                        |
|o29 : Graph                                                             |
+------------------------------------------------------------------------+
|i30 : completeGraph {x,y,w}                                             |
|                                                                        |
|o30 = Graph{"edges" => {{x, y}, {x, w}, {y, w}}}                        |
|            "ring" => R                                                 |
|            "vertices" => {x, y, z, w}                                  |
|                                                                        |
|o30 : Graph                                                             |
+------------------------------------------------------------------------+

Complete multipartite graphs can be constructed using
completeMultiPartite, which defines a graph with every
possible edge between certain partitions of the vertices. See
completeMultiPartite, for more details.

+--------------------------------------------------------+
|i31 : R = QQ[a,b,x,y];                                  |
+--------------------------------------------------------+
|i32 : completeMultiPartite(R,2,2)                       |
|                                                        |
|o32 = Graph{"edges" => {{a, x}, {a, y}, {b, x}, {b, y}}}|
|            "ring" => R                                 |
|            "vertices" => {a, b, x, y}                  |
|                                                        |
|o32 : Graph                                             |
+--------------------------------------------------------+

Random (Hyper)Graphs
====================

Three methods are provided for the construction of random (hyper)graphs.

  * randomGraph -- returns a random graph
  * randomUniformHyperGraph -- returns a random
    uniform hypergraph
  * randomHyperGraph -- returns a random hypergraph

Each method allows you to specify the number of edges desired. For the random
hypergraph methods, the sizes of the edges must also be specified.

+-----------------------------------------------------+
|i33 : R = QQ[x,y,z,u,v];                             |
+-----------------------------------------------------+
|i34 : randomGraph(R,3)                               |
|                                                     |
|o34 = Graph{"edges" => {{z, u}, {x, u}, {x, v}}}     |
|            "ring" => R                              |
|            "vertices" => {x, y, z, u, v}            |
|                                                     |
|o34 : Graph                                          |
+-----------------------------------------------------+
|i35 : randomUniformHyperGraph(R,2,3)                 |
|                                                     |
|o35 = HyperGraph{"edges" => {{y, u}, {x, u}, {x, y}}}|
|                 "ring" => R                         |
|                 "vertices" => {x, y, z, u, v}       |
|                                                     |
|o35 : HyperGraph                                     |
+-----------------------------------------------------+
|i36 : randomHyperGraph(R,{3,2,1})                    |
|                                                     |
|o36 = HyperGraph{"edges" => {{x, y, z}, {z, u}, {v}}}|
|                 "ring" => R                         |
|                 "vertices" => {x, y, z, u, v}       |
|                                                     |
|o36 : HyperGraph                                     |
+-----------------------------------------------------+

The randomHyperGraph, method is not guaranteed to
return a hypergraph; sometimes it returns null. Please see the documentation of
this method for more details.

See also
========

  * Extended Example -- an extended example using
    EdgeIdeals
  * Graph -- a class for graphs
  * HyperGraph -- a class for hypergraphs
  * graph -- constructor for Graph
  * hyperGraph -- constructor for HyperGraph
  * simplicialComplexToHyperGraph, --
    makes a (hyper)graph from a simplicial complex
  * hyperGraphToSimplicialComplex, --
    makes a simplicial complex from a (hyper)graph
  * cycle -- returns a graph cycle
  * antiCycle -- returns a graph of an anticycle
  * completeGraph -- returns a complete graph
  * completeMultiPartite -- returns a complete
    multipartite graph
  * randomGraph -- returns a random graph
  * randomUniformHyperGraph -- returns a random
    uniform hypergraph
  * randomHyperGraph -- returns a random hypergraph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1323:0.

coverIdeal -- creates the cover ideal of a (hyper)graph
*******************************************************

  * Usage:
        I = coverIdeal H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * I, a monomial ideal (Macaulay2Doc), the cover
        ideal of H

Description
===========

Returns the monomial ideal generated by the minimal vertex covers.  This is
also the Alexander dual of the edge ideal of the hypergraph H.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a,b,c,d,e,f];                                                    |
+-----------------------------------------------------------------------------+
|i2 : k6 = completeGraph S  -- complete graph on 6 vertices                   |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {a, f}, {b, c}, {b,   |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|d}, {b, e}, {b, f}, {c, d}, {c, e}, {c, f}, {d, e}, {d, f}, {e, f}}}         |
+-----------------------------------------------------------------------------+
|i3 : coverIdeal k6 -- each generator corresponds to a minimal vertex of k6   |
|                                                                             |
|o3 = monomialIdeal (a*b*c*d*e, a*b*c*d*f, a*b*c*e*f, a*b*d*e*f, a*c*d*e*f,   |
|     ------------------------------------------------------------------------|
|     b*c*d*e*f)                                                              |
|                                                                             |
|o3 : MonomialIdeal of S                                                      |
+-----------------------------------------------------------------------------+
|i4 : h = hyperGraph {a*b*c,c*d,d*e*f}                                        |
|                                                                             |
|o4 = HyperGraph{"edges" => {{a, b, c}, {c, d}, {d, e, f}}}                   |
|                "ring" => S                                                  |
|                "vertices" => {a, b, c, d, e, f}                             |
|                                                                             |
|o4 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i5 : coverIdeal h                                                            |
|                                                                             |
|o5 = monomialIdeal (a*d, b*d, c*d, c*e, c*f)                                 |
|                                                                             |
|o5 : MonomialIdeal of S                                                      |
+-----------------------------------------------------------------------------+
|i6 : dual coverIdeal h == edgeIdeal h                                        |
|                                                                             |
|o6 = true                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * dual (Macaulay2Doc) -- dual module or map
  * edgeIdeal -- creates the edge ideal of a (hyper)graph
  * vertexCoverNumber -- find the vertex covering
    number of a (hyper)graph
  * vertexCovers -- list the minimal vertex covers of a
    (hyper)graph

Ways to use coverIdeal:
=======================

  * "coverIdeal(HyperGraph)"

For the programmer
==================

The object coverIdeal, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2307:0.

cycle -- returns a graph cycle
******************************

  * Usage:
        C = cycle R
        C = cycle(R,n)
        C = cycle L
  * Inputs:
      * R, a ring (Macaulay2Doc),
      * n, an integer (Macaulay2Doc), length of cycle
      * L, a list (Macaulay2Doc), of vertices to make into a cycle
        in the order provided
  * Outputs:
      * C, a graph, a cycle on the vertices in L or on the
        variables of R.

Description
===========

Give a list of vertices (perhaps in some specified order), this function
returns the graph of the cycle on those vertices, using the order given or the
internal ordering of the vertices (Polyhedra).  Unspecified
vertices are treated as isolated vertices.

+---------------------------------------------------------------+
|i1 : R = QQ[a,b,c,d,e];                                        |
+---------------------------------------------------------------+
|i2 : cycle R                                                   |
|                                                               |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {a, e}}}|
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o2 : Graph                                                     |
+---------------------------------------------------------------+
|i3 : cycle(R,3)                                                |
|                                                               |
|o3 = Graph{"edges" => {{a, b}, {b, c}, {a, c}}}                |
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o3 : Graph                                                     |
+---------------------------------------------------------------+
|i4 : cycle {e,c,d,b}                                           |
|                                                               |
|o4 = Graph{"edges" => {{c, e}, {c, d}, {b, d}, {b, e}}}        |
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o4 : Graph                                                     |
+---------------------------------------------------------------+
|i5 : R = QQ[a,c,d,b,e];-- variables given different order      |
+---------------------------------------------------------------+
|i6 : cycle R                                                   |
|                                                               |
|o6 = Graph{"edges" => {{a, c}, {c, d}, {d, b}, {b, e}, {a, e}}}|
|           "ring" => R                                         |
|           "vertices" => {a, c, d, b, e}                       |
|                                                               |
|o6 : Graph                                                     |
+---------------------------------------------------------------+

See also
========

  * antiCycle -- returns a graph of an anticycle
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use cycle:
==================

  * "cycle(List)"
  * "cycle(Ring)"
  * "cycle(Ring,ZZ)"

For the programmer
==================

The object cycle, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2349:0.

degreeVertex -- returns the degree of a vertex
**********************************************

  * Usage:
        d = degreeVertex(H,n)
        d = degreeVertex(H,V)
  * Inputs:
      * H, a hypergraph,
      * n, an integer (Macaulay2Doc), the index of a vertex
      * V, a ring element (Macaulay2Doc), a vertex/variable
        of the HyperGraph
  * Outputs:
      * d, an integer (Macaulay2Doc), the degree of vertex V (or
        vertex number n)

Description
===========

The degree of a vertex in a (hyper)graph is the number of edges that contain
the vertex. In a graph, the degree is also the number of elements in the
neighbor set of a vertex.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a,b,c,d,e];                                                      |
+-----------------------------------------------------------------------------+
|i2 : k5 = completeGraph S                                                    |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {a, e}, {b, c}, {b, d}, {b,   |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|e}, {c, d}, {c, e}, {d, e}}}                                                 |
+-----------------------------------------------------------------------------+
|i3 : dv = degreeVertex(k5,a)                                                 |
|                                                                             |
|o3 = 4                                                                       |
+-----------------------------------------------------------------------------+
|i4 : n = neighbors(k5,a)                                                     |
|                                                                             |
|o4 = {b, c, d, e}                                                            |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+
|i5 : #n == dv                                                                |
|                                                                             |
|o5 = true                                                                    |
+-----------------------------------------------------------------------------+
|i6 : degreeVertex(k5,2)                                                      |
|                                                                             |
|o6 = 4                                                                       |
+-----------------------------------------------------------------------------+
|i7 : h = hyperGraph {a*b*c,c*d,a*d*e,b*e,c*e}                                |
|                                                                             |
|o7 = HyperGraph{"edges" => {{a, b, c}, {c, d}, {b, e}, {c, e}, {a, d, e}}}   |
|                "ring" => S                                                  |
|                "vertices" => {a, b, c, d, e}                                |
|                                                                             |
|o7 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i8 : degreeVertex(h,a)                                                       |
|                                                                             |
|o8 = 2                                                                       |
+-----------------------------------------------------------------------------+
|i9 : degreeVertex(h,2) -- degree of c                                        |
|                                                                             |
|o9 = 3                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * neighbors -- returns the neighbors of a vertex or list of
    vertices
  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

Ways to use degreeVertex:
=========================

  * "degreeVertex(HyperGraph,RingElement)"
  * "degreeVertex(HyperGraph,ZZ)"

For the programmer
==================

The object degreeVertex, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2391:0.

deleteEdges -- returns the (hyper)graph with specified edges removed
********************************************************************

  * Usage:
        h = deleteEdges(H, S)
  * Inputs:
      * H, a hypergraph,
      * S, a list (Macaulay2Doc), a subset of the edges of the
        graph or hypergraph
  * Outputs:
      * h, a hypergraph, the hypergraph with edges in S
        removed

Description
===========

This function enables the user to remove specified edges from a hypergraph to
form a subhypergraph.

+---------------------------------------------------------------+
|i1 : S = QQ[a,b,c,d,e];                                        |
+---------------------------------------------------------------+
|i2 : g = 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 : T = {{a,b},{d,e}}                                         |
|                                                               |
|o3 = {{a, b}, {d, e}}                                          |
|                                                               |
|o3 : List                                                      |
+---------------------------------------------------------------+
|i4 : gprime = deleteEdges (g,T)                                |
|                                                               |
|o4 = HyperGraph{"edges" => {{b, c}, {a, e}, {c, d}}}           |
|                "ring" => S                                    |
|                "vertices" => {a, b, c, d, e}                  |
|                                                               |
|o4 : HyperGraph                                                |
+---------------------------------------------------------------+
|i5 : h = hyperGraph {a*b*c,c*d*e,a*e}                          |
|                                                               |
|o5 = HyperGraph{"edges" => {{a, b, c}, {a, e}, {c, d, e}}}     |
|                "ring" => S                                    |
|                "vertices" => {a, b, c, d, e}                  |
|                                                               |
|o5 : HyperGraph                                                |
+---------------------------------------------------------------+
|i6 : T = edges h                                               |
|                                                               |
|o6 = {{a, b, c}, {a, e}, {c, d, e}}                            |
|                                                               |
|o6 : List                                                      |
+---------------------------------------------------------------+
|i7 : hprime = deleteEdges (h,T)                                |
|                                                               |
|o7 = HyperGraph{"edges" => {}                }                 |
|                "ring" => S                                    |
|                "vertices" => {a, b, c, d, e}                  |
|                                                               |
|o7 : HyperGraph                                                |
+---------------------------------------------------------------+

Ways to use deleteEdges:
========================

  * "deleteEdges(HyperGraph,List)"

For the programmer
==================

The object deleteEdges, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2426:0.

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

  * Usage:
        I = edgeIdeal H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * I, a monomial ideal (Macaulay2Doc), the edge ideal
        of H

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,   |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o5 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|e}, {c, d}, {c, e}, {d, e}}}                                                 |
+-----------------------------------------------------------------------------+
|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|
|                                                                             |
|o8 = HyperGraph{"edges" => {{z , z , z }, {z , z , z , z }, {z , z , z }, {z |
|                              1   2   3     2   3   4   5     4   5   6     6|
|                "ring" => S                                                  |
|                "vertices" => {z , z , z , z , z , z , z , z }               |
|                                1   2   3   4   5   6   7   8                |
|                                                                             |
|o8 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|_8}}                                                                         |
|                                                                             |
|, z , z }}}                                                                  |
|   7   8                                                                     |
+-----------------------------------------------------------------------------+
|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
========

  * coverIdeal -- creates the cover ideal of a (hyper)graph

Ways to use edgeIdeal:
======================

  * "edgeIdeal(HyperGraph)"

For the programmer
==================

The object edgeIdeal, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2478:0.

edges -- gets the edges of a (hyper)graph
*****************************************

  * Usage:
        E = edges(H)
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * E, a list (Macaulay2Doc), of the edges of H

Description
===========

This function takes a (hyper)graph, and returns the edge set of the
(hyper)graph.

+-----------------------------------------------------------------------+
|i1 : S = QQ[a..d];                                                     |
+-----------------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*a} -- the four cycle                     |
|                                                                       |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}                |
|           "ring" => S                                                 |
|           "vertices" => {a, b, c, d}                                  |
|                                                                       |
|o2 : Graph                                                             |
+-----------------------------------------------------------------------+
|i3 : edges g                                                           |
|                                                                       |
|o3 = {{a, b}, {b, c}, {a, d}, {c, d}}                                  |
|                                                                       |
|o3 : List                                                              |
+-----------------------------------------------------------------------+
|i4 : h = hyperGraph{a*b*c}                                             |
|                                                                       |
|o4 = HyperGraph{"edges" => {{a, b, c}}    }                            |
|                "ring" => S                                            |
|                "vertices" => {a, b, c, d}                             |
|                                                                       |
|o4 : HyperGraph                                                        |
+-----------------------------------------------------------------------+
|i5 : edges h                                                           |
|                                                                       |
|o5 = {{a, b, c}}                                                       |
|                                                                       |
|o5 : List                                                              |
+-----------------------------------------------------------------------+
|i6 : k4 = completeGraph S                                              |
|                                                                       |
|o6 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}}|
|           "ring" => S                                                 |
|           "vertices" => {a, b, c, d}                                  |
|                                                                       |
|o6 : Graph                                                             |
+-----------------------------------------------------------------------+
|i7 : edges k4                                                          |
|                                                                       |
|o7 = {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}                  |
|                                                                       |
|o7 : List                                                              |
+-----------------------------------------------------------------------+

See also
========

  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

Ways to use edges:
==================

  * "edges(HyperGraph)"

For the programmer
==================

The object edges, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2513:0.

Extended Example -- an extended example using EdgeIdeals
********************************************************

This is an example from the write-up of the EdgeIdeals package in the Journal
of Software for Algebra and Geometry: Macaulay 2.

At the heart of the EdgeIdeals package are two new classes that are entitled
HyperGraph, and Graph. The HyperGraph,
class can only be used to represent hypergraphs. The class
Graph, extends from HyperGraph, and inherits all of
the methods of HyperGraph. Functions have been made that
accept objects of either type as input.

In our example below, we illustrate Theorem 6.4.7 from R. Villarreal's Monomial
Algebras, which says that the independence complex of a Cohen-Macaulay
bipartite graph has a simplicial shelling. We begin by creating a graph and
verifying the Cohen-Macaulay and bipartite properties.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_3,y_1..y_3];                                              |
+-----------------------------------------------------------------------------+
|i2 : G = graph(R,{x_1*y_1,x_2*y_2,x_3*y_3, x_1*y_2,x_1*y_3,x_2*y_3})         |
|                                                                             |
|o2 = Graph{"edges" => {{x , y }, {x , y }, {x , y }, {x , y }, {x , y }, {x ,|
|                         1   1     2   2     3   3     1   2     1   3     2 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , y , y , y }                            |
|                           1   2   3   1   2   3                             |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|y }}}                                                                        |
| 3                                                                           |
+-----------------------------------------------------------------------------+
|i3 : isCM G and isBipartite G                                                |
|                                                                             |
|o3 = true                                                                    |
+-----------------------------------------------------------------------------+

When defining a (hyper)graph, the user specifies the vertex set by defining a
polynomial ring, while the edges are written as a list of square-free monomials
(there are alternative ways of listing the edges).  A (hyper)graph is stored as
a hash table which contains the list of edges, the polynomial ring, and the
list of vertices.

+----------------------------------------------------------+
|i4 : L = getGoodLeaf(G)                                   |
|                                                          |
|o4 = {x , y }                                             |
|       1   1                                              |
|                                                          |
|o4 : List                                                 |
+----------------------------------------------------------+
|i5 : degreeVertex(G,y_1)                                  |
|                                                          |
|o5 = 1                                                    |
+----------------------------------------------------------+
|i6 : H = inducedHyperGraph(G, vertices(G) - set(L))       |
|                                                          |
|o6 = HyperGraph{"edges" => {{x , y }, {x , y }, {x , y }}}|
|                              2   2     3   3     2   3   |
|                "ring" => QQ[x ..y ]                      |
|                              2   3                       |
|                "vertices" => {x , x , y , y }            |
|                                2   3   2   3             |
|                                                          |
|o6 : HyperGraph                                           |
+----------------------------------------------------------+

A Cohen-Macaulay bipartite graph must contain a leaf, which we retrieve above.
We remove the leaf, to form the induced graph, and at the same time, we
identify the vertex of degree one in the leaf.

+-------------------------------------------------------------+
|i7 : K = simplicialComplexToHyperGraph independenceComplex H;|
+-------------------------------------------------------------+
|i8 : edges K                                                 |
|                                                             |
|o8 = {{x , x }, {x , y }, {y , y }}                          |
|        2   3     3   2     2   3                            |
|                                                             |
|o8 : List                                                    |
+-------------------------------------------------------------+

Above, we formed the independence complex of H, that is, the simplicial complex
whose facets correspond to the maximal independent sets of H.  We then change
the type from a simplicial complex to a hypergraph, which we call K. Notice
that these edges give a shelling.

+---------------------------------------------------------------------------+
|i9 : use ring K;                                                           |
+---------------------------------------------------------------------------+
|i10 : A = apply(edges(K), e->append(e, y_1));                              |
+---------------------------------------------------------------------------+
|i11 : B = apply(edges inducedHyperGraph(K, {x_2,x_3}), e-> append(e, x_1));|
+---------------------------------------------------------------------------+
|i12 : shelling = join(A,B)                                                 |
|                                                                           |
|o12 = {{x , x , y }, {x , y , y }, {y , y , y }, {x , x , x }}             |
|         2   3   1     3   2   1     2   3   1     2   3   1               |
|                                                                           |
|o12 : List                                                                 |
+---------------------------------------------------------------------------+
|i13 : independenceComplex(G)                                               |
|                                                                           |
|o13 = simplicialComplex | y_1y_2y_3 x_3y_1y_2 x_2x_3y_1 x_1x_2x_3 |        |
|                                                                           |
|o13 : SimplicialComplex                                                    |
+---------------------------------------------------------------------------+

Using the method found in the proof of Theorem 6.4.7 from R. Villarreal's
Monomial Algebras, we now can form a shelling of the original independence
complex. Notice that our shelling is a permutation of the facets of the
independence complex defined from G.

See also
========

  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs
  * Graph -- a class for graphs
  * HyperGraph -- a class for hypergraphs
  * graph -- constructor for Graph
  * hyperGraph -- constructor for HyperGraph
  * isCM -- determines if a (hyper)graph is Cohen-Macaulay
  * isBipartite -- determines if a graph is bipartite
  * getGoodLeaf -- returns an edge that is a good leaf
  * degreeVertex -- returns the degree of a vertex
  * inducedHyperGraph -- returns the induced subgraph
    of a (hyper)graph
  * simplicialComplexToHyperGraph, --
    makes a (hyper)graph from a simplicial complex
  * edges -- gets the edges of a (hyper)graph
  * independenceComplex -- returns the independence
    complex of a (hyper)graph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1365:0.

getCliques -- returns cliques in a graph
****************************************

  * Usage:
        C = getCliques(G,d)
        C = getCliques G
  * Inputs:
      * G, a graph,
      * d, an integer (Macaulay2Doc), representing the size of the
        cliques desired
  * Outputs:
      * C, a list (Macaulay2Doc), of cliques of size d or, if no d
        is entered, all cliques

Description
===========

A clique of a graph is a subset of its vertices which induces a complete
subgraph. That is, a set of vertices is a clique if every pair of vertices in
the set forms an edge of the graph. This function returns all cliques of a
specified size, and if no size is given, it returns all cliques.  Note that all
the edges of the graph are considered cliques of size two.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[a..d];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = completeGraph R                                                     |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}}      |
|           "ring" => R                                                       |
|           "vertices" => {a, b, c, d}                                        |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : getCliques(G,3)                                                         |
|                                                                             |
|o3 = {{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}}                            |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : getCliques(G,4)                                                         |
|                                                                             |
|o4 = {{a, b, c, d}}                                                          |
|                                                                             |
|o4 : List                                                                    |
+-----------------------------------------------------------------------------+
|i5 : getCliques G                                                            |
|                                                                             |
|o5 = {{a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d},  |
|     ------------------------------------------------------------------------|
|     {a, c, d}, {b, c, d}, {a, b, c, d}}                                     |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * cliqueNumber -- computes the clique number of a graph

Ways to use getCliques:
=======================

  * "getCliques(Graph)"
  * "getCliques(Graph,ZZ)"

For the programmer
==================

The object getCliques, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2553:0.

getEdge -- gets the n-th edge in a (hyper)graph
***********************************************

  * Usage:
        E = getEdge(H,n)
  * Inputs:
      * H, a hypergraph,
      * n, an integer (Macaulay2Doc), an index of an edge in H
  * Outputs:
      * E, a list (Macaulay2Doc), the n-th edge of H

Description
===========

This function returns the n^{th} edge of the (hyper)graph.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : g = cycle S                                                             |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {e, f}, {a, f}}}      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e, f}                                  |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : edges g                                                                 |
|                                                                             |
|o3 = {{a, b}, {b, c}, {c, d}, {d, e}, {e, f}, {a, f}}                        |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : getEdge (g,3)  -- counting starts from 0, so the 4th element in the     |
|                                                                             |
|o4 = {d, e}                                                                  |
|                                                                             |
|o4 : List                                                                    |
|-----------------------------------------------------------------------------|
|above list                                                                   |
+-----------------------------------------------------------------------------+
|i5 : h = hyperGraph {a*b*c*d,d*e,a*f*c,a*d*f}                                |
|                                                                             |
|o5 = HyperGraph{"edges" => {{a, b, c, d}, {d, e}, {a, c, f}, {a, d, f}}}     |
|                "ring" => S                                                  |
|                "vertices" => {a, b, c, d, e, f}                             |
|                                                                             |
|o5 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i6 : getEdge (h,0) -- first edge                                             |
|                                                                             |
|o6 = {a, b, c, d}                                                            |
|                                                                             |
|o6 : List                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * edges -- gets the edges of a (hyper)graph
  * getEdgeIndex -- finds the index of an edge in a
    HyperGraph

Ways to use getEdge:
====================

  * "getEdge(HyperGraph,ZZ)"

For the programmer
==================

The object getEdge, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2588:0.

getEdgeIndex -- finds the index of an edge in a HyperGraph
**********************************************************

  * Usage:
        n = getEdgeIndex(H,E)
        n = getEdgeIndex(H,M)
  * Inputs:
      * H, a hypergraph,
      * E, a list (Macaulay2Doc), of vertices
      * M, a ring element (Macaulay2Doc), a monomial that is
        the product of vertices
  * Outputs:
      * n, an integer (Macaulay2Doc), the index of E as an edge of H.
        If E is not in H, then -1 is returned.

Description
===========

This function returns the index of the edge of the (hyper)graph, where the
ordering is determined by the internal ordering of the edges. Note that the
internal order of the edges may not be preserved by methods that change the
hypergraph (i.e., see inducedHyperGraph,
changeRing, hyperGraph(MonomialIdeal), etc.).

+-----------------------------------------------------------------------------+
|i1 : S = QQ[z_1..z_8];                                                       |
+-----------------------------------------------------------------------------+
|i2 : h = hyperGraph {z_2*z_3*z_4,z_6*z_8,z_7*z_5,z_1*z_6*z_7,z_2*z_4*z_8}    |
|                                                                             |
|o2 = HyperGraph{"edges" => {{z , z , z }, {z , z }, {z , z , z }, {z , z ,   |
|                              2   3   4     5   7     1   6   7     2   4    |
|                "ring" => S                                                  |
|                "vertices" => {z , z , z , z , z , z , z , z }               |
|                                1   2   3   4   5   6   7   8                |
|                                                                             |
|o2 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|z }, {z , z }}}                                                              |
| 8     6   8                                                                 |
+-----------------------------------------------------------------------------+
|i3 : edges h                                                                 |
|                                                                             |
|o3 = {{z , z , z }, {z , z }, {z , z , z }, {z , z , z }, {z , z }}          |
|        2   3   4     5   7     1   6   7     2   4   8     6   8            |
|                                                                             |
|o3 : List                                                                    |
+-----------------------------------------------------------------------------+
|i4 : getEdgeIndex (h,{z_2,z_4,z_8})  -- although entered last, edge is       |
|                                                                             |
|o4 = 3                                                                       |
|-----------------------------------------------------------------------------|
|internally stored in 4th spot (counting begins at 0)                         |
+-----------------------------------------------------------------------------+
|i5 : getEdge(h,3)                                                            |
|                                                                             |
|o5 = {z , z , z }                                                            |
|       2   4   8                                                             |
|                                                                             |
|o5 : List                                                                    |
+-----------------------------------------------------------------------------+
|i6 : getEdgeIndex (h,{z_1,z_2}) -- not in the edge list                      |
|                                                                             |
|o6 = -1                                                                      |
+-----------------------------------------------------------------------------+

See also
========

  * getEdge -- gets the n-th edge in a (hyper)graph
  * isEdge -- determines if an edge is in a (hyper)graph

Ways to use getEdgeIndex:
=========================

  * "getEdgeIndex(HyperGraph,List)"
  * "getEdgeIndex(HyperGraph,RingElement)"

For the programmer
==================

The object getEdgeIndex, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2630:0.

getGoodLeaf -- returns an edge that is a good leaf
**************************************************

  * Usage:
        L = getGoodLeaf(H)
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * L, a list (Macaulay2Doc), of vertices that comprise an edge
        in H that is a good leaf

Description
===========

A good leaf of a hypergraph H is an edge L whose intersections with all other
edges form a totally ordered set. It follows that L must have a free vertex,
i.e., a vertex contained in no other edges. In the graph setting, a good leaf
is an edge containing a vertex of degree one.  The notion of a good leaf was
introduced by X. Zheng in her Ph.D. thesis (2004).

+----------------------------------------------------------+
|i1 : R = QQ[a..g];                                        |
+----------------------------------------------------------+
|i2 : H = hyperGraph {a*b*c*d, b*c*d*e, c*d*f, d*g, e*f*g};|
+----------------------------------------------------------+
|i3 : getGoodLeaf(H)                                       |
|                                                          |
|o3 = {a, b, c, d}                                         |
|                                                          |
|o3 : List                                                 |
+----------------------------------------------------------+

See also
========

  * getGoodLeafIndex -- returns the index of an edge
    that is a good leaf
  * hasGoodLeaf -- determines if a HyperGraph contains a
    good leaf
  * isGoodLeaf -- determines if an edge is a good leaf

Ways to use getGoodLeaf:
========================

  * "getGoodLeaf(HyperGraph)"

For the programmer
==================

The object getGoodLeaf, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2665:0.

getGoodLeafIndex -- returns the index of an edge that is a good leaf
********************************************************************

  * Usage:
        n = getGoodLeafIndex(H)
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * n, an integer (Macaulay2Doc), the index of an edge in H of a
        good leaf. Returns -1 if H does not have a good leaf.

Description
===========

A good leaf of hypergraph H is an edge L whose intersections with all other
edges form a totally ordered set. It follows that L must have a free vertex. In
the graph setting, a good leaf is an edge containing a vertex of degree one.
The notion of a good leaf was introduced by X. Zheng in her Ph.D. thesis
(2004).

+---------------------------------------------------------------+
|i1 : R = QQ[a..g];                                             |
+---------------------------------------------------------------+
|i2 : H = hyperGraph {b*c*d*e, a*b*c*d, c*d*f, d*g, e*f*g};     |
+---------------------------------------------------------------+
|i3 : getGoodLeaf(H)                                            |
|                                                               |
|o3 = {a, b, c, d}                                              |
|                                                               |
|o3 : List                                                      |
+---------------------------------------------------------------+
|i4 : edges(H)                                                  |
|                                                               |
|o4 = {{a, b, c, d}, {b, c, d, e}, {c, d, f}, {d, g}, {e, f, g}}|
|                                                               |
|o4 : List                                                      |
+---------------------------------------------------------------+
|i5 : getGoodLeafIndex(H)                                       |
|                                                               |
|o5 = 0                                                         |
+---------------------------------------------------------------+

See also
========

  * getGoodLeaf -- returns an edge that is a good leaf
  * hasGoodLeaf -- determines if a HyperGraph contains a
    good leaf
  * isGoodLeaf -- determines if an edge is a good leaf

Ways to use getGoodLeafIndex:
=============================

  * "getGoodLeafIndex(HyperGraph)"

For the programmer
==================

The object getGoodLeafIndex, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2702:0.

getMaxCliques -- returns maximal cliques in a graph
***************************************************

  * Usage:
        C = getMaxCliques G
  * Inputs:
      * G, a graph,
  * Outputs:
      * C, a list (Macaulay2Doc), of cliques of maximal size
        contained in G

Description
===========

This function returns all cliques of maximal size in a graph as a list of
lists. For more details, see getCliques.

+-----------------------------------------------------------------------+
|i1 : R = QQ[a..d];                                                     |
+-----------------------------------------------------------------------+
|i2 : G = completeGraph R                                               |
|                                                                       |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}}}|
|           "ring" => R                                                 |
|           "vertices" => {a, b, c, d}                                  |
|                                                                       |
|o2 : Graph                                                             |
+-----------------------------------------------------------------------+
|i3 : getMaxCliques G                                                   |
|                                                                       |
|o3 = {{a, b, c, d}}                                                    |
|                                                                       |
|o3 : List                                                              |
+-----------------------------------------------------------------------+
|i4 : H = graph({a*b,b*c,a*c,c*d,b*d})                                  |
|                                                                       |
|o4 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {b, d}, {c, d}}}        |
|           "ring" => R                                                 |
|           "vertices" => {a, b, c, d}                                  |
|                                                                       |
|o4 : Graph                                                             |
+-----------------------------------------------------------------------+
|i5 : getMaxCliques H                                                   |
|                                                                       |
|o5 = {{a, b, c}, {b, c, d}}                                            |
|                                                                       |
|o5 : List                                                              |
+-----------------------------------------------------------------------+

See also
========

  * cliqueNumber -- computes the clique number of a graph
  * getCliques -- returns cliques in a graph

Ways to use getMaxCliques:
==========================

  * "getMaxCliques(Graph)"

For the programmer
==================

The object getMaxCliques, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2733:0.

Gins -- optional argument for isSCM
***********************************

Description
===========

Directs isSCM, to use generic initial ideals to determine whether
the Alexander dual of the edge ideal of a hypergraph is componentwise linear.
See full discussion at isSCM.

See also
========

  * isSCM -- determines if a (hyper)graph is sequentially
    Cohen-Macaulay

Functions with optional argument named Gins:
============================================

  * isSCM(...,Gins=>...) -- use
    gins inside isSCM

For the programmer
==================

The object Gins, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4194:0.

Graph -- a class for graphs
***************************

Description
===========

This class represents simple graphs. This class extends HyperGraph,
and hence inherits all HyperGraph methods.

+---------------------------------------------+
|i1 : R = QQ[w,x,y,z];                        |
+---------------------------------------------+
|i2 : G = graph(R, {{w,x},{w,y},{w,z},{y,z}});|
+---------------------------------------------+
|i3 : vertices G                              |
|                                             |
|o3 = {w, x, y, z}                            |
|                                             |
|o3 : List                                    |
+---------------------------------------------+
|i4 : edges G                                 |
|                                             |
|o4 = {{w, x}, {w, y}, {w, z}, {y, z}}        |
|                                             |
|o4 : List                                    |
+---------------------------------------------+
|i5 : ring G                                  |
|                                             |
|o5 = R                                       |
|                                             |
|o5 : PolynomialRing                          |
+---------------------------------------------+

Like hypergraphs, graphs are associated with a polynomial ring whose variables
are the vertices of the graph. Isolated vertices should not appear in the edge
list. As a consequence, the edgeIdeal, of a graph is always
generated by quadratics. The fact that isolated vertices are not edges in a
graph affects the output of the methods connectedComponents (SimplicialComplexes),
see
numConnectedComponents, and isConnected.
One can use connectedGraphComponents,
see numConnectedGraphComponents,
and isConnectedGraph, to
ensure that each isolated vertex is counted as a separate connected component.

See also
========

  * graph -- constructor for Graph
  * HyperGraph -- a class for hypergraphs
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Functions and methods returning a graph:
========================================

  * antiCycle -- returns a graph of an anticycle
  * "antiCycle(List)" -- see antiCycle, -- returns a graph of
    an anticycle
  * "antiCycle(Ring)" -- see antiCycle, -- returns a graph of
    an anticycle
  * "antiCycle(Ring,ZZ)" -- see antiCycle, -- returns a graph
    of an anticycle
  * "completeGraph(List)" -- see completeGraph, -- returns
    a complete graph
  * "completeGraph(Ring)" -- see completeGraph, -- returns
    a complete graph
  * "completeGraph(Ring,ZZ)" -- see completeGraph, --
    returns a complete graph
  * "completeMultiPartite(Ring,List)" -- see completeMultiPartite,
    -- returns a complete multipartite graph
  * "completeMultiPartite(Ring,ZZ,ZZ)" -- see completeMultiPartite,
    -- returns a complete multipartite graph
  * cycle -- returns a graph cycle
  * "cycle(List)" -- see cycle, -- returns a graph cycle
  * "cycle(Ring)" -- see cycle, -- returns a graph cycle
  * "cycle(Ring,ZZ)" -- see cycle, -- returns a graph cycle
  * graph -- constructor for Graph
  * "graph(HyperGraph)" -- see graph, -- constructor for Graph
  * "graph(Ideal)" -- see graph, -- constructor for Graph
  * "graph(List)" -- see graph, -- constructor for Graph
  * "graph(MonomialIdeal)" -- see graph, -- constructor for Graph
  * "graph(PolynomialRing,List)" -- see graph, -- constructor for
    Graph

Methods that use a graph:
=========================

  * "adjacencyMatrix(Graph)" -- see adjacencyMatrix, --
    returns the adjacency Matrix of a graph
  * "allEvenHoles(Graph)" -- see allEvenHoles, -- returns
    all even holes in a graph
  * "allOddHoles(Graph)" -- see allOddHoles, -- returns all
    odd holes in a graph
  * "cliqueComplex(Graph)" -- see cliqueComplex, --
    returns the clique complex of a graph
  * "cliqueNumber(Graph)" -- see cliqueNumber, -- computes
    the clique number of a graph
  * "complementGraph(Graph)" -- see complementGraph, --
    returns the complement of a graph or hypergraph
  * "getCliques(Graph)" -- see getCliques, -- returns cliques
    in a graph
  * "getCliques(Graph,ZZ)" -- see getCliques, -- returns
    cliques in a graph
  * "getMaxCliques(Graph)" -- see getMaxCliques, --
    returns maximal cliques in a graph
  * "hasOddHole(Graph)" -- see hasOddHole, -- tells whether a
    graph contains an odd hole
  * "hyperGraph(Graph)" -- see hyperGraph, -- constructor for
    HyperGraph
  * "independenceNumber(Graph)" -- see independenceNumber,
    -- determines the independence number of a graph
  * "inducedGraph(Graph,List)" -- see inducedGraph, --
    returns the induced subgraph of a graph
  * "isBipartite(Graph)" -- see isBipartite, -- determines
    if a graph is bipartite
  * "isChordal(Graph)" -- see isChordal, -- determines if a
    graph is chordal
  * "isForest(Graph)" -- see isForest, -- determines whether a
    (hyper)graph is a forest
  * "isLeaf(Graph,ZZ)" -- see isLeaf, -- determines if an edge
    (or vertex) is a leaf of a (hyper)graph
  * "isPerfect(Graph)" -- see isPerfect, -- determines whether
    a graph is perfect
  * "numTriangles(Graph)" -- see numTriangles, -- returns
    the number of triangles in a graph
  * "smallestCycleSize(Graph)" -- see smallestCycleSize,
    -- returns the size of the smallest induced cycle of a
    graph
  * "spanningTree(Graph)" -- see spanningTree, -- returns a
    spanning tree of a graph

For the programmer
==================

The object Graph, is a type (Macaulay2Doc), with
ancestor classes HyperGraph, < HashTable (Macaulay2Doc)
< Thing (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1485:0.

graph -- constructor for Graph
******************************

  * Usage:
        G = graph(R,E)
        G = graph(I)
        G = graph(J)
        G = graph(E)
        G = graph(H)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), whose
        variables correspond to vertices of the hypergraph
      * E, a list (Macaulay2Doc), a list of edges, which themselves
        are lists of vertices
      * I, a monomial ideal (Macaulay2Doc), which must be
        square-free and quadratic, and whose generators become the edges of the
        graph
      * J, an ideal (Macaulay2Doc), which must be square-free,
        quadratic, and monomial, and whose generators become the edges of the
        graph
      * H, a hypergraph, to be converted to a graph. The
        edges in H must be of size two.
  * Outputs:
      * G, a graph,

Description
===========

The function graph is a constructor for Graph, a type of
HyperGraph.  The user can input a graph in a number of different
ways, which we describe below.  The information describing the graph is stored
in a hash table.

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];                                                     |
+-----------------------------------------------------------------------+
|i2 : E = {{a,b},{b,c},{c,f},{d,a},{e,c},{b,d}}                         |
|                                                                       |
|o2 = {{a, b}, {b, c}, {c, f}, {d, a}, {e, c}, {b, d}}                  |
|                                                                       |
|o2 : List                                                              |
+-----------------------------------------------------------------------+
|i3 : g = graph (R,E)                                                   |
|                                                                       |
|o3 = Graph{"edges" => {{a, b}, {b, c}, {c, f}, {a, d}, {c, e}, {b, d}}}|
|           "ring" => R                                                 |
|           "vertices" => {a, b, c, d, e, f}                            |
|                                                                       |
|o3 : Graph                                                             |
+-----------------------------------------------------------------------+

As long as the edge list is not empty, the ring can be omitted. When a ring is
not passed to the constructor, the underlying hypergraph takes its ring from
the first variable found.

+-----------------------------------------------------------------------------+
|i4 : S = QQ[z_1..z_8];                                                       |
+-----------------------------------------------------------------------------+
|i5 : E1 = {{z_1,z_2},{z_2,z_3},{z_3,z_4},{z_4,z_5},{z_5,z_6},{z_6,z_7},{z_7,z|
|                                                                             |
|o5 = {{z , z }, {z , z }, {z , z }, {z , z }, {z , z }, {z , z }, {z , z },  |
|        1   2     2   3     3   4     4   5     5   6     6   7     7   8    |
|     ------------------------------------------------------------------------|
|     {z , z }}                                                               |
|       8   1                                                                 |
|                                                                             |
|o5 : List                                                                    |
|-----------------------------------------------------------------------------|
|_8},{z_8,z_1}}                                                               |
+-----------------------------------------------------------------------------+
|i6 : E2 = {{z_1,z_2},{z_2,z_3}}                                              |
|                                                                             |
|o6 = {{z , z }, {z , z }}                                                    |
|        1   2     2   3                                                      |
|                                                                             |
|o6 : List                                                                    |
+-----------------------------------------------------------------------------+
|i7 : g1 = graph E1                                                           |
|                                                                             |
|o7 = Graph{"edges" => {{z , z }, {z , z }, {z , z }, {z , z }, {z , z }, {z ,|
|                         1   2     2   3     3   4     4   5     5   6     6 |
|           "ring" => S                                                       |
|           "vertices" => {z , z , z , z , z , z , z , z }                    |
|                           1   2   3   4   5   6   7   8                     |
|                                                                             |
|o7 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|z }, {z , z }, {z , z }}}                                                    |
| 7     1   8     7   8                                                       |
+-----------------------------------------------------------------------------+
|i8 : g2 = graph E2                                                           |
|                                                                             |
|o8 = Graph{"edges" => {{z , z }, {z , z }}               }                   |
|                         1   2     2   3                                     |
|           "ring" => S                                                       |
|           "vertices" => {z , z , z , z , z , z , z , z }                    |
|                           1   2   3   4   5   6   7   8                     |
|                                                                             |
|o8 : Graph                                                                   |
+-----------------------------------------------------------------------------+

The list of edges could also be entered as a list of square-free quadratic
monomials.

+------------------------------------------------------------------------+
|i9 : T = QQ[w,x,y,z];                                                   |
+------------------------------------------------------------------------+
|i10 : e = {w*x,w*y,w*z,x*y,x*z,y*z}                                     |
|                                                                        |
|o10 = {w*x, w*y, w*z, x*y, x*z, y*z}                                    |
|                                                                        |
|o10 : List                                                              |
+------------------------------------------------------------------------+
|i11 : g = graph e                                                       |
|                                                                        |
|o11 = Graph{"edges" => {{w, x}, {w, y}, {x, y}, {w, z}, {x, z}, {y, z}}}|
|            "ring" => T                                                 |
|            "vertices" => {w, x, y, z}                                  |
|                                                                        |
|o11 : Graph                                                             |
+------------------------------------------------------------------------+

Another option for defining an graph is to use an ideal (Macaulay2Doc),
or monomialIdeal (Macaulay2Doc).

+--------------------------------------------------------------------------+
|i12 : C = QQ[p_1..p_6];                                                   |
+--------------------------------------------------------------------------+
|i13 : i = monomialIdeal (p_1*p_2,p_2*p_3,p_3*p_4,p_3*p_5,p_3*p_6)         |
|                                                                          |
|o13 = monomialIdeal (p p , p p , p p , p p , p p )                        |
|                      1 2   2 3   3 4   3 5   3 6                         |
|                                                                          |
|o13 : MonomialIdeal of C                                                  |
+--------------------------------------------------------------------------+
|i14 : graph i                                                             |
|                                                                          |
|o14 = Graph{"edges" => {{p , p }, {p , p }, {p , p }, {p , p }, {p , p }}}|
|                          1   2     2   3     3   4     3   5     3   6   |
|            "ring" => C                                                   |
|            "vertices" => {p , p , p , p , p , p }                        |
|                            1   2   3   4   5   6                         |
|                                                                          |
|o14 : Graph                                                               |
+--------------------------------------------------------------------------+
|i15 : j = ideal (p_1*p_2,p_1*p_3,p_1*p_4,p_1*p_5,p_1*p_6)                 |
|                                                                          |
|o15 = ideal (p p , p p , p p , p p , p p )                                |
|              1 2   1 3   1 4   1 5   1 6                                 |
|                                                                          |
|o15 : Ideal of C                                                          |
+--------------------------------------------------------------------------+
|i16 : graph j                                                             |
|                                                                          |
|o16 = Graph{"edges" => {{p , p }, {p , p }, {p , p }, {p , p }, {p , p }}}|
|                          1   2     1   3     1   4     1   5     1   6   |
|            "ring" => C                                                   |
|            "vertices" => {p , p , p , p , p , p }                        |
|                            1   2   3   4   5   6                         |
|                                                                          |
|o16 : Graph                                                               |
+--------------------------------------------------------------------------+

A graph can be made from any hypergraph whose edges are all of size two.

+-----------------------------------------------------------------------------+
|i17 : D = QQ[r_1..r_5];                                                      |
+-----------------------------------------------------------------------------+
|i18 : h = hyperGraph {r_1*r_2,r_2*r_4,r_3*r_5,r_5*r_4,r_1*r_5}               |
|                                                                             |
|o18 = HyperGraph{"edges" => {{r , r }, {r , r }, {r , r }, {r , r }, {r ,    |
|                               1   2     2   4     1   5     3   5     4     |
|                 "ring" => D                                                 |
|                 "vertices" => {r , r , r , r , r }                          |
|                                 1   2   3   4   5                           |
|                                                                             |
|o18 : HyperGraph                                                             |
|-----------------------------------------------------------------------------|
|r }}}                                                                        |
| 5                                                                           |
+-----------------------------------------------------------------------------+
|i19 : g = graph h                                                            |
|                                                                             |
|o19 = 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                                |
|                                                                             |
|o19 : Graph                                                                  |
+-----------------------------------------------------------------------------+

Not all graph constructors are able to make the empty graph, that is, the graph
with no edges. Specifically, the constructors that take only a list cannot make
the empty graph because the underlying ring is not given. To define the empty
graph, give an explicit polynomial ring, or give the (monomial) ideal.

+-----------------------------------------------------------------------+
|i20 : E = QQ[m,n,o,p]                                                  |
|                                                                       |
|o20 = E                                                                |
|                                                                       |
|o20 : PolynomialRing                                                   |
+-----------------------------------------------------------------------+
|i21 : graph(E, {})                                                     |
|                                                                       |
|o21 = Graph{"edges" => {}             }                                |
|            "ring" => E                                                |
|            "vertices" => {m, n, o, p}                                 |
|                                                                       |
|o21 : Graph                                                            |
+-----------------------------------------------------------------------+
|i22 : graph monomialIdeal(0_E)  -- the zero element of E (do not use 0)|
|                                                                       |
|o22 = Graph{"edges" => {}             }                                |
|            "ring" => E                                                |
|            "vertices" => {m, n, o, p}                                 |
|                                                                       |
|o22 : Graph                                                            |
+-----------------------------------------------------------------------+
|i23 : graph ideal(0_E)                                                 |
|                                                                       |
|o23 = Graph{"edges" => {}             }                                |
|            "ring" => E                                                |
|            "vertices" => {m, n, o, p}                                 |
|                                                                       |
|o23 : Graph                                                            |
+-----------------------------------------------------------------------+

See also
========

  * hyperGraph -- constructor for HyperGraph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use graph:
==================

  * "graph(HyperGraph)"
  * "graph(Ideal)"
  * "graph(List)"
  * "graph(MonomialIdeal)"
  * "graph(PolynomialRing,List)"

For the programmer
==================

The object graph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1667:0.

hasGoodLeaf -- determines if a HyperGraph contains a good leaf
**************************************************************

  * Usage:
        b = hasGoodLeaf(H)
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if H contains an
        edge that is a good leaf

Description
===========

A good leaf of hypergraph H is an edge L whose intersections with all other
edges form a totally ordered set. It follows that L must have a free vertex. In
the graph setting, a good leaf is an edge containing a vertex of degree one.
The notion of a good leaf was introduced by X. Zheng in her Ph.D. thesis
(2004).

+----------------------------------------------------------+
|i1 : R = QQ[a..g];                                        |
+----------------------------------------------------------+
|i2 : H = hyperGraph {b*c*d*e, a*b*c*d, c*d*f, d*g, e*f*g};|
+----------------------------------------------------------+
|i3 : hasGoodLeaf(H)                                       |
|                                                          |
|o3 = true                                                 |
+----------------------------------------------------------+
|i4 : getGoodLeaf(H)                                       |
|                                                          |
|o4 = {a, b, c, d}                                         |
|                                                          |
|o4 : List                                                 |
+----------------------------------------------------------+

See also
========

  * getGoodLeaf -- returns an edge that is a good leaf
  * getGoodLeafIndex -- returns the index of an edge
    that is a good leaf
  * isGoodLeaf -- determines if an edge is a good leaf

Ways to use hasGoodLeaf:
========================

  * "hasGoodLeaf(HyperGraph)"

For the programmer
==================

The object hasGoodLeaf, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2768:0.

hasOddHole -- tells whether a graph contains an odd hole
********************************************************

  * Usage:
        b = hasOddHole G
  * Inputs:
      * G, a graph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if G has an odd
        hole and false otherwise

Description
===========

An odd hole is an odd induced cycle of length at least 5. The method is based
on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the
square of the Alexander dual of the edge ideal.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd
holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_6];                                                       |
+-----------------------------------------------------------------------------+
|i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5|
|                                                                             |
|o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     1   5     4   5     1 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|-cycle and a triangle                                                        |
|                                                                             |
| x }, {x , x }}}                                                             |
|  6     5   6                                                                |
+-----------------------------------------------------------------------------+
|i3 : hasOddHole G                                                            |
|                                                                             |
|o3 = true                                                                    |
+-----------------------------------------------------------------------------+
|i4 : H = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6,x_1*x|
|                                                                             |
|o4 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     1   4     3   4     1   5     4 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|_4}) --no odd holes                                                          |
|                                                                             |
| x }, {x , x }, {x , x }}}                                                   |
|  5     1   6     5   6                                                      |
+-----------------------------------------------------------------------------+
|i5 : hasOddHole H                                                            |
|                                                                             |
|o5 = false                                                                   |
+-----------------------------------------------------------------------------+

See also
========

  * allOddHoles -- returns all odd holes in a graph

Ways to use hasOddHole:
=======================

  * "hasOddHole(Graph)"

For the programmer
==================

The object hasOddHole, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2803:0.

HyperGraph -- a class for hypergraphs
*************************************

Description
===========

This class represents hypergraphs. A hypergraph is a tuple (V,E) of vertices V
and edges E which are subsets of the vertices. In this package, all hypergraphs
have the additional property that no edge is a subset of any other edge.
Hypergraphs of this form are often referred to as clutters.

+------------------------------------------------+
|i1 : R = QQ[w,x,y,z];                           |
+------------------------------------------------+
|i2 : H = hyperGraph(R, {{w,x},{w,y,z},{x,y,z}});|
+------------------------------------------------+
|i3 : vertices H                                 |
|                                                |
|o3 = {w, x, y, z}                               |
|                                                |
|o3 : List                                       |
+------------------------------------------------+
|i4 : edges H                                    |
|                                                |
|o4 = {{w, x}, {w, y, z}, {x, y, z}}             |
|                                                |
|o4 : List                                       |
+------------------------------------------------+
|i5 : ring H                                     |
|                                                |
|o5 = R                                          |
|                                                |
|o5 : PolynomialRing                             |
+------------------------------------------------+

Hypergraphs are always associated with a polynomial ring whose variables are
the vertices of the hypergraph.

See also
========

  * hyperGraph -- constructor for HyperGraph
  * Graph -- a class for graphs
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Types of hypergraph:
====================

  * Graph -- a class for graphs

Functions and methods returning a hypergraph:
=============================================

  * hyperGraph -- constructor for HyperGraph
  * "hyperGraph(Graph)" -- see hyperGraph, -- constructor for
    HyperGraph
  * "hyperGraph(Ideal)" -- see hyperGraph, -- constructor for
    HyperGraph
  * "hyperGraph(List)" -- see hyperGraph, -- constructor for
    HyperGraph
  * "hyperGraph(MonomialIdeal)" -- see hyperGraph, --
    constructor for HyperGraph
  * "hyperGraph(PolynomialRing,List)" -- see hyperGraph, --
    constructor for HyperGraph

Methods that use a hypergraph:
==============================

  * "changeRing(HyperGraph,PolynomialRing,List)" -- see changeRing,
    -- replaces vertices with variables of a different ring
  * "chromaticNumber(HyperGraph)" -- see chromaticNumber,
    -- computes the chromatic number of a hypergraph
  * "complementGraph(HyperGraph)" -- see complementGraph,
    -- returns the complement of a graph or hypergraph
  * "connectedComponents(HyperGraph)" -- see connectedComponents,
    -- returns the connected components of a hypergraph
  * "connectedGraphComponents(HyperGraph)" -- see
    connectedGraphComponents, -- returns the
    connected components of a graph
  * "coverIdeal(HyperGraph)" -- see coverIdeal, -- creates
    the cover ideal of a (hyper)graph
  * "degreeVertex(HyperGraph,RingElement)" -- see degreeVertex,
    -- returns the degree of a vertex
  * "degreeVertex(HyperGraph,ZZ)" -- see degreeVertex, --
    returns the degree of a vertex
  * "deleteEdges(HyperGraph,List)" -- see deleteEdges, --
    returns the (hyper)graph with specified edges removed
  * "edgeIdeal(HyperGraph)" -- see edgeIdeal, -- creates the
    edge ideal of a (hyper)graph
  * "edges(HyperGraph)" -- see edges, -- gets the edges of a
    (hyper)graph
  * "getEdge(HyperGraph,ZZ)" -- see getEdge, -- gets the n-th
    edge in a (hyper)graph
  * "getEdgeIndex(HyperGraph,List)" -- see getEdgeIndex, --
    finds the index of an edge in a HyperGraph
  * "getEdgeIndex(HyperGraph,RingElement)" -- see getEdgeIndex,
    -- finds the index of an edge in a HyperGraph
  * "getGoodLeaf(HyperGraph)" -- see getGoodLeaf, -- returns
    an edge that is a good leaf
  * "getGoodLeafIndex(HyperGraph)" -- see getGoodLeafIndex,
    -- returns the index of an edge that is a good leaf
  * "graph(HyperGraph)" -- see graph, -- constructor for Graph
  * "hasGoodLeaf(HyperGraph)" -- see hasGoodLeaf, --
    determines if a HyperGraph contains a good leaf
  * HyperGraph == HyperGraph -- equality
  * "hyperGraphToSimplicialComplex(HyperGraph)" -- see
    hyperGraphToSimplicialComplex, -- makes a
    simplicial complex from a (hyper)graph
  * "incidenceMatrix(HyperGraph)" -- see incidenceMatrix,
    -- returns the incidence matrix of a hypergraph
  * "independenceComplex(HyperGraph)" -- see independenceComplex,
    -- returns the independence complex of a (hyper)graph
  * "inducedHyperGraph(HyperGraph,List)" -- see inducedHyperGraph,
    -- returns the induced subgraph of a (hyper)graph
  * "isCM(HyperGraph)" -- see isCM, -- determines if a (hyper)graph
    is Cohen-Macaulay
  * "isConnected(HyperGraph)" -- see isConnected, --
    determines if a (hyper)graph is connected
  * "isConnectedGraph(HyperGraph)" -- see isConnectedGraph,
    -- determines if a graph is connected
  * "isEdge(HyperGraph,List)" -- see isEdge, -- determines if an
    edge is in a (hyper)graph
  * "isEdge(HyperGraph,RingElement)" -- see isEdge, -- determines
    if an edge is in a (hyper)graph
  * "isForest(HyperGraph)" -- see isForest, -- determines
    whether a (hyper)graph is a forest
  * "isGoodLeaf(HyperGraph,ZZ)" -- see isGoodLeaf, --
    determines if an edge is a good leaf
  * "isGraph(HyperGraph)" -- see isGraph, -- determines if a
    hypergraph is a graph
  * "isLeaf(HyperGraph,RingElement)" -- see isLeaf, -- determines
    if an edge (or vertex) is a leaf of a (hyper)graph
  * "isLeaf(HyperGraph,ZZ)" -- see isLeaf, -- determines if an
    edge (or vertex) is a leaf of a (hyper)graph
  * "isolatedVertices(HyperGraph)" -- see isolatedVertices,
    -- returns all vertices not contained in any edge
  * "isSCM(HyperGraph)" -- see isSCM, -- determines if a
    (hyper)graph is sequentially Cohen-Macaulay
  * "lineGraph(HyperGraph)" -- see lineGraph, -- returns the
    line graph of a (hyper)graph
  * "neighbors(HyperGraph,List)" -- see neighbors, -- returns
    the neighbors of a vertex or list of vertices
  * "neighbors(HyperGraph,RingElement)" -- see neighbors, --
    returns the neighbors of a vertex or list of vertices
  * "neighbors(HyperGraph,ZZ)" -- see neighbors, -- returns
    the neighbors of a vertex or list of vertices
  * "numConnectedComponents(HyperGraph)" -- see numConnectedComponents,
    -- returns the number of connected components in a
    (hyper)graph
  * "numConnectedGraphComponents(HyperGraph)" -- see
    numConnectedGraphComponents, -- returns the
    number of connected components in a graph
  * ring(HyperGraph) -- gives the ring of a
    (hyper)graph
  * "vertexCoverNumber(HyperGraph)" -- see vertexCoverNumber,
    -- find the vertex covering number of a (hyper)graph
  * "vertexCovers(HyperGraph)" -- see vertexCovers, -- list
    the minimal vertex covers of a (hyper)graph
  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

For the programmer
==================

The object HyperGraph, is a type (Macaulay2Doc),
with ancestor classes HashTable (Macaulay2Doc), < Thing (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1455:0.

hyperGraph -- constructor for HyperGraph
****************************************

  * Usage:
        H = hyperGraph(R,E)
        H = hyperGraph(I)
        H = hyperGraph(J)
        H = hyperGraph(E)
        H = hyperGraph(G)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), whose
        variables correspond to vertices of the hypergraph
      * E, a list (Macaulay2Doc), a list of edges, which themselves
        are lists of vertices
      * I, a monomial ideal (Macaulay2Doc), which must be
        square-free and whose generators become the edges of the hypergraph
      * J, an ideal (Macaulay2Doc), 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 },    |
|                              1   2   3     2   4   5   6     4   7   8      |
|                "ring" => S                                                  |
|                "vertices" => {z , z , z , z , z , z , z , z }               |
|                                1   2   3   4   5   6   7   8                |
|                                                                             |
|o7 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|{z , z , z }}}                                                               |
|  5   7   8                                                                  |
+-----------------------------------------------------------------------------+
|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 (Macaulay2Doc),
or monomialIdeal (Macaulay2Doc).

+-------------------------------------------------------------------+
|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 ,    |
|                               1   2     2   4     1   5     3   5     4     |
|                 "ring" => D                                                 |
|                 "vertices" => {r , r , r , r , r }                          |
|                                 1   2   3   4   5                           |
|                                                                             |
|o19 : HyperGraph                                                             |
|-----------------------------------------------------------------------------|
|r }}}                                                                        |
| 5                                                                           |
+-----------------------------------------------------------------------------+

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
========

  * graph -- constructor for Graph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

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 (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1577:0.

HyperGraph == HyperGraph -- equality
************************************

  * Operator: == (Macaulay2Doc),
  * Usage:
        g == h
  * Inputs:
      * g, a hypergraph,
      * h, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if g and h are
        equal

Description
===========

This function determines if two HyperGraphs are mathematically equal. Two
HyperGraphs are equal if they are defined over the same ring, have the same
variables, and have the same set of edges. In particular, the order of the
edges and the order of variables within each edge do not matter.

+----------------------------------------------+
|i1 : R = QQ[a..f];                            |
+----------------------------------------------+
|i2 : g = hyperGraph {{a,b,c},{b,c,d},{d,e,f}};|
+----------------------------------------------+
|i3 : h = hyperGraph {{b,c,d},{a,b,c},{f,e,d}};|
+----------------------------------------------+
|i4 : k = hyperGraph {{a,b},{b,c,d},{d,e,f}};  |
+----------------------------------------------+
|i5 : g == h                                   |
|                                              |
|o5 = true                                     |
+----------------------------------------------+
|i6 : g == k                                   |
|                                              |
|o6 = false                                    |
+----------------------------------------------+

Ways to use this method:
========================

  * HyperGraph == HyperGraph -- equality
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:1709:0.

hyperGraphToSimplicialComplex -- makes a simplicial complex from a (hyper)graph
*******************************************************************************

  * Usage:
        D = hyperGraphToSimplicialComplex H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * D, an abstract simplicial complex (SimplicialComplexes),
        whose facets are given by the
        edges of H

Description
===========

This function produces a simplicial complex from a (hyper)graph. The facets of
the simplicial complex are given by the edge set of the (hyper)graph. This
function is the inverse of simplicialComplexToHyperGraph,
and enables users to make use of functions in
the package SimplicialComplexes.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_6];                                                       |
+-----------------------------------------------------------------------------+
|i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5|
|                                                                             |
|o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     1   5     4   5     1 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|-cycle and a triangle                                                        |
|                                                                             |
| x }, {x , x }}}                                                             |
|  6     5   6                                                                |
+-----------------------------------------------------------------------------+
|i3 : DeltaG = hyperGraphToSimplicialComplex G                                |
|                                                                             |
|o3 = simplicialComplex | x_5x_6 x_1x_6 x_4x_5 x_1x_5 x_3x_4 x_2x_3 x_1x_2 |  |
|                                                                             |
|o3 : SimplicialComplex                                                       |
+-----------------------------------------------------------------------------+
|i4 : hyperGraphDeltaG = simplicialComplexToHyperGraph DeltaG                 |
|                                                                             |
|o4 = HyperGraph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x },|
|                              1   2     2   3     3   4     1   5     4   5  |
|                "ring" => R                                                  |
|                "vertices" => {x , x , x , x , x , x }                       |
|                                1   2   3   4   5   6                        |
|                                                                             |
|o4 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|{x , x }, {x , x }}}                                                         |
|  1   6     5   6                                                            |
+-----------------------------------------------------------------------------+
|i5 : GPrime = graph(hyperGraphDeltaG)                                        |
|                                                                             |
|o5 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     1   5     4   5     1 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o5 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|x }, {x , x }}}                                                              |
| 6     5   6                                                                 |
+-----------------------------------------------------------------------------+
|i6 : G === GPrime                                                            |
|                                                                             |
|o6 = true                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * simplicialComplexToHyperGraph, --
    makes a (hyper)graph from a simplicial complex
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use hyperGraphToSimplicialComplex:
==========================================

  * "hyperGraphToSimplicialComplex(HyperGraph)"

For the programmer
==================

The object hyperGraphToSimplicialComplex,
is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2840:0.

incidenceMatrix -- returns the incidence matrix of a hypergraph
***************************************************************

  * Usage:
        M = incidenceMatrix H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * M, a matrix (Macaulay2Doc), the incidence matrix of the
        hypergraph

Description
===========

This function returns the incidence matrix of the given hypergraph H. The rows
of the matrix are indexed by the variables of the hypergraph, and the columns
are indexed by the edges. The (i,j)^{th} entry in the matrix is 1 if vertex i
is contained in edge j, and is 0 otherwise. The order of the rows and columns
are determined by the internal order of the vertices and edges. See
edges, and vertices(HyperGraph).

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..f];                                                           |
+-----------------------------------------------------------------------------+
|i2 : g = hyperGraph {a*b*c*d,c*e,e*f}                                        |
|                                                                             |
|o2 = HyperGraph{"edges" => {{a, b, c, d}, {c, e}, {e, f}}}                   |
|                "ring" => S                                                  |
|                "vertices" => {a, b, c, d, e, f}                             |
|                                                                             |
|o2 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i3 : incidenceMatrix g                                                       |
|                                                                             |
|o3 = | 1 0 0 |                                                               |
|     | 1 0 0 |                                                               |
|     | 1 1 0 |                                                               |
|     | 1 0 0 |                                                               |
|     | 0 1 1 |                                                               |
|     | 0 0 1 |                                                               |
|                                                                             |
|              6       3                                                      |
|o3 : Matrix ZZ  <-- ZZ                                                       |
+-----------------------------------------------------------------------------+
|i4 : T = QQ[f,e,d,c,b,a];                                                    |
+-----------------------------------------------------------------------------+
|i5 : h = hyperGraph {a*b*c*d,c*e,e*f}                                        |
|                                                                             |
|o5 = HyperGraph{"edges" => {{f, e}, {e, c}, {d, c, b, a}}}                   |
|                "ring" => T                                                  |
|                "vertices" => {f, e, d, c, b, a}                             |
|                                                                             |
|o5 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i6 : incidenceMatrix h -- although the same graph, matrix is different since |
|                                                                             |
|o6 = | 1 0 0 |                                                               |
|     | 1 1 0 |                                                               |
|     | 0 0 1 |                                                               |
|     | 0 1 1 |                                                               |
|     | 0 0 1 |                                                               |
|     | 0 0 1 |                                                               |
|                                                                             |
|              6       3                                                      |
|o6 : Matrix ZZ  <-- ZZ                                                       |
|-----------------------------------------------------------------------------|
|variables have different ordering                                            |
+-----------------------------------------------------------------------------+

See also
========

  * adjacencyMatrix -- returns the adjacency Matrix of
    a graph
  * edges -- gets the edges of a (hyper)graph
  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

Ways to use incidenceMatrix:
============================

  * "incidenceMatrix(HyperGraph)"

For the programmer
==================

The object incidenceMatrix, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2879:0.

independenceComplex -- returns the independence complex of a (hyper)graph
*************************************************************************

  * Usage:
        D = independenceComplex H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * D, an abstract simplicial complex (SimplicialComplexes),
        the independence complex
        associated to the (hyper)graph

Description
===========

This function associates to a (hyper)graph a simplicial complex whose faces
correspond to the independent sets of the (hyper)graph.  See, for example, the
paper of A. Van Tuyl and R. Villarreal "Shellable graphs and sequentially
Cohen-Macaulay bipartite graphs," Journal of Combinatorial Theory, Series A 115
(2008) 799-814.

+---------------------------------------------------------------+
|i1 : S = QQ[a..e];                                             |
+---------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*e,e*a} -- the 5-cycle            |
|                                                               |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}|
|           "ring" => S                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o2 : Graph                                                     |
+---------------------------------------------------------------+
|i3 : independenceComplex g                                     |
|                                                               |
|o3 = simplicialComplex | ce be bd ad ac |                      |
|                                                               |
|o3 : SimplicialComplex                                         |
+---------------------------------------------------------------+
|i4 : h = hyperGraph {a*b*c,b*c*d,d*e}                          |
|                                                               |
|o4 = HyperGraph{"edges" => {{a, b, c}, {b, c, d}, {d, e}}}     |
|                "ring" => S                                    |
|                "vertices" => {a, b, c, d, e}                  |
|                                                               |
|o4 : HyperGraph                                                |
+---------------------------------------------------------------+
|i5 : independenceComplex h                                     |
|                                                               |
|o5 = simplicialComplex | bce ace abe acd abd |                 |
|                                                               |
|o5 : SimplicialComplex                                         |
+---------------------------------------------------------------+

Equivalently, the independence complex is the simplicial complex associated to
the edge ideal of the (hyper)graph H via the Stanley-Reisner correspondence.

+---------------------------------------------------------------+
|i6 : S = QQ[a..e];                                             |
+---------------------------------------------------------------+
|i7 : g = graph {a*b,b*c,a*c,d*e,a*e}                           |
|                                                               |
|o7 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {a, e}, {d, e}}}|
|           "ring" => S                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o7 : Graph                                                     |
+---------------------------------------------------------------+
|i8 : Delta1 = independenceComplex g                            |
|                                                               |
|o8 = simplicialComplex | ce be cd bd ad |                      |
|                                                               |
|o8 : SimplicialComplex                                         |
+---------------------------------------------------------------+
|i9 : Delta2 = simplicialComplex edgeIdeal g                    |
|                                                               |
|o9 = simplicialComplex | ce be cd bd ad |                      |
|                                                               |
|o9 : SimplicialComplex                                         |
+---------------------------------------------------------------+
|i10 : Delta1 === Delta2                                        |
|                                                               |
|o10 = true                                                     |
+---------------------------------------------------------------+

See also
========

  * independenceNumber -- determines the
    independence number of a graph

Ways to use independenceComplex:
================================

  * "independenceComplex(HyperGraph)"

For the programmer
==================

The object independenceComplex, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2923:0.

independenceNumber -- determines the independence number of a graph
*******************************************************************

  * Usage:
        d = independenceNumber G
  * Inputs:
      * G, a graph,
  * Outputs:
      * d, an integer (Macaulay2Doc), the independence number of G

Description
===========

This function returns the maximum number of independent vertices in a graph.
This number can be found by computing the dimension of the simplicial complex
whose faces are the independent sets (see independenceComplex)
and adding 1 to this number.

+------------------------------------------------------------------------+
|i1 : R = QQ[a..e];                                                      |
+------------------------------------------------------------------------+
|i2 : c4 = graph {a*b,b*c,c*d,d*a} -- 4-cycle plus an isolated vertex!!!!|
|                                                                        |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}                 |
|           "ring" => R                                                  |
|           "vertices" => {a, b, c, d, e}                                |
|                                                                        |
|o2 : Graph                                                              |
+------------------------------------------------------------------------+
|i3 : c5 = graph {a*b,b*c,c*d,d*e,e*a} -- 5-cycle                        |
|                                                                        |
|o3 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}         |
|           "ring" => R                                                  |
|           "vertices" => {a, b, c, d, e}                                |
|                                                                        |
|o3 : Graph                                                              |
+------------------------------------------------------------------------+
|i4 : independenceNumber c4                                              |
|                                                                        |
|o4 = 3                                                                  |
+------------------------------------------------------------------------+
|i5 : independenceNumber c5                                              |
|                                                                        |
|o5 = 2                                                                  |
+------------------------------------------------------------------------+
|i6 : dim independenceComplex c4 + 1 == independenceNumber c4            |
|                                                                        |
|o6 = true                                                               |
+------------------------------------------------------------------------+

See also
========

  * independenceComplex -- returns the independence
    complex of a (hyper)graph

Ways to use independenceNumber:
===============================

  * "independenceNumber(Graph)"

For the programmer
==================

The object independenceNumber, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:2960:0.

inducedGraph -- returns the induced subgraph of a graph
*******************************************************

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

Description
===========

This function returns the induced subgraph of a graph on a specified set of
vertices. This function enables the user to create subgraphs of the original
graph. inducedGraph accepts a Graph, as input and returns a
Graph, as well. Use inducedHyperGraph, for a
HyperGraph, instead.

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 graph. However, one can set the option OriginalRing,
to true if one wants to give the induced graph the same ring as
the original graph.

+-------------------------------------------------------------------------+
|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 = inducedGraph(G,{b,c,d,e})                                      |
|                                                                         |
|o3 = Graph{"edges" => {{b, c}, {c, d}, {d, e}}}                          |
|           "ring" => QQ[b..e]                                            |
|           "vertices" => {b, c, d, e}                                    |
|                                                                         |
|o3 : Graph                                                               |
+-------------------------------------------------------------------------+
|i4 : H2 = inducedGraph(G,{a,b,d,e})                                      |
|                                                                         |
|o4 = Graph{"edges" => {{a, b}, {a, e}, {d, e}}}                          |
|           "ring" => QQ[a..b, d..e]                                      |
|           "vertices" => {a, b, d, e}                                    |
|                                                                         |
|o4 : Graph                                                               |
+-------------------------------------------------------------------------+
|i5 : use ring H1                                                         |
|                                                                         |
|o5 = QQ[b..e]                                                            |
|                                                                         |
|o5 : PolynomialRing                                                      |
+-------------------------------------------------------------------------+
|i6 : inducedGraph(H1,{c,d,e})                                            |
|                                                                         |
|o6 = Graph{"edges" => {{c, d}, {d, e}}}                                  |
|           "ring" => QQ[c..e]                                            |
|           "vertices" => {c, d, e}                                       |
|                                                                         |
|o6 : Graph                                                               |
+-------------------------------------------------------------------------+
|i7 : use ring G                                                          |
|                                                                         |
|o7 = R                                                                   |
|                                                                         |
|o7 : PolynomialRing                                                      |
+-------------------------------------------------------------------------+
|i8 : inducedGraph(G,{b,c,d,e},OriginalRing=>true) --H1 but in bigger ring|
|                                                                         |
|o8 = Graph{"edges" => {{b, c}, {c, d}, {d, e}}}                          |
|           "ring" => R                                                   |
|           "vertices" => {a, b, c, d, e}                                 |
|                                                                         |
|o8 : Graph                                                               |
+-------------------------------------------------------------------------+

Equivalently, one can use changeRing, (and graph)
to move the induced graph 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 = inducedGraph(G,{b,c,d})                               |
|                                                                |
|o11 = Graph{"edges" => {{b, c}, {c, d}}}                        |
|            "ring" => QQ[b..d]                                  |
|            "vertices" => {b, c, d}                             |
|                                                                |
|o11 : Graph                                                     |
+----------------------------------------------------------------+
|i12 : graph changeRing(H,R,{b,c,d})                             |
|                                                                |
|o12 = Graph{"edges" => {{c, d}, {b, c}}  }                      |
|            "ring" => R                                         |
|            "vertices" => {a, b, c, d, e}                       |
|                                                                |
|o12 : Graph                                                     |
+----------------------------------------------------------------+

See also
========

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

Ways to use inducedGraph:
=========================

  * "inducedGraph(Graph,List)"

For the programmer
==================

The object inducedGraph, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3016:0.

inducedGraph(...,OriginalRing=>...) -- use OriginalRing inside inducedGraph or inducedHyperGraph
************************************************************************************************

  * Usage:
        J = inducedGraph(G,L,OriginalRing=>true)
        K = inducedHyperGraph(H,L,OrignalRing=>true)
  * Inputs:
      * G, a graph, the graph being considered
      * H, a hypergraph, the hypergraph being considered
      * L, a list (Macaulay2Doc), a list of vertices
  * Outputs:
      * G, a graph, the induced Graph of G on the vertices of L
      * K, a hypergraph, the induced HyperGraph of H on the
        vertices of L

Description
===========

When OriginalRing is set to true, see inducedGraph, or
inducedHyperGraph, returns a (hyper)graph with the original
(larger) ring attached rather than the subring only involving the variables of
L.

See also
========

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

Functions with optional argument named OriginalRing:
====================================================

  * inducedGraph(...,OriginalRing=>...)
    -- use OriginalRing
    inside inducedGraph or inducedHyperGraph
  * "inducedHyperGraph(...,OriginalRing=>...)"

Further information
===================

  * Default value: false (Macaulay2Doc),
  * Function: inducedGraph, -- returns the induced subgraph
    of a graph
  * Option key: OriginalRing, -- optional argument for
    inducedHyperGraph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4346:0.

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

  * Usage:
        h = inducedHyperGraph(H, L)
  * Inputs:
      * H, a hypergraph,
      * L, a list (Macaulay2Doc), of vertices (i.e. variables in
        the ring of H)
  * Optional inputs (Macaulay2Doc),:
      * 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 (Macaulay2Doc), 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    |
|                                                                             |
|o8 = HyperGraph{"edges" => {{b, c}, {c, d}, {d, e}}}                         |
|                "ring" => R                                                  |
|                "vertices" => {a, b, c, d, e}                                |
|                                                                             |
|o8 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|ring                                                                         |
+-----------------------------------------------------------------------------+

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 (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3073:0.

isBipartite -- determines if a graph is bipartite
*************************************************

  * Usage:
        b = isBipartite G
  * Inputs:
      * G, a graph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if G is
        bipartite, false otherwise

Description
===========

The function isBipartite determines if a given graph is bipartite.  A graph is
said to be bipartite if the vertices can be partitioned into two sets W and Y
such that every edge has one vertex in W and the other in Y.  Since a graph is
bipartite if and only if its chromatic number is 2, we can check if a graph is
bipartite by computing its chromatic number.

+----------------------------------------------------------------+
|i1 : S = QQ[a..e];                                              |
+----------------------------------------------------------------+
|i2 : t = graph {a*b,b*c,c*d,a*e} -- a tree (and thus, bipartite)|
|                                                                |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}}}         |
|           "ring" => S                                          |
|           "vertices" => {a, b, c, d, e}                        |
|                                                                |
|o2 : Graph                                                      |
+----------------------------------------------------------------+
|i3 : c5 = cycle S -- 5-cycle (not bipartite)                    |
|                                                                |
|o3 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {d, e}, {a, e}}} |
|           "ring" => S                                          |
|           "vertices" => {a, b, c, d, e}                        |
|                                                                |
|o3 : Graph                                                      |
+----------------------------------------------------------------+
|i4 : isBipartite t                                              |
|                                                                |
|o4 = true                                                       |
+----------------------------------------------------------------+
|i5 : isBipartite c5                                             |
|                                                                |
|o5 = false                                                      |
+----------------------------------------------------------------+

See also
========

  * chromaticNumber -- computes the chromatic number of
    a hypergraph

Ways to use isBipartite:
========================

  * "isBipartite(Graph)"

For the programmer
==================

The object isBipartite, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3108:0.

isChordal -- determines if a graph is chordal
*********************************************

  * Usage:
        b = isChordal G
  * Inputs:
      * G, a graph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if the graph is
        chordal

Description
===========

A graph is chordal if the graph has no induced cycles of length 4 or more
(triangles are allowed). To check if a graph is chordal, we use a
characterization of Fr\"oberg (see "On Stanley-Reisner rings,"  Topics in
algebra, Part 2 (Warsaw, 1988),  57-70, Banach Center Publ., 26, Part 2, PWN,
Warsaw, 1990.) that says that a graph G is chordal if and only if the edge
ideal of G^c has a linear resolution, where G^c is the complementary graph of
G.

+---------------------------------+
|i1 : S = QQ[a..e];               |
+---------------------------------+
|i2 : C = cycle S;                |
+---------------------------------+
|i3 : isChordal C                 |
|                                 |
|o3 = false                       |
+---------------------------------+
|i4 : D = graph {a*b,b*c,c*d,a*c};|
+---------------------------------+
|i5 : isChordal D                 |
|                                 |
|o5 = true                        |
+---------------------------------+
|i6 : E = completeGraph S;        |
+---------------------------------+
|i7 : isChordal E                 |
|                                 |
|o7 = true                        |
+---------------------------------+

Ways to use isChordal:
======================

  * "isChordal(Graph)"

For the programmer
==================

The object isChordal, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3144:0.

isCM -- determines if a (hyper)graph is Cohen-Macaulay
******************************************************

  * Usage:
        b = isCM H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if the
        edgeIdeal, of H is Cohen-Macaulay

Description
===========

This uses the edge ideal notion of Cohen-Macaulayness; a hypergraph is called
C-M if and only if its edge ideal is C-M.

+-----------------------------------------+
|i1 : R = QQ[a..e];                       |
+-----------------------------------------+
|i2 : C = cycle R;                        |
+-----------------------------------------+
|i3 : UnmixedTree = graph {a*b, b*c, c*d};|
+-----------------------------------------+
|i4 : MixedTree = graph {a*b, a*c, a*d};  |
+-----------------------------------------+
|i5 : isCM C                              |
|                                         |
|o5 = true                                |
+-----------------------------------------+
|i6 : isCM UnmixedTree                    |
|                                         |
|o6 = true                                |
+-----------------------------------------+
|i7 : isCM MixedTree                      |
|                                         |
|o7 = false                               |
+-----------------------------------------+

See also
========

  * isSCM -- determines if a (hyper)graph is sequentially
    Cohen-Macaulay
  * edgeIdeal -- creates the edge ideal of a (hyper)graph

Ways to use isCM:
=================

  * "isCM(HyperGraph)"

For the programmer
==================

The object isCM, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3179:0.

isConnected -- determines if a (hyper)graph is connected
********************************************************

  * Usage:
        b = isConnected H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if H is
        connected, false otherwise

Description
===========

This function checks if the given (hyper)graph H is connected. A (hyper)graph
is said to be connected if it has exactly one connected component.

Isolated vertices do not count as connected components and will not make this
method return false. This is in contrast to isConnectedGraph,
in which isolated vertices form their own connected
components. See the Connected Components Tutorial,
for more information.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = graph {a*b,b*c,c*d,d*e,a*e} -- the 5-cycle (connected)              |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}              |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : H = graph {a*b,b*c,c*a,d*e} -- a 3-cycle and a disjoint edge (not       |
|                                                                             |
|o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {d, e}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o3 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|connected)                                                                   |
+-----------------------------------------------------------------------------+
|i4 : isConnected G                                                           |
|                                                                             |
|o4 = true                                                                    |
+-----------------------------------------------------------------------------+
|i5 : isConnected H                                                           |
|                                                                             |
|o5 = false                                                                   |
+-----------------------------------------------------------------------------+

In the following example, the graph G has the isolated vertex d. As d is not
considered to be in any connected component, this graph is connected.

+---------------------------------------+
|i6 : S = QQ[a,b,c,d];                  |
+---------------------------------------+
|i7 : G = graph {a*b,b*c}               |
|                                       |
|o7 = Graph{"edges" => {{a, b}, {b, c}}}|
|           "ring" => S                 |
|           "vertices" => {a, b, c, d}  |
|                                       |
|o7 : Graph                             |
+---------------------------------------+
|i8 : isolatedVertices G                |
|                                       |
|o8 = {d}                               |
|                                       |
|o8 : List                              |
+---------------------------------------+
|i9 : isConnected G                     |
|                                       |
|o9 = true                              |
+---------------------------------------+

See also
========

  * Connected Components Tutorial, --
    clarifying the difference between graph and hypergraph components
  * isConnectedGraph -- determines if a graph is
    connected
  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex
  * isolatedVertices -- returns all vertices not
    contained in any edge
  * numConnectedComponents -- returns the number
    of connected components in a (hyper)graph

Ways to use isConnected:
========================

  * "isConnected(HyperGraph)"

For the programmer
==================

The object isConnected, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3229:0.

isConnectedGraph -- determines if a graph is connected
******************************************************

  * Usage:
        b = isConnectedGraph G
  * Inputs:
      * G, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if G is
        connected, false otherwise

Description
===========

This function checks if the given graph G is connected. A graph is said to be
connected if it has exactly one connected component.

Isolated vertices form their own connected components and will cause this
method return false. This is in contrast to isConnected, in
which isolated vertices are not in any connected components. See the
Connected Components Tutorial, for more
information.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : G = graph {a*b,b*c,c*d,d*e,a*e} -- the 5-cycle (connected)              |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}              |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : H = graph {a*b,b*c,c*a,d*e} -- a 3-cycle and a disjoint edge (not       |
|                                                                             |
|o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {d, e}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o3 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|connected)                                                                   |
+-----------------------------------------------------------------------------+
|i4 : isConnectedGraph G                                                      |
|                                                                             |
|o4 = true                                                                    |
+-----------------------------------------------------------------------------+
|i5 : isConnectedGraph H                                                      |
|                                                                             |
|o5 = false                                                                   |
+-----------------------------------------------------------------------------+

In the following example, the graph G has the isolated vertex e. As d forms its
own connected component, this graph is not connected.

+-----------------------------------------------------------------------------+
|i6 : S = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i7 : G = graph {a*b,b*c,c*d,a*d} -- 4-cycle with isolated vertex (not        |
|                                                                             |
|o7 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o7 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|connected)                                                                   |
+-----------------------------------------------------------------------------+
|i8 : isolatedVertices G                                                      |
|                                                                             |
|o8 = {e}                                                                     |
|                                                                             |
|o8 : List                                                                    |
+-----------------------------------------------------------------------------+
|i9 : isConnectedGraph G                                                      |
|                                                                             |
|o9 = false                                                                   |
+-----------------------------------------------------------------------------+

See also
========

  * Connected Components Tutorial, --
    clarifying the difference between graph and hypergraph components
  * connectedGraphComponents -- returns the
    connected components of a graph
  * isConnected -- determines if a (hyper)graph is
    connected
  * isolatedVertices -- returns all vertices not
    contained in any edge
  * numConnectedGraphComponents -- returns
    the number of connected components in a graph

Ways to use isConnectedGraph:
=============================

  * "isConnectedGraph(HyperGraph)"

For the programmer
==================

The object isConnectedGraph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3279:0.

isEdge -- determines if an edge is in a (hyper)graph
****************************************************

  * Usage:
        b = isEdge(H,E)
        b = isEdge(H,M)
  * Inputs:
      * H, a hypergraph,
      * E, a list (Macaulay2Doc), of vertices
      * M, a ring element (Macaulay2Doc), a monomial
        representing an edge
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true iff E (or
        support M) is an edge of H

Description
===========

This function checks if a given edge, represented either as a list or monomial,
belongs to a given (hyper)graph.

+--------------------------------------------------------------------------+
|i1 : S = QQ[z_1..z_8];                                                    |
+--------------------------------------------------------------------------+
|i2 : h = hyperGraph {z_2*z_3*z_4,z_6*z_8,z_7*z_5,z_1*z_6*z_7,z_2*z_4*z_8};|
+--------------------------------------------------------------------------+
|i3 : edges h                                                              |
|                                                                          |
|o3 = {{z , z , z }, {z , z }, {z , z , z }, {z , z , z }, {z , z }}       |
|        2   3   4     5   7     1   6   7     2   4   8     6   8         |
|                                                                          |
|o3 : List                                                                 |
+--------------------------------------------------------------------------+
|i4 : isEdge (h,{z_2,z_4,z_8})                                             |
|                                                                          |
|o4 = true                                                                 |
+--------------------------------------------------------------------------+
|i5 : isEdge (h,z_2*z_3*z_4)                                               |
|                                                                          |
|o5 = true                                                                 |
+--------------------------------------------------------------------------+
|i6 : isEdge (h,{z_1,z_2})                                                 |
|                                                                          |
|o6 = false                                                                |
+--------------------------------------------------------------------------+

See also
========

  * getEdgeIndex -- finds the index of an edge in a
    HyperGraph

Ways to use isEdge:
===================

  * "isEdge(HyperGraph,List)"
  * "isEdge(HyperGraph,RingElement)"

For the programmer
==================

The object isEdge, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3319:0.

isForest -- determines whether a (hyper)graph is a forest
*********************************************************

  * Usage:
        b = isForest G
        b = isForest H
  * Inputs:
      * G, a graph,
      * H, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if G (or H) is a
        forest

Description
===========

This function determines if a graph or hypergraph is a forest.  A graph is a
forest if if the graph has no cycles. We say that a hypergraph is forest if
each connected component is a tree in the sense of S. Faridi.  See the paper
"The facet ideal of a simplicial complex," Manuscripta Mathematica 109, 159-174
(2002).

+-------------------------------------------------------------+
|i1 : S = QQ[a..f];                                           |
+-------------------------------------------------------------+
|i2 : t = graph {a*b,a*c,a*e}                                 |
|                                                             |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, e}}}              |
|           "ring" => S                                       |
|           "vertices" => {a, b, c, d, e, f}                  |
|                                                             |
|o2 : Graph                                                   |
+-------------------------------------------------------------+
|i3 : isForest t                                              |
|                                                             |
|o3 = true                                                    |
+-------------------------------------------------------------+
|i4 : h = hyperGraph {a*b*c,c*d*e,b*d*f}                      |
|                                                             |
|o4 = HyperGraph{"edges" => {{a, b, c}, {c, d, e}, {b, d, f}}}|
|                "ring" => S                                  |
|                "vertices" => {a, b, c, d, e, f}             |
|                                                             |
|o4 : HyperGraph                                              |
+-------------------------------------------------------------+
|i5 : isForest h                                              |
|                                                             |
|o5 = false                                                   |
+-------------------------------------------------------------+

Ways to use isForest:
=====================

  * "isForest(Graph)"
  * "isForest(HyperGraph)"

For the programmer
==================

The object isForest, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3353:0.

isGoodLeaf -- determines if an edge is a good leaf
**************************************************

  * Usage:
        b = isGoodLeaf(H,n)
  * Inputs:
      * H, a hypergraph,
      * n, an integer (Macaulay2Doc), index of an edge
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if edge n of H
        is a good leaf

Description
===========

A good leaf of hypergraph H is an edge L whose intersections with all other
edges form a totally ordered set. It follows that L must have a free vertex. In
the graph setting, a good leaf is an edge containing a vertex of degree one.
The notion of a good leaf was introduced by X. Zheng in her Ph.D. thesis
(2004).

+---------------------------------------------------------------+
|i1 : R = QQ[a..g];                                             |
+---------------------------------------------------------------+
|i2 : H = hyperGraph {a*b*c*d, b*c*d*e, c*d*f, d*g, e*f*g};     |
+---------------------------------------------------------------+
|i3 : edges(H)                                                  |
|                                                               |
|o3 = {{a, b, c, d}, {b, c, d, e}, {c, d, f}, {d, g}, {e, f, g}}|
|                                                               |
|o3 : List                                                      |
+---------------------------------------------------------------+
|i4 : isGoodLeaf(H,0)                                           |
|                                                               |
|o4 = true                                                      |
+---------------------------------------------------------------+
|i5 : isGoodLeaf(H,1)                                           |
|                                                               |
|o5 = false                                                     |
+---------------------------------------------------------------+

See also
========

  * getGoodLeaf -- returns an edge that is a good leaf
  * getGoodLeafIndex -- returns the index of an edge
    that is a good leaf
  * hasGoodLeaf -- determines if a HyperGraph contains a
    good leaf

Ways to use isGoodLeaf:
=======================

  * "isGoodLeaf(HyperGraph,ZZ)"

For the programmer
==================

The object isGoodLeaf, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3391:0.

isGraph -- determines if a hypergraph is a graph
************************************************

  * Usage:
        b = isGraph H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if all edges in
        H have size two

Description
===========

+--------------------------------------+
|i1 : QQ[a,b,c,d];                     |
+--------------------------------------+
|i2 : isGraph(hyperGraph {a*b,b*c,c*d})|
|                                      |
|o2 = true                             |
+--------------------------------------+
|i3 : isGraph(hyperGraph {a*b,b*c*d})  |
|                                      |
|o3 = false                            |
+--------------------------------------+
|i4 : isGraph(hyperGraph {a*b,b*c,d})  |
|                                      |
|o4 = false                            |
+--------------------------------------+

Ways to use isGraph:
====================

  * "isGraph(HyperGraph)"

For the programmer
==================

The object isGraph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3416:0.

isLeaf -- determines if an edge (or vertex) is a leaf of a (hyper)graph
***********************************************************************

  * Usage:
        b = isLeaf(G,N)
        b = isLeaf(H,n)
        b = isLeaf(H,V)
  * Inputs:
      * G, a graph,
      * H, a hypergraph,
      * n, an integer (Macaulay2Doc), an index of an edge
      * V, a ring element (Macaulay2Doc), a vertex
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if edge n is a
        leaf or if vertex V has degree 1

Description
===========

An edge in a graph is a leaf if it contains a vertex of degree one. An edge E
in a hypergraph is a leaf if there is another edge B with the property that for
all edges F (other than E), the intersection of F with E is contained in the
intersection of B with E.

A vertex of a graph is a leaf if it has degree one. A vertex of a hypergraph is
a leaf if it is contained in precisely one edge which is itself is leaf.

+------------------------------------------+
|i1 : R = QQ[a..f];                        |
+------------------------------------------+
|i2 : G = graph {a*b,b*c,c*a,b*d};         |
+------------------------------------------+
|i3 : isLeaf(G, d)                         |
|                                          |
|o3 = true                                 |
+------------------------------------------+
|i4 : isLeaf(G, getEdgeIndex(G, {b,d}))    |
|                                          |
|o4 = true                                 |
+------------------------------------------+
|i5 : isLeaf(G, a)                         |
|                                          |
|o5 = false                                |
+------------------------------------------+
|i6 : isLeaf(G, getEdgeIndex(G, {a,b}))    |
|                                          |
|o6 = false                                |
+------------------------------------------+
|i7 : H = hyperGraph {a*b*c,b*d,c*e,b*c*f};|
+------------------------------------------+
|i8 : K = hyperGraph {a*b*c,b*d,c*e};      |
+------------------------------------------+
|i9 : isLeaf(H, a)                         |
|                                          |
|o9 = true                                 |
+------------------------------------------+
|i10 : isLeaf(H, getEdgeIndex(H, {a,b,c})) |
|                                          |
|o10 = true                                |
+------------------------------------------+
|i11 : isLeaf(K, a)                        |
|                                          |
|o11 = false                               |
+------------------------------------------+
|i12 : isLeaf(K, getEdgeIndex(K, {a,b,c})) |
|                                          |
|o12 = false                               |
+------------------------------------------+

See also
========

  * isForest -- determines whether a (hyper)graph is a forest
  * isGoodLeaf -- determines if an edge is a good leaf

Ways to use isLeaf:
===================

  * "isLeaf(Graph,ZZ)"
  * "isLeaf(HyperGraph,RingElement)"
  * "isLeaf(HyperGraph,ZZ)"

For the programmer
==================

The object isLeaf, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3470:0.

isolatedVertices -- returns all vertices not contained in any edge
******************************************************************

  * Usage:
        L = isolatedVertices(H)
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * L, a list (Macaulay2Doc), all vertices that are not
        contained in any edge of H

Description
===========

A vertex of a hypergraph is called isolated if it is not contained in any
edges. Vertices in a hypergraph that are contained in an edge of size one are
not considered to be isolated.

+----------------------------------------------+
|i1 : R = QQ[a,b,c,d,e];                       |
+----------------------------------------------+
|i2 : G = graph {a*b,c*d}                      |
|                                              |
|o2 = Graph{"edges" => {{a, b}, {c, d}}  }     |
|           "ring" => R                        |
|           "vertices" => {a, b, c, d, e}      |
|                                              |
|o2 : Graph                                    |
+----------------------------------------------+
|i3 : isolatedVertices G                       |
|                                              |
|o3 = {e}                                      |
|                                              |
|o3 : List                                     |
+----------------------------------------------+
|i4 : H = hyperGraph {a*b,c}                   |
|                                              |
|o4 = HyperGraph{"edges" => {{a, b}, {c}}     }|
|                "ring" => R                   |
|                "vertices" => {a, b, c, d, e} |
|                                              |
|o4 : HyperGraph                               |
+----------------------------------------------+
|i5 : isolatedVertices H                       |
|                                              |
|o5 = {d, e}                                   |
|                                              |
|o5 : List                                     |
+----------------------------------------------+

See also
========

  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex
  * isConnected -- determines if a (hyper)graph is
    connected
  * numConnectedComponents -- returns the number
    of connected components in a (hyper)graph

Ways to use isolatedVertices:
=============================

  * "isolatedVertices(HyperGraph)"

For the programmer
==================

The object isolatedVertices, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3503:0.

isPerfect -- determines whether a graph is perfect
**************************************************

  * Usage:
        b = isPerfect G
  * Inputs:
      * G, a graph,
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if G is perfect
        and false otherwise

Description
===========

The algorithm uses the Strong Perfect Graph Theorem, which says that G is
perfect if and only if neither G nor its complement contains an odd hole. See
hasOddHole, is used to determine whether these conditions hold.

+----------------------------------------------------------------+
|i1 : R = QQ[x_1..x_7];                                          |
+----------------------------------------------------------------+
|i2 : G = complementGraph cycle R; --odd antihole with 7 vertices|
+----------------------------------------------------------------+
|i3 : isPerfect G                                                |
|                                                                |
|o3 = false                                                      |
+----------------------------------------------------------------+
|i4 : H = cycle(R,4)                                             |
|                                                                |
|o4 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }}} |
|                         1   2     2   3     3   4     1   4    |
|           "ring" => R                                          |
|           "vertices" => {x , x , x , x , x , x , x }           |
|                           1   2   3   4   5   6   7            |
|                                                                |
|o4 : Graph                                                      |
+----------------------------------------------------------------+
|i5 : isPerfect H                                                |
|                                                                |
|o5 = true                                                       |
+----------------------------------------------------------------+

See also
========

  * hasOddHole -- tells whether a graph contains an odd hole

Ways to use isPerfect:
======================

  * "isPerfect(Graph)"

For the programmer
==================

The object isPerfect, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3536:0.

isSCM -- determines if a (hyper)graph is sequentially Cohen-Macaulay
********************************************************************

  * Usage:
        b = isSCM H
  * Inputs:
      * H, a hypergraph,
  * Optional inputs (Macaulay2Doc),:
      * Gins, => ..., default
        value false, use gins inside isSCM
  * Outputs:
      * b, a Boolean value (Macaulay2Doc), true if the
        edgeIdeal, of H is sequentially Cohen-Macaulay

Description
===========

This uses the edge ideal notion of sequential Cohen-Macaulayness; a hypergraph
is called SCM if and only if its edge ideal is SCM. The algorithm is based on
work of Herzog and Hibi, using the Alexander dual. H is SCM if and only if the
Alexander dual of the edge ideal of H is componentwise linear.

There is an optional argument called Gins, for isSCM. The default
value is false, meaning that isSCM takes the Alexander dual of the edge ideal
of H and checks in all relevant degrees to see if the ideal in that degree has
a linear resolution. In characteristic zero with the reverse-lex order, one can
test for componentwise linearity using gins, which may be faster in some cases.
This approach is based on work of Aramova-Herzog-Hibi and Conca. We make no
attempt to check the characteristic of the field or the monomial order, so use
caution when using this method.

+--------------------------------------------------------------------------+
|i1 : R = QQ[a..f];                                                        |
+--------------------------------------------------------------------------+
|i2 : G = cycle(R,4)                                                       |
|                                                                          |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, d}}}                   |
|           "ring" => R                                                    |
|           "vertices" => {a, b, c, d, e, f}                               |
|                                                                          |
|o2 : Graph                                                                |
+--------------------------------------------------------------------------+
|i3 : isSCM G                                                              |
|                                                                          |
|o3 = false                                                                |
+--------------------------------------------------------------------------+
|i4 : H = graph(monomialIdeal(a*b,b*c,c*d,a*d,a*e)); --4-cycle with whisker|
+--------------------------------------------------------------------------+
|i5 : isSCM H                                                              |
|                                                                          |
|o5 = true                                                                 |
+--------------------------------------------------------------------------+
|i6 : isSCM(H,Gins=>true) --use Gins technique                             |
|                                                                          |
|o6 = true                                                                 |
+--------------------------------------------------------------------------+

See also
========

  * isCM -- determines if a (hyper)graph is Cohen-Macaulay
  * edgeIdeal -- creates the edge ideal of a (hyper)graph

Ways to use isSCM:
==================

  * "isSCM(HyperGraph)"

For the programmer
==================

The object isSCM, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3582:0.

isSCM(...,Gins=>...) -- use gins inside isSCM
*********************************************

  * Usage:
        B = isSCM(H,Gins=>true)
  * Inputs:
      * H, a hypergraph, the hypergraph being considered
  * Outputs:
      * B, a Boolean value (Macaulay2Doc), whether H is SCM or
        not

Description
===========

The default value for Gins is false since using generic initial ideals makes
the isSCM, algorithm probabilistic, and there are characteristic
and monomial order requirements. See full discussion at isSCM.

See also
========

  * isSCM -- determines if a (hyper)graph is sequentially
    Cohen-Macaulay

Functions with optional argument named Gins:
============================================

  * isSCM(...,Gins=>...) -- use
    gins inside isSCM

Further information
===================

  * Default value: false (Macaulay2Doc),
  * Function: isSCM, -- determines if a (hyper)graph is
    sequentially Cohen-Macaulay
  * Option key: Gins, -- optional argument for isSCM
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4217:0.

lineGraph -- returns the line graph of a (hyper)graph
*****************************************************

  * Usage:
        L = lineGraph H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * L, a graph, the line graph of H

Description
===========

The line graph L of a hypergraph H has a vertex for each edge in H. Two
vertices in L are adjacent if their edges in H share a vertex. The order of the
vertices in L are determined by the implicit order on the edges of H. See
edges.

+---------------------------------------------------------------+
|i1 : R = QQ[a..e];                                             |
+---------------------------------------------------------------+
|i2 : G = graph {a*b,a*c,a*d,d*e}                               |
|                                                               |
|o2 = Graph{"edges" => {{a, b}, {a, c}, {a, d}, {d, e}}}        |
|           "ring" => R                                         |
|           "vertices" => {a, b, c, d, e}                       |
|                                                               |
|o2 : Graph                                                     |
+---------------------------------------------------------------+
|i3 : lineGraph G                                               |
|                                                               |
|o3 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }}}|
|                         0   1     0   2     1   2     2   3   |
|           "ring" => QQ[x ..x ]                                |
|                         0   3                                 |
|           "vertices" => {x , x , x , x }                      |
|                           0   1   2   3                       |
|                                                               |
|o3 : Graph                                                     |
+---------------------------------------------------------------+

See also
========

  * edges -- gets the edges of a (hyper)graph

Ways to use lineGraph:
======================

  * "lineGraph(HyperGraph)"

For the programmer
==================

The object lineGraph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3613:0.

MaximalEdges -- optional argument for changeRing
************************************************

Description
===========

This is an option to tell changeRing, whether to make a
hypergraph using maximal or minimal edges after substitution for the variables.

Functions with optional argument named MaximalEdges:
====================================================

  * changeRing(...,MaximalEdges=>...)
    -- optional argument
    for changeRing

For the programmer
==================

The object MaximalEdges, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4282:0.

neighbors -- returns the neighbors of a vertex or list of vertices
******************************************************************

  * Usage:
        N = neighbors(H,V)
        N = neighbors(H,n)
        N = neighbors(H,L)
  * Inputs:
      * H, a hypergraph,
      * V, a ring element (Macaulay2Doc), a vertex
      * n, an integer (Macaulay2Doc), the index of a vertex
      * L, a list (Macaulay2Doc), a list of vertices or indices of
        vertices
  * Outputs:
      * N, a list (Macaulay2Doc), of neighbors to the given vertex
        or vertices

Description
===========

The vertices adjacent to vertex V are called the neighbors of V. The neighbors
of a list of vertices L are those vertices that are not in L and are adjacent
to a vertex in L.

+-----------------------------------------+
|i1 : R = QQ[a..f];                       |
+-----------------------------------------+
|i2 : G = graph {a*b, a*c, a*d, d*e, d*f};|
+-----------------------------------------+
|i3 : neighbors(G,a)                      |
|                                         |
|o3 = {b, c, d}                           |
|                                         |
|o3 : List                                |
+-----------------------------------------+
|i4 : neighbors(G,0)                      |
|                                         |
|o4 = {b, c, d}                           |
|                                         |
|o4 : List                                |
+-----------------------------------------+
|i5 : neighbors(G,{a,d})                  |
|                                         |
|o5 = {b, c, e, f}                        |
|                                         |
|o5 : List                                |
+-----------------------------------------+
|i6 : neighbors(G,{0,3})                  |
|                                         |
|o6 = {b, c, e, f}                        |
|                                         |
|o6 : List                                |
+-----------------------------------------+

See also
========

  * degreeVertex -- returns the degree of a vertex
  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

Ways to use neighbors:
======================

  * "neighbors(HyperGraph,List)"
  * "neighbors(HyperGraph,RingElement)"
  * "neighbors(HyperGraph,ZZ)"

For the programmer
==================

The object neighbors, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3657:0.

numConnectedComponents -- returns the number of connected components in a (hyper)graph
**************************************************************************************

  * Usage:
        d = numConnectedComponents H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * d, an integer (Macaulay2Doc), the number of connected
        components of H

Description
===========

This function returns the number of connected components of a hypergraph. A
connected component of a hypergraph is any maximal set of vertices which are
pairwise connected by a non-trivial path.  Isolated vertices, which are those
not appearing in any edge, do not count as connected components. This is in
contrast to numConnectedGraphComponents, in
which isolated vertices are counted as connected components. See the
Connected Components Tutorial, for more
information.

The algorithm used by numConnectedComponents turns H into a simplicial complex,
and then computes the rank of the 0^{th} reduced homology group. This number
plus 1 gives the number of connected components of H.

We depart from this method in two cases: We define the hypergraph with only the
empty edge (corresponding to the irrelevant simplicial complex) and the
hypergraph with empty edge set (corresponding to the void simplicial complex)
to have 0 connected components.

Although this method can be applied to graphs, its output does not match the
most common meaning for the number of connected components of a graph. Instead,
one should use numConnectedGraphComponents.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*e,a*e} -- the 5-cycle (connected)              |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}              |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : h = graph {a*b,b*c,c*a,d*e} -- a 3-cycle and a disjoint edge (not       |
|                                                                             |
|o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {d, e}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o3 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|connected)                                                                   |
+-----------------------------------------------------------------------------+
|i4 : numConnectedComponents g                                                |
|                                                                             |
|o4 = 1                                                                       |
+-----------------------------------------------------------------------------+
|i5 : numConnectedComponents h                                                |
|                                                                             |
|o5 = 2                                                                       |
+-----------------------------------------------------------------------------+

The following example contains a hypergraph with an edge of size one. The
vertex in this edge is not considered isolated and does count as a connected
component.

+-------------------------------------------+
|i6 : S = QQ[a..d];                         |
+-------------------------------------------+
|i7 : H = hyperGraph {a*b,c}                |
|                                           |
|o7 = HyperGraph{"edges" => {{a, b}, {c}}  }|
|                "ring" => S                |
|                "vertices" => {a, b, c, d} |
|                                           |
|o7 : HyperGraph                            |
+-------------------------------------------+
|i8 : isolatedVertices H                    |
|                                           |
|o8 = {d}                                   |
|                                           |
|o8 : List                                  |
+-------------------------------------------+
|i9 : connectedComponents H                 |
|                                           |
|o9 = {{a, b}, {c}}                         |
|                                           |
|o9 : List                                  |
+-------------------------------------------+
|i10 : numConnectedComponents H             |
|                                           |
|o10 = 2                                    |
+-------------------------------------------+

See also
========

  * Connected Components Tutorial, --
    clarifying the difference between graph and hypergraph components
  * connectedComponents (SimplicialComplexes)
    -- find
    the connected components of an abstract simplicial complex
  * numConnectedGraphComponents -- returns
    the number of connected components in a graph
  * isConnected -- determines if a (hyper)graph is
    connected
  * isolatedVertices -- returns all vertices not
    contained in any edge

Ways to use numConnectedComponents:
===================================

  * "numConnectedComponents(HyperGraph)"

For the programmer
==================

The object numConnectedComponents, is a
method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3719:0.

numConnectedGraphComponents -- returns the number of connected components in a graph
************************************************************************************

  * Usage:
        d = numConnectedGraphComponents G
  * Inputs:
      * G, a hypergraph,
  * Outputs:
      * d, an integer (Macaulay2Doc), the number of connected
        components of G

Description
===========

This function returns the number of connected components of a graph. A
connected component of a graph is any maximal set of vertices which are
pairwise connected by a path.  Isolated vertices, which are those not appearing
in any edge, count as connected components. This is in contrast to
numConnectedComponents, in which isolated vertices are
not counted as connected components. See the Connected Components Tutorial,
for more information.

The algorithm used by numConnectedGraphComponents turns G into a simplicial
complex, and then computes the rank of the 0^{th} reduced homology group. This
number plus 1 plus the number of isolated vertices of G gives the number of
connected components of G.

This method is intended to match the most common meaning for the number of
connected components of a graph. This method can also be used on hypergraphs.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*e,a*e} -- the 5-cycle (connected)              |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}}              |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : h = graph {a*b,b*c,c*a,d*e} -- a 3-cycle and a disjoint edge (not       |
|                                                                             |
|o3 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {d, e}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o3 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|connected)                                                                   |
+-----------------------------------------------------------------------------+
|i4 : k = graph {a*b,b*c,c*d,a*d} -- 4-cycle and isolated vertex (not         |
|                                                                             |
|o4 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|connected)                                                                   |
+-----------------------------------------------------------------------------+
|i5 : numConnectedGraphComponents g                                           |
|                                                                             |
|o5 = 1                                                                       |
+-----------------------------------------------------------------------------+
|i6 : numConnectedGraphComponents h                                           |
|                                                                             |
|o6 = 2                                                                       |
+-----------------------------------------------------------------------------+
|i7 : numConnectedGraphComponents k                                           |
|                                                                             |
|o7 = 2                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * Connected Components Tutorial, --
    clarifying the difference between graph and hypergraph components
  * connectedGraphComponents -- returns the
    connected components of a graph
  * isConnectedGraph -- determines if a graph is
    connected
  * isolatedVertices -- returns all vertices not
    contained in any edge
  * numConnectedComponents -- returns the number
    of connected components in a (hyper)graph

Ways to use numConnectedGraphComponents:
========================================

  * "numConnectedGraphComponents(HyperGraph)"

For the programmer
==================

The object numConnectedGraphComponents, is a
method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3770:0.

numTriangles -- returns the number of triangles in a graph
**********************************************************

  * Usage:
        d = numTriangles G
  * Inputs:
      * G, a graph,
  * Outputs:
      * d, an integer (Macaulay2Doc), the number of triangles
        contained in G

Description
===========

This method is based on work of Francisco-Ha-Van Tuyl, looking at the
associated primes of the square of the Alexander dual of the edge ideal. The
algorithm counts the number of these associated primes of height 3.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd
holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_6];                                                       |
+-----------------------------------------------------------------------------+
|i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5|
|                                                                             |
|o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     1   5     4   5     1 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|-cycle and a triangle                                                        |
|                                                                             |
| x }, {x , x }}}                                                             |
|  6     5   6                                                                |
+-----------------------------------------------------------------------------+
|i3 : numTriangles G                                                          |
|                                                                             |
|o3 = 1                                                                       |
+-----------------------------------------------------------------------------+
|i4 : H = completeGraph R;                                                    |
+-----------------------------------------------------------------------------+
|i5 : numTriangles H == binomial(6,3)                                         |
|                                                                             |
|o5 = true                                                                    |
+-----------------------------------------------------------------------------+

See also
========

  * allOddHoles -- returns all odd holes in a graph
  * getCliques -- returns cliques in a graph

Ways to use numTriangles:
=========================

  * "numTriangles(Graph)"

For the programmer
==================

The object numTriangles, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3807:0.

OriginalRing -- optional argument for inducedHyperGraph
*******************************************************

Description
===========

This is an option to tell inducedGraph, and
inducedHyperGraph, whether to return a (hyper)graph with the
original (larger) ring attached or the subring only involving the variables of
L. The smaller ring is the default.

See also
========

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

Functions with optional argument named OriginalRing:
====================================================

  * inducedGraph(...,OriginalRing=>...)
    -- use OriginalRing
    inside inducedGraph or inducedHyperGraph
  * "inducedHyperGraph(...,OriginalRing=>...)" -- see
    inducedGraph(...,OriginalRing=>...),
    -- use OriginalRing
    inside inducedGraph or inducedHyperGraph

For the programmer
==================

The object OriginalRing, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4315:0.

randomGraph -- returns a random graph
*************************************

  * Usage:
        G = randomGraph(R,d)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), which gives
        the vertex set of G
      * d, an integer (Macaulay2Doc), the number of edges in G
  * Outputs:
      * G, a graph, a graph with d edges on vertex set determined
        by R

Description
===========

This function allows one to create a graph on an underlying vertex set with a
given number of randomly chosen edges.

+---------------------------------------------------------------+
|i1 : R = QQ[x_1..x_9];                                         |
+---------------------------------------------------------------+
|i2 : randomGraph(R,4)                                          |
|                                                               |
|o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }}}|
|                         3   4     1   4     6   7     1   9   |
|           "ring" => R                                         |
|           "vertices" => {x , x , x , x , x , x , x , x , x }  |
|                           1   2   3   4   5   6   7   8   9   |
|                                                               |
|o2 : Graph                                                     |
+---------------------------------------------------------------+
|i3 : randomGraph(R,4)                                          |
|                                                               |
|o3 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }}}|
|                         4   9     5   6     5   7     4   5   |
|           "ring" => R                                         |
|           "vertices" => {x , x , x , x , x , x , x , x , x }  |
|                           1   2   3   4   5   6   7   8   9   |
|                                                               |
|o3 : Graph                                                     |
+---------------------------------------------------------------+

See also
========

  * randomUniformHyperGraph -- returns a random
    uniform hypergraph
  * randomHyperGraph -- returns a random hypergraph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use randomGraph:
========================

  * "randomGraph(PolynomialRing,ZZ)"

For the programmer
==================

The object randomGraph, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3841:0.

randomHyperGraph -- returns a random hypergraph
***********************************************

  * Usage:
        H = randomHyperGraph(R,D)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), which gives
        the vertex set of H
      * D, a list (Macaulay2Doc), of integers that are the
        cardinalities of the edges of H
  * Optional inputs (Macaulay2Doc),:
      * BranchLimit,
        => ..., default value 3, limit recursive branching in
        randomHyperGraph
      * TimeLimit,
        => ..., default value 5, limit the running time of randomHyperGraph
  * Outputs:
      * H, a hypergraph, a hypergraph with edges E_i each of
        size D_i. Returns null if none can be found.

Description
===========

This method is not guaranteed to return a HyperGraph, even if one exists with
the given edge sizes. This method searches for a hypergraph with the given edge
sizes using a random recursive algorithm. Limits can be placed on the both
number of recursive steps taken (see BranchLimit) and on
the time taken (see TimeLimit). The method will return null
if it cannot find a hypergraph within the branch and time limits.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_5];                                                       |
+-----------------------------------------------------------------------------+
|i2 : randomHyperGraph(R,{3,2,4})                                             |
+-----------------------------------------------------------------------------+
|i3 : randomHyperGraph(R,{3,2,4})                                             |
+-----------------------------------------------------------------------------+
|i4 : randomHyperGraph(R,{3,2,4})                                             |
|                                                                             |
|o4 = HyperGraph{"edges" => {{x , x , x }, {x , x }, {x , x , x , x }}}       |
|                              1   3   5     2   3     1   2   4   5          |
|                "ring" => R                                                  |
|                "vertices" => {x , x , x , x , x }                           |
|                                1   2   3   4   5                            |
|                                                                             |
|o4 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i5 : randomHyperGraph(R,{4,4,2,2}) -- impossible, returns null when          |
|-----------------------------------------------------------------------------|
|time/branch limit reached                                                    |
+-----------------------------------------------------------------------------+

The randomHyperGraph method will return null immediately if the sizes of the
edges fail to pass the LYM-inequality: $1/(n choose D_1) + 1/(n choose D_2) +
... + 1/(n choose D_m) \leq 1$ where $n$ is the number of variables in R and
$m$ is the length of D. Note that even if D passes this inequality, it is not
necessarily true that there is some hypergraph with edge sizes given by D. See
D. Lubell's "A short proof of Sperner's lemma," J. Combin. Theory, 1:299
(1966).

See also
========

  * randomGraph -- returns a random graph
  * randomUniformHyperGraph -- returns a random
    uniform hypergraph
  * BranchLimit -- optional argument for randomHyperGraph
  * TimeLimit -- optional argument for randomHyperGraph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use randomHyperGraph:
=============================

  * "randomHyperGraph(PolynomialRing,List)"

For the programmer
==================

The object randomHyperGraph, is a method function with options (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3888:0.

randomHyperGraph(...,BranchLimit=>...) -- limit recursive branching in randomHyperGraph
***************************************************************************************

  * Usage:
        G = randomHyperGraph(R,D,BranchLimit=>n)
  * Inputs:
      * n, an integer (Macaulay2Doc), number of branches at each
        level in the recursion of randomHyperGraph

Description
===========

The randomHyperGraph, method follows a backtracking
algorithm to generate edges with no inclusions between them. At each step in
the recursive tree,  see randomHyperGraph, will make
BranchLimit attempts to complete its list of edges. Thus, if a hypergraph with
N edges is required, see randomHyperGraph, may take
BranchLimit^N steps before terminating. To be more precise, the method is
implemented so that it makes BranchLimit + L attempts at level L of the
recursion. The default value is 3.

See also
========

  * TimeLimit -- optional argument for randomHyperGraph
  * randomHyperGraph -- returns a random hypergraph

Functions with optional argument named BranchLimit:
===================================================

  * randomHyperGraph(...,BranchLimit=>...)
    -- limit
    recursive branching in randomHyperGraph

Further information
===================

  * Default value: 3
  * Function: randomHyperGraph, -- returns a random
    hypergraph
  * Option key: BranchLimit, -- optional argument for
    randomHyperGraph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4266:0.

randomHyperGraph(...,TimeLimit=>...) -- limit the running time of randomHyperGraph
**********************************************************************************

  * Usage:
        randomHyperGraph(R,D,TimeLimit=>s)
  * Inputs:
      * s, an integer (Macaulay2Doc), time in seconds before
        randomHyperGraph returns null

Description
===========

The randomHyperGraph, method follows a backtracking
algorithm to generate edges with no inclusions between them. As it may take a
long time to terminate, a time limit is imposed on the method. The TimeLimit
option is the amount of time, in seconds, that the method
randomHyperGraph, will take before terminating. A value of 0
is interpreted as one day. The default value is 5 (seconds).

See also
========

  * BranchLimit -- optional argument for randomHyperGraph
  * randomHyperGraph -- returns a random hypergraph

Functions with optional argument named TimeLimit:
=================================================

  * randomHyperGraph(...,TimeLimit=>...)
    -- limit the
    running time of randomHyperGraph

Further information
===================

  * Default value: 5
  * Function: randomHyperGraph, -- returns a random
    hypergraph
  * Option key: TimeLimit, -- optional argument for
    randomHyperGraph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4391:0.

randomUniformHyperGraph -- returns a random uniform hypergraph
**************************************************************

  * Usage:
        H = randomUniformHyperGraph(R,c,d)
  * Inputs:
      * R, a polynomial ring (Macaulay2Doc), which gives
        the vertex set of H
      * c, an integer (Macaulay2Doc), the cardinality of the edge
        sets
      * d, an integer (Macaulay2Doc), the number of edges in H
  * Outputs:
      * H, a hypergraph, a hypergraph with d edges of
        cardinality c on vertex set determined by R

Description
===========

This function allows one to create a uniform hypergraph on an underlying vertex
set with a given number of randomly chosen edges of given cardinality.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_9];                                                       |
+-----------------------------------------------------------------------------+
|i2 : randomUniformHyperGraph(R,3,4)                                          |
|                                                                             |
|o2 = HyperGraph{"edges" => {{x , x , x }, {x , x , x }, {x , x , x }, {x ,   |
|                              5   6   9     2   6   8     4   7   8     3    |
|                "ring" => R                                                  |
|                "vertices" => {x , x , x , x , x , x , x , x , x }           |
|                                1   2   3   4   5   6   7   8   9            |
|                                                                             |
|o2 : HyperGraph                                                              |
|-----------------------------------------------------------------------------|
|x , x }}}                                                                    |
| 5   7                                                                       |
+-----------------------------------------------------------------------------+
|i3 : randomUniformHyperGraph(R,4,2)                                          |
|                                                                             |
|o3 = HyperGraph{"edges" => {{x , x , x , x }, {x , x , x , x }}   }          |
|                              2   3   4   9     2   3   4   8                |
|                "ring" => R                                                  |
|                "vertices" => {x , x , x , x , x , x , x , x , x }           |
|                                1   2   3   4   5   6   7   8   9            |
|                                                                             |
|o3 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+

See also
========

  * randomGraph -- returns a random graph
  * randomHyperGraph -- returns a random hypergraph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use randomUniformHyperGraph:
====================================

  * "randomUniformHyperGraph(PolynomialRing,ZZ,ZZ)"

For the programmer
==================

The object randomUniformHyperGraph, is a
method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3924:0.

ring(HyperGraph) -- gives the ring of a (hyper)graph
****************************************************

  * Function: ring (Macaulay2Doc),
  * Usage:
        R = ring H
  * Inputs:
      * H, a hypergraph,
  * Outputs:
      * R, a ring (Macaulay2Doc),

Description
===========

Every (hyper)graph is defined over some polynomial ring. This method returns
the ring of a hypergraph.

+--------------------------------------------+
|i1 : S = QQ[a..d];                          |
+--------------------------------------------+
|i2 : g = cycle S;                           |
+--------------------------------------------+
|i3 : h = inducedHyperGraph(g,{a,b,c});      |
+--------------------------------------------+
|i4 : describe ring g                        |
|                                            |
|o4 = QQ[a..d, Degrees => {4:1}, Heft => {1}]|
+--------------------------------------------+
|i5 : describe ring h                        |
|                                            |
|o5 = QQ[a..c, Degrees => {3:1}, Heft => {1}]|
+--------------------------------------------+

See also
========

  * edges -- gets the edges of a (hyper)graph
  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph

Ways to use this method:
========================

  * ring(HyperGraph) -- gives the ring of a
    (hyper)graph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3955:0.

simplicialComplexToHyperGraph -- makes a (hyper)graph from a simplicial complex
*******************************************************************************

  * Usage:
        H = simplicialComplexToHyperGraph(D)
  * Inputs:
      * D, an abstract simplicial complex (SimplicialComplexes),
        the input
  * Outputs:
      * H, a hypergraph, whose edges are the facets of D

Description
===========

This function makes a HyperGraph, from a
SimplicialComplex (SimplicialComplexes). The edges of the
HyperGraph are given by the facets of the SimplicialComplex. This is the
inverse of the function hyperGraphToSimplicialComplex.

+------------------------------------------------------------------------+
|i1 : S = QQ[a..f];                                                      |
+------------------------------------------------------------------------+
|i2 : Delta = simplicialComplex {a*b*c,b*c*d,c*d*e,d*e*f}                |
|                                                                        |
|o2 = simplicialComplex | def cde bcd abc |                              |
|                                                                        |
|o2 : SimplicialComplex                                                  |
+------------------------------------------------------------------------+
|i3 : H = simplicialComplexToHyperGraph Delta                            |
|                                                                        |
|o3 = HyperGraph{"edges" => {{a, b, c}, {b, c, d}, {c, d, e}, {d, e, f}}}|
|                "ring" => S                                             |
|                "vertices" => {a, b, c, d, e, f}                        |
|                                                                        |
|o3 : HyperGraph                                                         |
+------------------------------------------------------------------------+

See also
========

  * hyperGraphToSimplicialComplex, --
    makes a simplicial complex from a (hyper)graph
  * Constructor Overview -- a summary of the many
    ways of making graphs and hypergraphs

Ways to use simplicialComplexToHyperGraph:
==========================================

  * "simplicialComplexToHyperGraph(SimplicialComplex)"

For the programmer
==================

The object simplicialComplexToHyperGraph,
is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:3990:0.

smallestCycleSize -- returns the size of the smallest induced cycle of a graph
******************************************************************************

  * Usage:
        s = smallestCycleSize(G)
  * Inputs:
      * G, a graph, the input
  * Outputs:
      * s, an integer (Macaulay2Doc), the size of the smallest
        induced cycle

Description
===========

This function returns the size of the smallest induced cycle of a graph. It is
based upon Theorem 2.1 in the paper "Restricting linear syzygies: algebra and
geometry" by Eisenbud, Green, Hulek, and Popsecu.  This theorem states that if
G is graph, then the edge ideal of the complement of G satisfies property
N_{2,p}, that is, the resolution of I(G^c) is linear up to the p-th step, if
and only if the smallest induced cycle of G has length p+3.  The algorithm
looks at the resolution of the edge ideal of the complement to determine the
size of the smallest cycle.

+-----------------------------------------------------------------------------+
|i1 : T = QQ[x_1..x_9];                                                       |
+-----------------------------------------------------------------------------+
|i2 : g = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x|
|                                                                             |
|o2 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     4   5     5   6     6 |
|           "ring" => T                                                       |
|           "vertices" => {x , x , x , x , x , x , x , x , x }                |
|                           1   2   3   4   5   6   7   8   9                 |
|                                                                             |
|o2 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|_9,x_9*x_1} -- a 9-cycle                                                     |
|                                                                             |
| x }, {x , x }, {x , x }, {x , x }}}                                         |
|  7     7   8     1   9     8   9                                            |
+-----------------------------------------------------------------------------+
|i3 : smallestCycleSize g                                                     |
|                                                                             |
|o3 = 9                                                                       |
+-----------------------------------------------------------------------------+
|i4 : h = graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*x|
|                                                                             |
|o4 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     3   4     4   5     5   6     6 |
|           "ring" => T                                                       |
|           "vertices" => {x , x , x , x , x , x , x , x , x }                |
|                           1   2   3   4   5   6   7   8   9                 |
|                                                                             |
|o4 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|_9} -- a tree (no cycles)                                                    |
|                                                                             |
| x }, {x , x }, {x , x }}}                                                   |
|  7     7   8     8   9                                                      |
+-----------------------------------------------------------------------------+
|i5 : smallestCycleSize h                                                     |
|                                                                             |
|o5 = infinity                                                                |
|                                                                             |
|o5 : InfiniteNumber                                                          |
+-----------------------------------------------------------------------------+
|i6 : l =  graph {x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_5*x_6,x_6*x_7,x_7*x_8,x_8*|
|                                                                             |
|o6 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x ,|
|                         1   2     2   3     1   4     3   4     4   5     5 |
|           "ring" => T                                                       |
|           "vertices" => {x , x , x , x , x , x , x , x , x }                |
|                           1   2   3   4   5   6   7   8   9                 |
|                                                                             |
|o6 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|x_9,x_9*x_1,x_1*x_4}                                                         |
|                                                                             |
| x }, {x , x }, {x , x }, {x , x }, {x , x }}}                               |
|  6     6   7     7   8     1   9     8   9                                  |
+-----------------------------------------------------------------------------+
|i7 : smallestCycleSize l                                                     |
|                                                                             |
|o7 = 4                                                                       |
+-----------------------------------------------------------------------------+

Note that G is a tree if and only if smallestCycleSize G is infinity.

Ways to use smallestCycleSize:
==============================

  * "smallestCycleSize(Graph)"

For the programmer
==================

The object smallestCycleSize, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4031:0.

spanningTree -- returns a spanning tree of a graph
**************************************************

  * Usage:
        T = spanningTree(G)
  * Inputs:
      * G, a graph,
  * Outputs:
      * T, a graph, the spanning tree of G

Description
===========

This function returns a breadth first spanning tree of a graph.

+-----------------------------------------------------------------------------+
|i1 : R = QQ[x_1..x_6];                                                       |
+-----------------------------------------------------------------------------+
|i2 : C = cycle R; -- a 6-cycle                                               |
+-----------------------------------------------------------------------------+
|i3 : spanningTree C                                                          |
|                                                                             |
|o3 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}    |
|                         1   2     2   3     3   4     4   5     5   6       |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o3 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i4 : T = graph {x_1*x_2,x_2*x_3, x_1*x_4,x_1*x_5,x_5*x_6}; -- a tree (no     |
|-----------------------------------------------------------------------------|
|cycles)                                                                      |
+-----------------------------------------------------------------------------+
|i5 : T == spanningTree T                                                     |
|                                                                             |
|o5 = true                                                                    |
+-----------------------------------------------------------------------------+
|i6 : G = graph {x_1*x_2,x_2*x_3,x_3*x_1,x_4*x_5,x_5*x_6,x_6*x_4}; -- two     |
|-----------------------------------------------------------------------------|
|three cycles                                                                 |
+-----------------------------------------------------------------------------+
|i7 : spanningTree G                                                          |
|                                                                             |
|o7 = Graph{"edges" => {{x , x }, {x , x }, {x , x }, {x , x }}}              |
|                         1   2     1   3     4   5     4   6                 |
|           "ring" => R                                                       |
|           "vertices" => {x , x , x , x , x , x }                            |
|                           1   2   3   4   5   6                             |
|                                                                             |
|o7 : Graph                                                                   |
+-----------------------------------------------------------------------------+

Ways to use spanningTree:
=========================

  * "spanningTree(Graph)"

For the programmer
==================

The object spanningTree, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4063:0.

TimeLimit -- optional argument for randomHyperGraph
***************************************************

Description
===========

The randomHyperGraph, method follows a backtracking
algorithm to generate edges with no inclusions between them. As it may take a
long time to terminate, a time limit is imposed on the method. The TimeLimit
option is the amount of time, in seconds, that the method
randomHyperGraph, will take before terminating. A value of 0
is interpreted as one day. The default value is 5 (seconds).

See also
========

  * BranchLimit -- optional argument for randomHyperGraph
  * randomHyperGraph -- returns a random hypergraph

Functions with optional argument named TimeLimit:
=================================================

  * randomHyperGraph(...,TimeLimit=>...)
    -- limit the
    running time of randomHyperGraph

For the programmer
==================

The object TimeLimit, is a symbol (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4368:0.

vertexCoverNumber -- find the vertex covering number of a (hyper)graph
**********************************************************************

  * Usage:
        c = vertexCoverNumber(H)
  * Inputs:
      * H, a hypergraph, the input
  * Outputs:
      * c, an integer (Macaulay2Doc), the vertex covering number

Description
===========

This function returns the vertex covering number of a (hyper)graph. The vertex
covering number is the size of smallest vertex cover of the (hyper)graph.  This
corresponds to the smallest degree of a generator of the cover ideal of the
(hyper)graph.

+-----------------------------------------------------------------------------+
|i1 : S = QQ[a..d];                                                           |
+-----------------------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*a} -- the four cycle                           |
|                                                                             |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}                      |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d}                                        |
|                                                                             |
|o2 : Graph                                                                   |
+-----------------------------------------------------------------------------+
|i3 : vertexCoverNumber g                                                     |
|                                                                             |
|o3 = 2                                                                       |
+-----------------------------------------------------------------------------+
|i4 : S = QQ[a..e];                                                           |
+-----------------------------------------------------------------------------+
|i5 : g = graph {a*b,a*c,a*d,a*e,b*c,b*d,b*e,c*d,c*e,d*e} -- the complete     |
|                                                                             |
|o5 = Graph{"edges" => {{a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a    |
|           "ring" => S                                                       |
|           "vertices" => {a, b, c, d, e}                                     |
|                                                                             |
|o5 : Graph                                                                   |
|-----------------------------------------------------------------------------|
|graph K_5                                                                    |
|                                                                             |
|, e}, {b, e}, {c, e}, {d, e}}}                                               |
+-----------------------------------------------------------------------------+
|i6 : vertexCoverNumber g                                                     |
|                                                                             |
|o6 = 4                                                                       |
+-----------------------------------------------------------------------------+
|i7 : h = hyperGraph {a*b*c,a*d,c*e,b*d*e}                                    |
|                                                                             |
|o7 = HyperGraph{"edges" => {{a, b, c}, {a, d}, {c, e}, {b, d, e}}}           |
|                "ring" => S                                                  |
|                "vertices" => {a, b, c, d, e}                                |
|                                                                             |
|o7 : HyperGraph                                                              |
+-----------------------------------------------------------------------------+
|i8 : vertexCoverNumber(h)                                                    |
|                                                                             |
|o8 = 2                                                                       |
+-----------------------------------------------------------------------------+

See also
========

  * coverIdeal -- creates the cover ideal of a (hyper)graph
  * vertexCovers -- list the minimal vertex covers of a
    (hyper)graph

Ways to use vertexCoverNumber:
==============================

  * "vertexCoverNumber(HyperGraph)"

For the programmer
==================

The object vertexCoverNumber, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4102:0.

vertexCovers -- list the minimal vertex covers of a (hyper)graph
****************************************************************

  * Usage:
        c = vertexCovers(H)
  * Inputs:
      * H, a hypergraph, the input
  * Outputs:
      * c, a list (Macaulay2Doc), of the minimal vertex covers of
        H.  The vertex covers are represented as monomials.

Description
===========

This function returns the minimal vertex covers of a (hyper)graph. A vertex
cover is a subset of the vertices such that every edge of the (hyper)graph has
non-empty intersection with this set.  The minimal vertex covers are given by
the minimal generators of the cover ideal of H.

+------------------------------------------------------------------+
|i1 : S = QQ[a..d];                                                |
+------------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*a} -- the four cycle                |
|                                                                  |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}           |
|           "ring" => S                                            |
|           "vertices" => {a, b, c, d}                             |
|                                                                  |
|o2 : Graph                                                        |
+------------------------------------------------------------------+
|i3 : vertexCovers g                                               |
|                                                                  |
|o3 = {a*c, b*d}                                                   |
|                                                                  |
|o3 : List                                                         |
+------------------------------------------------------------------+
|i4 : coverIdeal g                                                 |
|                                                                  |
|o4 = monomialIdeal (a*c, b*d)                                     |
|                                                                  |
|o4 : MonomialIdeal of S                                           |
+------------------------------------------------------------------+
|i5 : flatten entries gens coverIdeal g == vertexCovers g          |
|                                                                  |
|o5 = true                                                         |
+------------------------------------------------------------------+
|i6 : S = QQ[a..e];                                                |
+------------------------------------------------------------------+
|i7 : h = hyperGraph {a*b*c,a*d,c*e,b*d*e}                         |
|                                                                  |
|o7 = HyperGraph{"edges" => {{a, b, c}, {a, d}, {c, e}, {b, d, e}}}|
|                "ring" => S                                       |
|                "vertices" => {a, b, c, d, e}                     |
|                                                                  |
|o7 : HyperGraph                                                   |
+------------------------------------------------------------------+
|i8 : vertexCovers(h)                                              |
|                                                                  |
|o8 = {a*b*c, c*d, a*e, b*d*e}                                     |
|                                                                  |
|o8 : List                                                         |
+------------------------------------------------------------------+

See also
========

  * coverIdeal -- creates the cover ideal of a (hyper)graph
  * vertexCoverNumber -- find the vertex covering
    number of a (hyper)graph

Ways to use vertexCovers:
=========================

  * "vertexCovers(HyperGraph)"

For the programmer
==================

The object vertexCovers, is a method function (Macaulay2Doc).

-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4141:0.

vertices(HyperGraph) -- gets the vertices of a (hyper)graph
***********************************************************

  * Function: vertices (Polyhedra),
  * Usage:
        V = vertices(H)
  * Inputs:
      * H, a hypergraph, the input
  * Outputs:
      * V, a list (Macaulay2Doc), of the vertices of H

Description
===========

This function takes a graph or hypergraph and returns the vertex set of the
graph.

+-----------------------------------------------------------------+
|i1 : S = QQ[a..d];                                               |
+-----------------------------------------------------------------+
|i2 : g = graph {a*b,b*c,c*d,d*a} -- the four cycle               |
|                                                                 |
|o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}}          |
|           "ring" => S                                           |
|           "vertices" => {a, b, c, d}                            |
|                                                                 |
|o2 : Graph                                                       |
+-----------------------------------------------------------------+
|i3 : vertices g                                                  |
|                                                                 |
|o3 = {a, b, c, d}                                                |
|                                                                 |
|o3 : List                                                        |
+-----------------------------------------------------------------+
|i4 : h = hyperGraph{a*b*c}                                       |
|                                                                 |
|o4 = HyperGraph{"edges" => {{a, b, c}}    }                      |
|                "ring" => S                                      |
|                "vertices" => {a, b, c, d}                       |
|                                                                 |
|o4 : HyperGraph                                                  |
+-----------------------------------------------------------------+
|i5 : vertices h  -- the vertex d is treated as an isolated vertex|
|                                                                 |
|o5 = {a, b, c, d}                                                |
|                                                                 |
|o5 : List                                                        |
+-----------------------------------------------------------------+

See also
========

  * edges -- gets the edges of a (hyper)graph

Ways to use this method:
========================

  * vertices(HyperGraph) -- gets the vertices
    of a (hyper)graph
-------------------------------------------------------------------------------

The source of this document is in EdgeIdeals.m2:4172:0.