Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleGröbner Bases And Triangulations Of The Second Hypersimplex
Author(s) Jesus A. de Loera, Bernd Sturmfels, Rekha R. Thomas
TypeArticle in Journal
AbstractThe 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.
KeywordsTriangulations, Gröbner bases, second hypersimplex, secondary polytope, state polytope, toric ideals, f-matchings
ISSN0209-9683
LanguageEnglish
JournalCombinatorica
Volume15
Number3
Pages409-424
Year1995
Edition0
Translation No
Refereed No
Webmaster