Polytopes from Subgraph Statistics

International audience 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 des...

Full description

Bibliographic Details
Published in:Discrete Mathematics & Theoretical Computer Science
Main Authors: Engström, Alexander, Norén, Patrik
Other Authors: Department of Mathematics Berkeley, University of California Berkeley (UC Berkeley), University of California (UC)-University of California (UC), Department of Mathematics Sweden (KTH), Stockholm University, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
Format: Conference Object
Language:English
Published: HAL CCSD 2011
Subjects:
polytopes
subgraph statistics
exponential random graph models
curvy zonotopes
graph limits
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Selberg
Iceland
Online Access:https://hal.inria.fr/hal-01215115
https://hal.inria.fr/hal-01215115/document
https://hal.inria.fr/hal-01215115/file/dmAO0128.pdf
https://doi.org/10.46298/dmtcs.2912
Description
Summary:International audience 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. Nous étudions les polytopes qui sont les enveloppes convexes des vecteurs des densités de sous-graphe. Beaucop de questions théoriques de graphe peuvent être exprimées en termes de ces polytopes, et les statisticiens les utilisent pour comprendre les modèles de graphes aléatoires exponentielles Des relations parmi leurs polynômes d'Ehrhart sont décrites leurs duals sont appliqués pour certifier que les polynômes sont non négatifs, et nous trouvons certaines de leurs faces. Pour la description générale nous inscrivons les polytopes cycliques dans eux et calculons les volumes. D'après les calculs de volume, nous conjecturons qu'une variation de l'intégrale de Selberg indexés par des polynômes de Schur a une formule combinatoire. Nous inscrivons polynomialement les ensembles paramétrisés appelés ``curvy zonotopes'' dans les polytopes et montrons qu'ils sont arbitrairement proches de polytopes.

Similar Items