The convex support of the k-star model

Johannes Rauh

Contact the author: Please use for correspondence this email.
Submission date: 11. Sep. 2012
Pages: 19
Bibtex
MSC-Numbers: 52B11, 05C80, 05C35, 05C07
Keywords and phrases: polytope, $k$-star model, exponential random graph model, vertex degrees, convex support
Download full preprint: PDF (248 kB)

Abstract:
This paper describes the polytope P_k;N of i-star counts, for all i ≤ 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, 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.