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 1,2; Francisco Santos 3
0000-0002-2070-9223##0000-0003-2120-9068
Vincent Pilaud;Francisco Santos
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
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.
Hohlweg, Christophe, 2012, Permutahedra And Associahedra, Associahedra, Tamari Lattices And Related Structures, pp. 129-159, 10.1007/978-3-0348-0405-9_8.
Lange, Carsten E. M. C., 2013, Minkowski Decomposition Of Associahedra And Related Combinatorics, Discrete & Computational Geometry, 50, 4, pp. 903-939, 10.1007/s00454-013-9546-5.