The number of edges of the edge polytope of a finite simple graph

Takayuki Hibi, Aki Mori, Hidefumi Ohsugi, Akihiro Shikama

Published 2013-08-16, updated 2014-09-05Version 2

Let $[d] = \{ 1, \ldots, d \}$ be the vertex set and $\Omega_{d}$ the set of finite simple graphs on $[d]$, where $d \geq 3$. We write $\varepsilon(G)$ for the number of edges of the edge polytope $\mathcal{P}_G \subset {\mathbb R}^{d}$ of $G \in \Omega_{d}$. For example, $\varepsilon(K_{d}) = d(d-1)(d-2)/2$, where $K_{d}$ is the complete graph on $[d]$. In this paper, we study the number $\mu_{d} = \max \{ \varepsilon(G) \, : \, G \in \Omega_{d} \}$. We show that $\mu_{d} = \varepsilon(K_{d})$ for each $3 \leq d \leq 14$ and $\mu_{d} > \varepsilon(K_{d})$ for each $d \geq 15$. Moreover, we study the asymptotic behavior of $\mu_d$. Tuan--Ziegler gave a lower bound for $\mu_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.