Polytopes from subgraph statistics

MaRDI QIDQ2959963zbMATH OpenFDO

Authors Alexander Engström, Patrik Noren

Publication date 10 February 2017

Full work available at URL https://arxiv.org/abs/1011.3552, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAO0128

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)

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.

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

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)