Polytopes from subgraph statistics

zbMATH Open1355.52007arXiv1011.3552MaRDI QIDQ2959963FDOQ2959963

Authors: Alexander Engström, Patrik Noren 

Publication date: 10 February 2017

Abstract: Polytopes from subgraph statistics are important in applications and conjectures and theorems in extremal graph theory can be stated as properties of them. We have studied them with a view towards applications by inscribing large explicit polytopes and semi-algebraic sets when the facet descriptions are intractable. The semi-algebraic sets called curvy zonotopes are introduced and studied using graph limits. From both volume calculations and algebraic descriptions we find several interesting conjectures.

Full work available at URL: https://arxiv.org/abs/1011.3552

Recommendations

• The polytope of \(k\)-star densities
• scientific article; zbMATH DE number 3929064
• Subgraph polytopes and independence polytopes of count matroids
• Hypergraph polytopes
• Convex polytopes and enumeration

zbMATH Keywords

polytopesgraph limitsexponential random graph modelssubgraph statisticscurvy zonotopes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Cited In (4)

• Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
• Invariants of multidimensional time series based on their iterated-integral signature
• Ground states for exponential random graphs
• The polytope of \(k\)-star densities

This page was built for publication: Polytopes from subgraph statistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959963)