Combinatorics of rectangulations: Old and new bijections
Preprint
Abstract
A rectangulation is a decomposition of a rectangle into finitely many rectangles. Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes, lattice paths, Hopf algebras, etc. In this paper, we first revisit the structure of the respective equivalence classes: weak rectangulations that preserve rectangle-segment adjacencies, and strong rectangulations that preserve rectangle-rectangle adjacencies. We thoroughly investigate posets defined by adjacency in rectangulations of both kinds, and unify and simplify known bijections between rectangulations and permutation classes. This yields a uniform treatment of mappings between permutations and rectangulations that unifies the results from earlier contributions, and emphasizes parallelism and differences between the weak and the strong cases. Then, we consider the special case of guillotine rectangulations, and prove that they can be characterized - under all known mappings between permutations and rectangulations - by avoidance of two mesh patterns that correspond to "windmills" in rectangulations. This yields new permutation classes in bijection with weak guillotine rectangulations, and the first known permutation class in bijection with strong guillotine rectangulations. Finally, we address enumerative issues and prove asymptotic bounds for several families of strong rectangulations.Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Combinatorial Generation via Permutation Languages. III. RectangulationsDiscrete & Computational Geometry, 2022
- Many non-equivalent realizations of the associahedronCombinatorica, 2014
- On the Number of Tilings of a Square by RectanglesAnnals of Combinatorics, 2013
- Separable d-Permutations and Guillotine PartitionsAnnals of Combinatorics, 2010
- A (4n − 4)-Bit Representation of a Rectangular Drawing or FloorplanLecture Notes in Computer Science, 2009
- Lattice Congruences of the Weak OrderOrder, 2004
- Realization of the Stasheff polytopeArchiv der Mathematik, 2004
- Optimal rectangular partitionsNetworks, 2002
- Partitioning a Square into Rectangles: NP-Completeness and Approximation AlgorithmsAlgorithmica, 2002
- Partial orders of dimension 2Networks, 1972