The brick polytope of a sorting network
From MaRDI portal
Publication:412257
DOI10.1016/J.EJC.2011.12.003zbMATH Open1239.52026arXiv1103.2731OpenAlexW2031065814MaRDI QIDQ412257FDOQ412257
Authors: Vincent Pilaud, Francisco Santos 
Publication date: 4 May 2012
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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 flip graphs on pseudoline arrangements with contacts supported by a given sorting network. In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes. Our brick polytopes include Hohlweg and Lange's many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.
Full work available at URL: https://arxiv.org/abs/1103.2731
Recommendations
Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)
Cites Work
- Title not available (Why is that?)
- Oriented Matroids
- Triangulations. Structures for algorithms and applications
- Title not available (Why is that?)
- Maximal fillings of Moon polyominoes, simplicial complexes, and Schubert polynomials
- Coxeter complexes and graph-associahedra
- Permutohedra, Associahedra, and Beyond
- Faces of generalized permutohedra
- Subword complexes in Coxeter groups.
- Brick polytopes of spherical subword complexes and generalized associahedra
- Subword complexes, cluster complexes, and generalized multi-associahedra
- Multitriangulations, pseudotriangulations and primitive sorting networks
- A new perspective on \(k\)-triangulations
- Permutahedra and generalized associahedra.
- Matroid polytopes and their volumes
- A simple way to tell a simple polytope from its graph
- The associahedron and triangulations of the \(n\)-gon
- Realizations of the associahedron and cyclohedron
- Many non-equivalent realizations of the associahedron
- Constructions and complexity of secondary polytopes
- Multitriangulations as complexes of star polygons
- Pseudo-triangulations -- a survey
- Title not available (Why is that?)
- Puzzles and polytope isomorphisms
- Realization of the Stasheff polytope
- Isometry classes of generalized associahedra
- A Turán-type theorem on chords of a convex polygon
- A generalization of diagonal flips in a convex polygon
- Topologically sweeping visibility complexes via pseudotriangulations
- On line arrangements in the hyperbolic plane
- Minkowski decompositions of associahedra
- Title not available (Why is that?)
Cited In (37)
- Minkowski decomposition of associahedra and related combinatorics
- The brick polytope of a sorting network
- Fan realizations of type \(A\) subword complexes and multi-associahedra of rank 3
- Fan realizations for some 2-associahedra
- Quotientopes
- Brick manifolds and toric varieties of brick polytopes
- Associahedra for finite‐type cluster algebras and minimal relations between g‐vectors
- Cambrian acyclic domains: counting \(c\)-singletons
- A catalanization map on the symmetric group
- Multitriangulations, pseudotriangulations and primitive sorting networks
- Compatibility fans for graphical nested complexes
- Associahedra via spines
- Bruhat intervals, subword complexes and brick polyhedra for finite Coxeter groups
- Homotopical perspective on statistical quantities
- Title not available (Why is that?)
- Subword complexes via triangulations of root polytopes
- Brick polytopes, lattice quotients, and Hopf algebras
- Hopf dreams and diagonal harmonics
- Combinatorial generation via permutation languages. II. Lattice congruences
- A Hopf algebra of subword complexes
- Brick polytopes of spherical subword complexes and generalized associahedra
- Denominator vectors and compatibility degrees in cluster algebras of finite type
- Subword complexes, cluster complexes, and generalized multi-associahedra
- Hopf Monoids and Generalized Permutahedra
- A Hopf algebra of subword complexes (Extended abstract)
- Generating near‐bipartite bricks
- Toric matrix Schubert varieties and their polytopes
- The diameter of type \(D\) associahedra and the non-leaving-face property
- Rectangulotopes
- Celebrating Loday's associahedron
- Polytopal realizations and Hopf algebra structures for lattice quotients of the weak order
- Non-kissing complexes and tau-tilting for gentle algebras
- Vertex barycenter of generalized associahedra
- Geometric realizations of the accordion complex of a dissection
- Many non-equivalent realizations of the associahedron
- Lifted generalized permutahedra and composition polynomials
- \(\mathsf{K}\)-orbit closures and Barbasch-Evens-Magyar varieties
This page was built for publication: The brick polytope of a sorting network
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412257)
