Hypergraphic zonotopes and acyclohedra

Abstract

We introduce a higher-uniformity analogue of graphic zonotopes and permutohedra. Specifically, given a $(d+1)$-uniform hypergraph $H$, we define its hypergraphic zonotope ${\mathcal{Z}}_H$, and when $H$ is the complete $(d+1)$-uniform hypergraph $K_n^{(d+1)}$, we call its hypergraphic zonotope the acyclohedron ${\mathcal{A}}_{n,d}$. We express the volume of ${\mathcal{Z}}_H$ as a homologically weighted count of the spanning $d$-dimensional hypertrees of $H$, which is closely related to Kalai's generalization of Cayley's theorem in the case when $H=K_n^{(d+1)}$ (but which, curiously, is not the same). We also relate the vertices of hypergraphic zonotopes to a notion of acyclic orientations previously studied by Linial and Morganstern for complete hypergraphs.

7 pages