The polytope of \(k\)-star densities
type: Item
instance of: scholarly article
title: The polytope of \(k\)-star densities
zbMATH Open document ID: 1355.05228
author: Johannes Rauh
published in: The Electronic Journal of Combinatorics
publication date: 2017-02-17T00:00:00Z
full work available at URL: v24i1p4
review text: Summary: This paper describes the polytope \(P_{k;N}\) of \(i\)-star counts, for all \(i\leqslant 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 \(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. 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.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 52B11
zbMATH DE Number: 6686257
zbMATH Keywords: polytopes
zbMATH Keywords: \(k\)-star model
zbMATH Keywords: exponential random graph model
zbMATH Keywords: vertex degrees
zbMATH Keywords: convex support
describes a project that uses: polymake
describes a project that uses: gnuplot
MaRDI profile type: Publication
cites work: Q3995193
cites work: Estimating and understanding exponential random graph models
cites work: The large deviation principle for the Erdős-Rényi random graph
cites work: Cyclic polytopes and oriented matroids
cites work: Q2947597
cites work: polymake: a framework for analyzing convex polytopes
cites work: Geometry of moment spaces
cites work: Eine Vorzeichenregel in der Theorie der algebraischen Gleichungen. Aus einem Vorlesungsmanuskript herausgegeben von Alexander Ostrowski
description: scientific article; zbMATH DE number 6686257