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

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

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, after installing subversion, with the following shell command:

   svn export -r 9342 svn://macaulay2.math.uiuc.edu/Macaulay2/trunk/M2/Macaulay2/packages/EdgeIdeals.m2

The following command will display the log messages accompanying any changes to the file in the repository since publication.

   svn log -r 9343:HEAD svn://macaulay2.math.uiuc.edu/Macaulay2/trunk/M2/Macaulay2/packages/EdgeIdeals.m2

The following command will summarize the changes to the file in the repository since publication, in the format the program diff uses: lines starting with + have been added, and lines starting with - have been removed. (Changes to white space or end of line style will not be reported.)

   svn diff -x "-b --ignore-eol-style" -r 9342:HEAD svn://macaulay2.math.uiuc.edu/Macaulay2/trunk/M2/Macaulay2/packages/EdgeIdeals.m2

The differences between two releases in the repository mentioned in the log can be displayed by replacing 9342:HEAD by the pair of release numbers separated by a colon.

Version

This documentation describes version 1.0.0 of EdgeIdeals.

Source code

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

Exports