Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

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