Details:
Title  Gröbner Bases And Triangulations Of The Second Hypersimplex  Author(s)  Jesus A. de Loera, Bernd Sturmfels, Rekha R. Thomas  Type  Article in Journal  Abstract  The algebraic technique of Groebner bases is applied to study triangulations of the second hypersimplex Delta(2,n). We present a quadratic Groebner basis for the associated toric ideal I(K_n). The simplices in the resulting triangulation of Delta(2,n) have unit volume, and they are indexed by subgraphs which are linear thrackles [28] with respect to a circular embedding of K_n . For n equal or greater 6 the number of distinct initial ideals of I(K_n) exceeds the number of regular triangulations of Delta(2,n); more precisely, the secondary polytope of Delta(2,n) equals the state polytope of I(K_n) for n smaller or equal 5 but not for n greater or equal 6.
We also construct a nonregular triangulation of Delta(2,n) for n greater or equal 9. We determine an explicit universal Groebner basis of I(K_n) for n smaller or equal 8. Potential applications in combinatorial optimization and random generation of graphs are indicated.  Keywords  Triangulations, Gröbner bases, second hypersimplex, secondary polytope, state polytope, toric ideals, fmatchings  ISSN  02099683 
Language  English  Journal  Combinatorica  Volume  15  Number  3  Pages  409424  Year  1995  Edition  0  Translation 
No  Refereed 
No 
