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

# 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 <chris@math.okstate.edu>
- Andrew Hoefel <handrew@mathstat.dal.ca>
- Adam Van Tuyl <avantuyl@lakeheadu.ca>

## Certification

Version 1.0.0 of this package was accepted for publication in volume 1 of The Journal of Software for Algebra and Geometry: Macaulay2 on 2009-06-27, in the article EdgeIdeals: a package for (hyper)graphs (DOI: 10.2140/jsag.2009.1.1). That version can be obtained from the journal.

## Version

This documentation describes version 1.0.2 of EdgeIdeals, released March 30, 2011.

## 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/stable/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, defined in EdgeIdeals.m2.

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