next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
EdgeIdeals :: EdgeIdeals

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

Certification a gold star

Version 1.0.0 of this package was accepted for publication in volume 1 of the journal 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, svn://svn.macaulay2.com/Macaulay2/trunk/M2/Macaulay2/packages/EdgeIdeals.m2, release number 9342.

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
    • 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
    • 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
    • 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
    • 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
    • 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 == 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
    • ring(HyperGraph) -- gives the ring of a (hyper)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
    • 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