The polytope of \(k\)-star densities (Q510308)

Summary: This paper describes the polytope \(P_{k;N}\) of \(i\)-star counts, for all \(i\leqslant k\), for graphs on \(N\) nodes. 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, \(P_{k;N}\) approaches the convex hull of the moment curve. The affine symmetry group of \(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 \(P_{I;N}\) of \(i\)-star counts, for \(i\) in some set \(I\) of non-consecutive integers. In this case, \(P_{I;N}\) can still be approximated by a cyclic polytope, but it is usually not a cyclic polytope itself. Polytopes of subgraph statistics characterize corresponding exponential random graph models. The elongated shape of the \(k\)-star polytope gives a qualitative explanation of some of the degeneracies found in such random graph models.