10182

# 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.

### 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.

### PERMANENT CITATION

 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 » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.