Skip to Main content Skip to Navigation
Conference papers

The brick polytope of a sorting network

Abstract : 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01215072
Contributor : Coordination Episciences Iam <>
Submitted on : Tuesday, October 13, 2015 - 3:06:11 PM
Last modification on : Monday, November 9, 2020 - 2:56:03 PM
Long-term archiving on: : Thursday, April 27, 2017 - 12:26:08 AM

File

dmAO0168.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01215072, version 1

Collections

Citation

Vincent Pilaud, Francisco Santos. The brick polytope of a sorting network. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.777-788. ⟨hal-01215072⟩

Share

Metrics

Record views

259

Files downloads

823