Simple polytopes arising from finite graphs

zbMATH Open1169.13018arXiv0804.4287MaRDI QIDQ3601426FDOQ3601426

Authors: Hidefumi Ohsugi, Takayuki Hibi 

Publication date: 10 February 2009

Abstract: Let $G$ be a finite graph allowing loops, having no multiple edge and no isolated vertex. We associate $G$ with the edge polytope ${calP}_G$ and the toric ideal $I_G$. By classifying graphs whose edge polytope is simple, it is proved that the toric ideals $I_G$ of $G$ possesses a quadratic Gr"obner basis if the edge polytope ${calP}_G$ of $G$ is simple. It is also shown that, for a finite graph $G$, the edge polytope is simple but not a simplex if and only if it is smooth but not a simplex. Moreover, the Ehrhart polynomial and the normalized volume of simple edge polytopes are computed.

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

Recommendations

• Many toric ideals generated by quadratic binomials possess no quadratic Gröbner bases
• Binomial edge ideals with quadratic Gröbner bases
• Gröbner bases for some toric rings
• Toric ideals associated with gap-free graphs
• Toric ideals generalized by quadratic binomials

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cited In (19)

• Two way subtable sum problems and quadratic Gröbner bases
• Normalized volumes of configurations related with root systems and complete bipartite graphs.
• Extremal edge polytopes
• Many toric ideals generated by quadratic binomials possess no quadratic Gröbner bases
• Quadratic Gröbner bases for smooth \(3\times 3\) transportation polytopes
• Quadratic initial ideals of root systems
• Gröbner bases of nested configurations
• A geometric definition of combinatorial pure subrings and Gröbner bases of toric ideals of positive roots
• Lexicographic and reverse lexicographic quadratic Gröbner bases of cut ideals
• Gröbner basis approach to some combinatorial problems
• Toric ideals associated with gap-free graphs
• Quasi-binomial coefficients stemming from Nakayama algebras
• On the strongly robust property of toric ideals
• Toric ideals for high Veronese subrings of toric algebras
• Linear orders of variables for complete graphs
• Quadratic Gröbner bases of twinned order polytopes
• A Gröbner basis characterization for chordal comparability graphs
• Markov basis and Gröbner basis of Segre-Veronese configuration for testing independence in group-wise selections
• Binomial edge ideals with quadratic Gröbner bases

This page was built for publication: Simple polytopes arising from finite graphs

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