Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. The brick polytope o ...
Conference paper

The brick polytope of a sorting network

Vincent Pilaud ORCID (1) (2), Francisco Santos ORCID (3)
(1) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
(2) Université Paris Diderot - Paris 7
(3) Departamento de Matemáticas, Estadística y Computación
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2010
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
Proceedings
DOI
10.46298/dmtcs.2952
License
https://about.hal.science/hal-authorisation-v1
Indicators
653
Views
568
Downloads

The brick polytope of a sorting network

Vincent Pilaud ORCID (1) (2), Francisco Santos ORCID (3)
(1) Laboratoire d'informatique de l'École polytechnique [Palaiseau]
(2) Université Paris Diderot - Paris 7
(3) Departamento de Matemáticas, Estadística y Computación
Abstract
English
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.
French
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.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • associahedron
  • sorting networks
  • pseudoline arrangements with contacts
Cited by

Source: OpenCitations

  • Minkowski Decomposition of Associahedra and Related Combinatorics

    arXiv (Cornell University)

    Authors : Carsten E. M. C. Lange

    Journal reference : Volume 50, 2013, pp. 903-939

    DOI : 10.1007/s00454-013-9546-5
  • Permutahedra and Associahedra

    Associahedra, Tamari Lattices and Related Structures

    Authors : Christophe Hohlweg ORCID

    Journal reference : Volume , 2012, pp. 129-159

    DOI : 10.1007/978-3-0348-0405-9_8
Preview
Loading PDF preview...