The brick polytope of a sorting network

• Published in: Discrete Mathematics & Theoretical Computer Science
• Main Authors: Pilaud, Vincent, Santos, Francisco
• Other Authors: Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Université Paris Diderot - Paris 7 (UPD7), Departamento de Matemáticas, Estadística y Computación (MATESCO), Universidad de Cantabria Santander, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2011
• Subjects: 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]; Iceland
• Online Access: https://inria.hal.science/hal-01215072; https://inria.hal.science/hal-01215072/document; https://inria.hal.science/hal-01215072/file/dmAO0168.pdf; https://doi.org/10.46298/dmtcs.2952

International audience 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. L'associaèdre est un polytope dont le graphe est le graphe des flips sur les triangulations d'un polygone convexe. Les pseudotriangulations et les multitriangulations généralisent les triangulations dans deux directions différentes, qui ont été unifiées par Pilaud et Pocchiola au travers de leur étude des arrangements de pseudodroites avec contacts couvrant un support donné. Nous construisons ici le "polytope de briques'' d'un support, obtenu comme l'enveloppe convexe des "vecteurs de briques'' associés à chaque arrangement de pseudodroites couvrant ce support. Nous caractérisons les sommets de ce polytope, décrivons ses faces et le décomposons en somme de Minkowski de polytopes élémentaires. Notre construction contient toutes les réalisations de l'associaèdre d'Hohlweg et Lange, qui apparaissent comme polytopes de briques de certains supports bien choisis.