Generic Rectangulations: Enumerative and Structural Aspects.
Grant P32731, funded by


A rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles ("blocks"). Their study in combinatorics and in computational geometry is motivated by their connections to many other combinatorial structures (trees, maps, lattice paths, etc.), and by their link with integrated circuit layout. The combinatorial analysis of rectangulations is challenging, and many naturally arising questions have been answered only for very special cases. Mosaic rectangulations and generic rectangulations are equivalence classes of rectangulations under certain equivalence relations. Mosaic rectangulations are considered identical if they can be obtained from each other by continuous shifting of walls. Generic rectangulations are considered identical if, in addition, their blocks have the same contact relations. "Guillotine rectangulations" are an important class of rectangulations with a nice recursive structure. It is known that
(1) Guillotine mosaic rectangulations are in bijection with separable permutations, and are counted by Schröder numbers (easy);
(2) Mosaic rectangulations are in bijection with Baxter permutations, and are counted by Baxter numbers (Ackerman et al., 2006, and other authors);
(3) Generic rectangulations are in bijection with 2-clumped permutations (Reading, 2012).

The main problems that we plan to tackle in this project are exact and asymptotic enumeration of generic rectangulations and investigating the case of guillotine generic rectangulations. Specifically, we want to address the following problems:
(1) Representation of guillotine generic rectangulations by a permutation class and by lattice paths;
(2) Enumeration of guillotine generic rectangulations;
(3) Enumeration of all generic rectangulations;
(4) Other Baxter-related classes of permutations with interpretations in terms of rectangulations;
(5) Reconfiguration of rectangulations by flips.

The suggested methodology includes structural analysis and modern methods in analytic and enumerative combinatorics. In particular, the project should benefit from the powerful tools of analytic combinatorics for tackling problems motivated by computational geometry. So far, such methods have been employed in this area rarely, and we believe that their application in this field will lead to major progress. In addition, we expect that the use of computer algebra and symbolic computation algorithms will play an important role for obtaining experimental data and checking hypotheses, and in some cases directly lead to new results.


Publications:

A. Asinowski and C. Banderier.
From geometry to generating functions: Rectangulations and permutations.
arXiv:2401.05558.

A. Asinowski, J. Cardinal, S. Felsner, and É. Fusy.
Combinatorics of rectangulations: Old and new bijections.
arXiv:2402.01483.