Wolfram Demonstrations Project

12,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Simple Graphs and Their Binomial Edge Ideals

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.

[more]

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.

[less]

Contributed by: Andrzej Kozlowski (December 2011)
Open content licensed under CC BY-NC-SA

Snapshots

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.

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send