Separating hyperplanes of edge polytopes

摘要

Let G be a finite connected simple graph with d vertices and let PGRd be the edge polytope of G. We call PG decomposable if PG decomposes into integral polytopes PG+ and PG- via a hyperplane. In this paper, we explore various aspects of decomposition of PG: we give an algorithm deciding the decomposability of PG, we prove that PG is normal if and only if both PG+ and PG- are normal, and we also study how a condition on the toric ideal of PG (namely, the ideal being generated by quadratic binomials) behaves under decomposition.