Higher dimensional floorplans and Baxter d d -permutations
Nicolas Bonichon, Thomas Muller, Adrian Tanasa · 2025
Read Higher dimensional floorplans and Baxter d d -permutations by Nicolas Bonichon, Thomas Muller, Adrian Tanasa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01116.txt.
Introduction
Nicolas Bonichon, Thomas Muller, and Adrian Tanasa study floorplans, a topic where geometry meets counting. A floorplan divides a rectangle into smaller rectangles with no empty rooms. In two dimensions, such layouts are known to match a special family of orderings called Baxter permutations.
The authors extend this picture to higher dimensions, where a layout splits a box into smaller boxes. They build a generating tree, a step-by-step scheme that grows all layouts of a given size from smaller ones. The labels and rules for this tree turn out to be far more complex than in the flat case. They also give an exact match between a certain family of higher layouts and lists of permutations marked by forbidden patterns. This family is strictly smaller than the Baxter family defined earlier. The work sharpens what is known about how layouts and orderings correspond when extra dimensions are added.
Catalog record
| CREATOR | Nicolas Bonichon, Thomas Muller, Adrian Tanasa |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-01116
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher dimensional floorplans and Baxter d d -permutations Nicolas Bonichon, Thomas Muller, Adrian Tanasa Abstract A 2 − 2- dimensional mosaic floorplan is a partition of a rectangle by other rectangles with no empty rooms. These partitions (considered up to some deformations) are known to be in bijection with Baxter permutations. A d d -floorplan is the generalisation of mosaic floorplans in higher dimensions, and a d d -permutation is a ( d − 1 ) (d-1) -tuple of permutations. Recently, in N. Bonichon and P.-J. Morel, J. Integer Sequences 25 (2022), Baxter d d -permutations generalising the usual Baxter permutations were introduced. In this paper, we consider mosaic floorplans in arbitrary dimensions, and we construct a generating tree for d d -floorplans, which generalises the known generating tree structure for 2 2 -floorplans. The corresponding labels and rewriting rules appear to be significantly more involved in higher dimensions. Moreover we give a bijection between the 2 d − 1 2^{d-1} -floorplans and d d -permutations characterized by forbidden vincular patterns. Surprisingly, this set of d d -permutations is strictly contained within the set of Baxter d d -permutations. 1 Introduction A floorplan of size n is a partition of a rectangle using n interior-disjoint rectangles. These combinatorial objects have been studied in various fields of computer science, architecture or discrete geometry. The boundaries of the rectangles of a floorplan define a set of horizontal and vertical straight lines. A floorplan is generic if the union of horizontal (resp. vertical) boundary straight lines that share the same y -coordinate (resp. x -coordinate) is a single line. A segment is a maximal (horizontal or vertical) straight line in the inner boundaries. A mosaic floorplan is a generic floorplan with no segment crossing. This condition is called the tatami condition . In this paper we investigate a natural generalization of floorplans to higher dimensions. A d -dimensional floorplan (or a box partition ) is a partition of a d -dimensional hyperrectangle with n interior-disjoint d -dimensional hyperrectangles (called blocks). The boundaries of the hyperrectangles of a d -dimensional floorplan define a set of (d-1) -hyperrectangles. A d -dimensional floorplan is generic if the set of boundaries that share the same i -th coordinate is a single (d-1) -hyperrectangle. A border is a maximal (d-1) -hyperrectangle of the interior of the bounding d -hyperrectangle. A d -floorplan is a generic d -dimensional floorplan that has no border crossing (this being the tatami condition in higher dimensions). These objects have already been considered in the literature. In the case d=3 , they are called generic boxed Plattenbau in [ FKU20 ] . Figure 1: On the left an example of a 3- floorplan. In the middle the relative order of each blocks with respect to each direction ( x,y,z ). On the right the corresponding 3 -permutation (considering the 3 -floorplan as a 4 -floorplan). Two d -floorplans are equivalent if the relative positions (up, down, left, right etc…) of their boxes are the same. In the two dimensional case, these objects are known to be closely related to pattern-avoiding permutations such as Baxter permutations or separable permutations [ ABP06 , ABBM+13 ] and other combinatorial objects [ ABB+12 , YCS03 ] . The study of the generating functions and the enumeration of families of pattern-avoiding mosaic floorplans is also an active field of research, see for example [ AB24 ] . Additionally, in [ AM10 ] , a generalization to arbitrary dimensions of a restricted family of mosaic floorplans, called guillotine partitions , was considered. The authors find a bijection between 2^{d-1}- dimensional guillotine partitions and separable d -permutations, which are a higher dimensional generalisation of separable permutations. The main contribution of this paper is twofold. First, we exhibit a generation tree for d -floorplans. Given a floorplan, we can remove its top box and unequivocally fill the resulting empty space in order to obtain a smaller floorplan (using the tatami condition). This gives a natural definition for a generating tree. In the d=2 case, the children of a given floorplan is determined by the number of boxes that touch the top and left boundaries. Moreover, determining these parameters for the children is straightforward [ BBMF10 ] . However, for d\geq 3 , we need to manage more involved parameters. This allows us to enumerate efficiently the set of all d -floorplans for n\leq 10 . The second main contribution is a generalization of the bijection between mosaic floorplans and Baxter permutations. A d -permutation (or multipermutation ) is a tuple of d-1 permutations of size n . The presented generalization of the mapping from d -permutation to 2^{d-1} -floorplan is straightforward, but the characterization of the corresponding multipermutation is more involved. These multipermutations are defined by the avoidance of the vincular patterns of Baxter permutations and the dimension 3 patterns of the separable d -permutations. Surprisingly, this set is strictly included in the set of Baxter d -permutations defined in [ BM22 ] . A summary of the objects and the corresponding pattern avoiding permutations is given in Table 2 . Moreover, this bijection generalizes the bijection between guillotine 2^{d-1} -floorplans and separable d -permutations of [ AM10 ] . Objects Permutations Pattern avoidance Slicing floorplans Separable \Sym(2413) Mosaic floorplans Baxter \Sym(2413|_{{\color[rgb]{0.33,0.42,0.18}2},{\color[rgb]{0.832,0.168,0.043}2}}) 2^{d-1} -guillotine floorplans d -Separable \Sym(2413),\Sym(({\color[rgb]{0.0781,0.3164,0.8008}312},{\color[rgb]{0.832,0.168,0.043}213})) 2^{d-1} -Floorplans sub d -Baxter \Sym(2413|_{{\color[rgb]{0.33,0.42,0.18}2},{\color[rgb]{0.832,0.168,0.043}2}}) , \Sym(({\color[rgb]{0.0781,0.3164,0.8008}312},{\color[rgb]{0.832,0.168,0.043}213})) d- Baxter \Sym(2413|_{{\color[rgb]{0.33,0.42,0.18}2},{\color[rgb]{0.832,0.168,0.043}2}}) , \Sym(({\color[rgb]{0.0781,0.3164,0.8008}312},{\color[rgb]{0.832,0.168,0.043}213})|_{\color[rgb]{0.33,0.42,0.18}{{\color[rgb]{0.33,0.42,0.18}1},{\color[rgb]{0.832,0.168,0.043}2},{\color[rgb]{0.0781,0.3164,0.8008}.}}}) , \Sym(({\color[rgb]{0.0781,0.3164,0.8008}3412},{\color[rgb]{0.832,0.168,0.043}1432})|_{\color[rgb]{0.33,0.42,0.18}{{\color[rgb]{0.33,0.42,0.18}2},{\color[rgb]{0.832,0.168,0.043}2},{\color[rgb]{0.0781,0.3164,0.8008}.}}}) , \Sym(({\color[rgb]{0.0781,0.3164,0.8008}2143},{\color[rgb]{0.832,0.168,0.043}1423})|_{\color[rgb]{0.33,0.42,0.18}{{\color[rgb]{0.33,0.42,0.18}2},{\color[rgb]{0.832,0.168,0.043}2},{\color[rgb]{0.0781,0.3164,0.8008}.}}}) Table 1: Table of the different class of floorplans and their corresponding permutation classes 2 Preliminaries and definitions In this section, we give various definitions leading to the one of d -floorplans. We then introduce a notion of equivalence and some operations on these objects. The definitions of this section are natural generalisations of the 2- dimensional case (see [ ABP06 , HHC+00 , ACFF24 ] ). 2.1 Generalisation of rectangles in dimension d Let us consider a d -dimensional Euclidean space with coordinates (x_{1},\ldots,x_{d}) . A hyperrectangle is defined by the Cartesian product of d intervals of the form [x_{i,min},x_{i,max}] , where i denotes the i th coordinate. An interval [a,b] is punctual if a=b . The dimension of a hyperrectangle is the number of non-punctual intervals. The interior of a hyperrectangle R is the Cartesian product of the d intervals of R where each non-punctual interval [x_{i,min},x_{i,max}] is replaced by the open interval ]x_{i,min},x_{i,max}[ . The boundary of a hyperrectangle is the difference between the hyperrectangle and its interior. A box (resp. facet , edge ) is a hyperrectangle of dimension d (resp. d-1 , d-2 ). We say that a facet is of axis i if its i -th coordinate is punctual. We say that a point q=(x_{1},...,x_{d}) is a corner of a hyperrectangle R=\Pi_{i=1..d}[x_{i,min},x_{i,max}] if x_{i}\in\{x_{i,min},x_{i,max}\} for all i . We denote by q_{\min}(R) (resp. q_{\max}(R) ) the corner of the hyperrectangle with the minimal (resp. maximal) coordinates, we call these corners the minimal and the maximal corner of R£ . Note that R is fully determined by q_{\min}(R) and q_{\max}(R) . We denote by \bar{q} the opposite corner of q in R . By extension a corner is a point that is a corner of at least one block. The boundary of