A Gröbner basis characterization for chordal comparability graphs

DOI10.1016/J.EJC.2016.08.004zbMATH Open1348.05098arXiv1602.00285OpenAlexW2271574463MaRDI QIDQ326658FDOQ326658

Authors: Hidefumi Ohsugi, Takayuki Hibi 

Publication date: 12 October 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper, we study toric ideals associated with multichains of posets. It is shown that the comparability graph of a poset is chordal if and only if there exists a quadratic Gr"obner basis of the toric ideal of the poset. Strong perfect elimination orderings of strongly chordal graphs play an important role.

Full work available at URL: https://arxiv.org/abs/1602.00285

Recommendations

• Simple polytopes arising from finite graphs
• On the universal Gröbner bases of toric ideals of graphs
• Many toric ideals generated by quadratic binomials possess no quadratic Gröbner bases
• Toric ideals associated with gap-free graphs
• Linear orders of variables for complete graphs

zbMATH Keywords

strongly chordal graphsmultichains of posetstoric ideals

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Combinatorics of partially ordered sets (06A07)

Cites Work

• On the toric algebra of graphical models
• Gröbner Bases
• Title not available (Why is that?)
• Normal polytopes arising from finite graphs
• Koszul bipartite graphs
• Toric ideals generalized by quadratic binomials
• Compressed polytopes, initial ideals and complete multipartite graphs
• Title not available (Why is that?)
• Graph Classes: A Survey
• Monomial ideals whose powers have a linear resolution
• Title not available (Why is that?)
• A unique exchange property for bases
• Markov bases for decomposable graphical models
• The toric ideal of a matroid of rank 3 is generated by quadrics
• On the toric ideal of a matroid
• Rees algebras of edge ideals
• Base-sortable matroids and Koszulness of semigroup rings
• Minimal generators of toric ideals of graphs
• Cut ideals of \(K_{4}\)-minor free graphs are generated by quadrics
• Properties of cut ideals associated to ring graphs
• Markov basis and Gröbner basis of Segre-Veronese configuration for testing independence in group-wise selections
• The toric ideal of a graphic matroid is generated by quadrics

Cited In (4)

• Koszul multi-Rees algebras of principal \(L\)-Borel ideals
• On toric ideals arising from signed graphs
• On the linearity of the syzygies of Hibi rings
• Quadratic-monomial generated domains from mixed signed, directed graphs

This page was built for publication: A Gröbner basis characterization for chordal comparability graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q326658)