# 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).

## 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. That version can be obtained from the journal or from the Macaulay2 source code repository.

## Version

This documentation describes version 1.0.2 of EdgeIdeals.

## Source code

The source code from which this documentation is derived is in the file EdgeIdeals.m2.

## Exports

• Types
• Functions and commands
• Methods
• "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 .