Alexander Engström ; Patrik Norén - Polytopes from Subgraph Statistics

dmtcs:2912 - Discrete Mathematics & Theoretical Computer Science, January 1, 2011, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) - https://doi.org/10.46298/dmtcs.2912
Polytopes from Subgraph Statistics

Authors: Alexander Engström ; Patrik Norén

    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.


    Volume: DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
    Section: Proceedings
    Published on: January 1, 2011
    Imported on: January 31, 2017
    Keywords: 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]

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 164 times.
    This article's PDF has been downloaded 174 times.