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

Certification a gold star

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.

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
  • 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
    • 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 EdgeIdeals.m2:1241:0.