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...
Main Authors: | , |
---|---|
Other Authors: | , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2011
|
Subjects: | |
Online Access: | https://hal.inria.fr/hal-01215115 https://hal.inria.fr/hal-01215115/document https://hal.inria.fr/hal-01215115/file/dmAO0128.pdf |
id |
ftccsdartic:oai:HAL:hal-01215115v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01215115v1 2023-05-15T16:51:32+02:00 Polytopes from Subgraph Statistics Engström, Alexander Norén, Patrik 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 Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215115 https://hal.inria.fr/hal-01215115/document https://hal.inria.fr/hal-01215115/file/dmAO0128.pdf en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS hal-01215115 https://hal.inria.fr/hal-01215115 https://hal.inria.fr/hal-01215115/document https://hal.inria.fr/hal-01215115/file/dmAO0128.pdf info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science Discrete Mathematics and Theoretical Computer Science (DMTCS) 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215115 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.305-316 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] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic 2020-12-25T18:15:03Z 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. Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) Selberg ENVELOPE(-7.374,-7.374,62.056,62.056) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
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] |
spellingShingle |
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] Engström, Alexander Norén, Patrik Polytopes from Subgraph Statistics |
topic_facet |
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] |
description |
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. |
author2 |
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 |
author |
Engström, Alexander Norén, Patrik |
author_facet |
Engström, Alexander Norén, Patrik |
author_sort |
Engström, Alexander |
title |
Polytopes from Subgraph Statistics |
title_short |
Polytopes from Subgraph Statistics |
title_full |
Polytopes from Subgraph Statistics |
title_fullStr |
Polytopes from Subgraph Statistics |
title_full_unstemmed |
Polytopes from Subgraph Statistics |
title_sort |
polytopes from subgraph statistics |
publisher |
HAL CCSD |
publishDate |
2011 |
url |
https://hal.inria.fr/hal-01215115 https://hal.inria.fr/hal-01215115/document https://hal.inria.fr/hal-01215115/file/dmAO0128.pdf |
op_coverage |
Reykjavik, Iceland |
long_lat |
ENVELOPE(-7.374,-7.374,62.056,62.056) |
geographic |
Selberg |
geographic_facet |
Selberg |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science Discrete Mathematics and Theoretical Computer Science (DMTCS) 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215115 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.305-316 |
op_relation |
hal-01215115 https://hal.inria.fr/hal-01215115 https://hal.inria.fr/hal-01215115/document https://hal.inria.fr/hal-01215115/file/dmAO0128.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1766041653854863360 |