MiS Preprint Repository

This paper describes the polytope ${\mathbf{P}}_{k;N}$ of $i$-star counts, for all $i\le k$, for graphs on $N$ vertices. The vertices correspond to graphs that are regular or as regular as possible. For even $N$ the polytope is a cyclic polytope, and for odd $N$ the polytope is well-approximated by a cyclic polytope. As $N$ goes to infinity, ${\mathbf{P}}_{k;N}$ approaches the convex hull of the moment curve. The affine symmetry group of ${\mathbf{P}}_{k;N}$ contains just a single non-trivial element, which corresponds to forming the complement of a graph.

The results generalize to the polytope ${\mathbf{P}}_{I;N}$ of $i$-star counts, for $i$ in some set $I$ of non-consecutive integers. In this case, ${\mathbf{P}}_{I;N}$ can still be approximated by a cyclic polytope, but it is usually not a cyclic polytope itself.