Details:
| Title | | | 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 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 | | | ISSN | 0209-9683 |
| Language | English | | Journal | Combinatorica | | Volume | 15 | | Number | 3 | | Pages | 409-424 | | Year | 1995 | | Edition | 0 | | Translation |
No | | Refereed |
No |
|
