Polytopes from Subgraph Statistics

• Main Authors: Engström, Alexander, Norén, Patrik
• Other Authors: Department of Mathematics Berkeley, University of California Berkeley, University of California-University of California, 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

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.