EdgeIdeals: a Macaulay 2 package for (hyper)graphs

Adam Van Tuyl

Department of Mathematics and Statistics
McMaster University
Hamilton, ON, Canada
L8S 4L8
vantuyl@math.mcmaster.ca

EdgeIdeals: a Macaulay 2 package for (hyper)graphs

Chris Francisco (Oklahoma State), Andrew Hoefel (Google), and myself have written a Macaulay 2 package for working with graphs and hypergraphs. The note

EdgeIdeals: a package for (hyper)graphs
The Journal of Software for Algebra and Geomtery 1 (2009) 1-4.

gives an quick overview of the package. This package was started in Snowbird, Utah, as part of the Macaulay 2 Workshop. We would like to thank the organizers for inviting us to this conference.

Bug Reports and Wish Lists

Please let us know if you find any bugs. As well, we are also looking for suggestions. Let us know what you would like to see in future versions. Are there functions you would like to see? Are there invariants we missed? You can contact the authors at:

Chris Francisco (Oklahoma State) chris AT math.okstate.edu
Andrew Hoefel (Google)
Adam Van Tuyl (McMaster) vantuyl AT math.mcmaster.ca

Instructions for Use

Please feel free to use our package. Here are some instructions on how to use this package:

Starting with version 1.2 of Macaulay 2, the EdgeIdeals package is already included in the Macaulay 2 distribution. Go to the next step. If you have an older version, you may have to go through the following steps:
1. Download a copy of the package here:
  - EdgeIdeals.m2 -- the EdgeIdeal source code.
  You will have to cut-and-paste the code into a new file called:
  EdgeIdeals.m2
  Alternatively, right-click the above link and select the Save Link as... option.
2. Save the file into your working directory.

Open Macaulay 2. If you just downloaded the file, you need to run Macaulay 2 in the same directory in which you saved the file. Enter the following command:

Macaulay 2, version 1.1
with packages: Classic, Core, Elimination, IntegralClosure, LLLBases, Parsing,
               PrimaryDecomposition, SchurRings, TangentCone

i1 : installPackage "EdgeIdeals"

This will install the package, and move EdgeIdeals.m2 to a directory where Macaulay 2 will always be able to find it. As well, this command will install the documentation.

Whenever you want to use the EdgeIdeals package in the future, simple type:

Macaulay 2, version 1.1
with packages: Classic, Core, Elimination, IntegralClosure, LLLBases, Parsing,
               PrimaryDecomposition, SchurRings, TangentCone

i1 : loadPackage "EdgeIdeals"

You do not need to be in the directory where you saved EdgeIdeals.m2

Documentation

Documenation for the EdgeIdeals package is available by using the viewHelp command, or by checking out the web page:

EdgeIdeals Documentation

on the Macaulay 2 web page.

Example

You are now ready to go! As an example, we input the complete graph of size four and find its chromatic number and clique number.

i2 : S = QQ[x_1..x_4]

o2 = S

o2 : PolynomialRing

i3 : g = completeGraph(S)

o3 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }, {x , x }, {x , x }}}
                       1   2     1   3     1   4     2   3     2   4     3   4
           ring => S
           vertices => {x , x , x , x }
                         1   2   3   4

o3 : Graph

i4 : cliqueNumber(g)

o4 = 4

i5 : chromaticNumber(g)

o5 = 4