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