Michael Albert ; Robert Brignall
-
$2\times 2$ monotone grid classes are finitely based
dmtcs:1325 -
Discrete Mathematics & Theoretical Computer Science,
February 11, 2016,
Vol. 18 no. 2, Permutation Patterns 2015
-
https://doi.org/10.46298/dmtcs.1325$2\times 2$ monotone grid classes are finitely basedArticle
Authors: Michael Albert ; Robert Brignall
NULL##NULL
Michael Albert;Robert Brignall
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.
Comment: 10 pages, 5 figures. To appear in Discrete Mathematics and Theoretical Computer Science, special issue for Permutation Patterns 2015
Volume: Vol. 18 no. 2, Permutation Patterns 2015
Section: Permutation Patterns
Published on: February 11, 2016
Imported on: February 11, 2016
Keywords: Mathematics - Combinatorics, 05A05