$2\times 2$ monotone grid classes are finitely based

Abstract

In this note, we prove that all $2\times 2$ monotone grid classes are finitely based, i.e., defined by a finite collection of minimal forbidden permutations. This follows from a slightly more general result about certain $2\times 2$ (generalized) grid classes having two monotone cells in the same row.

10 pages, 5 figures. To appear in Discrete Mathematics and Theoretical Computer Science, special issue for Permutation Patterns 2015

References in corpus (2)

• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Profile classes and partial well-order for permutations