9873

Simple Graphs and Their Binomial Edge Ideals

This Demonstration illustrates the relationship between combinatorial properties of a simple graph and its binomial edge ideal (see the Details section for definitions). In particular, it can be used to verify that a graph is closed (for a given ordering of vertices) if and only if the Groebner basis of its edge ideal consists of quadratic polynomials. By starting with a random graph that is not closed and adding suitable edges until the Groebner basis consists only of quadratic polynomials, you can find the closure of the graph, that is, the minimal closed graph containing the given graph. Alternatively, you can start with a complete graph (which is always closed) and remove edges (or vertices) to obtain non-closed graphs.
To add/delete a vertex, choose the vertex number from the third setter bar. To add/delete an edge, choose the first and second vertex of the edge from the first two setter bars.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Let be a simple graph on the vertex set We say that the graph is closed with respect to the given ordering of vertices if satisfies the condition that for any pair of edges and with and , the edge is an edge of and for any pair of edges and with and the edge is an edge of .
For a field , let be the ring of polynomials in variables. The binomial edge ideal is the ideal generated by the elements where and is an edge of Binomial edge ideals of graphs were introduced in [1] and play a role in the study of conditional independence statements and the subject of algebraic statistics [2]. In this Demonstration we illustrate theorem 1.1 of (1), which states that a simple graph is closed (for a given ordering) if and only if the reduced Gröbner basis of its binomial edge ideal with respect to the lexicographic ordering on induced by is quadratic (and generated by ).
References
[1] J. Herzog, T. Hibi, F. Hreinsdóttir, F. Kahle, and T. Rauh, "Binomial Edge Ideals and Conditional Independence Statements," arXiv:0909.4717, 2009.
[2] M. Drton, B. Sturmfels, and S. Sullivant, Lectures on Algebraic Statistics, Vol. 39, Berlin: Springer, 2009.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+