Abstract | ||
---|---|---|
This paper describes the polytope P-k;N of i-star counts, for all i <= 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 (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. |
Year | Venue | Keywords |
---|---|---|
2017 | ELECTRONIC JOURNAL OF COMBINATORICS | polytope,k-star model,exponential random graph model,vertex degrees,convex support |
DocType | Volume | Issue |
Journal | 24 | 1 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Johannes Rauh | 1 | 152 | 16.63 |