2023/05/09 by Linusson, Svante, Restadh, Petter · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2305.05275
The purpose of this paper is twofold. We investigate a simple necessary condition, called the rhombus criterion, for two vertices in a polytope not to form an edge and show that in many examples of 0/1-polytopes it is also sufficient. We explain how also when this is not the case, the criterion can give a good algorithm for determining the edges of high-dimenional polytopes. In particular we study the Chordal graph polytope, which arises in the theory of causality and is an important example of a characteristic imset polytope. We prove that, asymptotically, for almost all pairs of vertices the rhombus criterion holds. We conjecture it to hold for all pairs of vertices.