Vincent Pilaud ; Francisco Santos - The brick polytope of a sorting network

dmtcs:2952 - 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.2952
The brick polytope of a sorting network

Authors: Vincent Pilaud ORCID-iD; Francisco Santos ORCID-iD

    The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud and Pocchiola in their study of pseudoline arrangements with contacts supported by a given network. In this paper, we construct the "brick polytope'' of a network, obtained as the convex hull of the "brick vectors'' associated to each pseudoline arrangement supported by the network. We characterize its vertices, describe its faces, and decompose it as a Minkowski sum of simpler polytopes. Our brick polytopes include Hohlweg and Lange's many realizations of the associahedron, which arise as brick polytopes of certain well-chosen networks.


    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: associahedron,sorting networks,pseudoline arrangements with contacts,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Linked data

    Source : ScholeXplorer IsReferencedBy ARXIV 1009.5344
    Source : ScholeXplorer IsReferencedBy DOI 10.1007/s00454-012-9408-6
    Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1009.5344
    • 10.48550/arxiv.1009.5344
    • 10.1007/s00454-012-9408-6
    • 10.1007/s00454-012-9408-6
    • 10.1007/s00454-012-9408-6
    • 1009.5344
    Multitriangulations, Pseudotriangulations and Primitive Sorting Networks
    Pilaud, Vincent ; Pocchiola, Michel ;

    2 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 140 times.
    This article's PDF has been downloaded 121 times.