The polytope of \(k\)-star densities

Johannes Rauh¹

¹MPI für Mathematik in den Naturwissenschaften

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

This paper describes the polytope $\mathbf{P}_{k;N}$ of $i$-star counts, for all $i\le 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, $\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.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.

Détail

DOI : 10.37236/4471

Classification : 05C80, 52B11
Mots-clés : polytopes, \(k\)-star model, exponential random graph model, vertex degrees, convex support