The number of edges of the edge polytope of a finite simple graph - Hibi, Takayuki (Ars mathematica contemporanea, 2016)
Let ?$d \ge 3$? be an integer. It is known that the number of edges of the edge polytope of the complete graph with ?$d$? vertices is ?$d(d-1)(d-2)/2$?. In this paper, we study the maximum possible number ?$μ_{d}$? of edges of the edge polytope arising from finite simple graphs with ?$d$? vertices. We show that ?$μ_{d} = d(d-1)(d-2)/2$? if and only if ?$3 ≤ d ≤ 14$?. In addition, we study the asymptotic behavior of ?$μ_{d}$?. Tran-Ziegler gave a lower bound for ?$μ_{d}$? by constructing a random graph. We succeeded in improving this bound by constructing both a non-random graph and a random graph whose complement is bipartite.
Keywords: edge polytope; finite simple graph; končni enostavni graf; povezavni politop