Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
58/2012

The convex support of the $k$-star model

Johannes Rauh

Abstract

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.

Received:
Sep 11, 2012
Published:
Sep 12, 2012
MSC Codes:
52B11, 05C80, 05C35, 05C07
Keywords:
polytope, $k$-star model, exponential random graph model, vertex degrees, convex support

Related publications

Preprint
2012 Repository Open Access
Johannes Rauh

The convex support of the k-star model