Skip to Main content Skip to Navigation
Conference papers

Polytopes from Subgraph Statistics

Abstract : We study polytopes that are convex hulls of vectors of subgraph densities. Many graph theoretical questions can be expressed in terms of these polytopes, and statisticians use them to understand exponential random graph models. Relations among their Ehrhart polynomials are described, their duals are applied to certify that polynomials are non-negative, and we find some of their faces. For the general picture we inscribe cyclic polytopes in them and calculate volumes. From the volume calculations we conjecture that a variation of the Selberg integral indexed by Schur polynomials has a combinatorial formula. We inscribe polynomially parametrized sets, called curvy zonotopes, in the polytopes and show that they approximate the polytopes arbitrarily close.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215115
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, October 13, 2015 - 3:07:07 PM
Last modification on : Wednesday, August 7, 2019 - 12:19:22 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:04:27 AM

File

dmAO0128.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01215115, version 1

Collections

Citation

Alexander Engström, Patrik Norén. Polytopes from Subgraph Statistics. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.305-316. ⟨hal-01215115⟩

Share

Metrics

Record views

211

Files downloads

791