|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  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 non-regular 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, f-matchings|