Rectangulations avoiding a pattern

Abstract

Fix a strong rectangulation pattern $P$ of size $L$. We show that the growth constant of the class of strong rectangulations avoiding $P$ is strictly smaller than $\hat{I}›=27/2$, the growth constant for all strong rectangulations. More precisely, forbidding any such $P$ yields a pattern-uniform exponential drop of at least $\hat{I}›-1/\hat{I}{›}^{3L-1}$. Consequently, the proportion of $P$-avoiding rectangulations among all rectangulations tends to zero as $n\to \infty$. This is the first result on the uniform drop of exponential growth for pattern-avoiding rectangulations. The proof utilizes the standard correspondence with leftmost history quadrant walks, along with a pattern-insertion scheme that controls the radius of convergence of the associated generating functions, thereby establishing the first uniform exponential upper bound for rectangulation classes defined by geometric avoidance.

7pages, 6 figures