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.

Source : oai:arXiv.org:1511.00473

Volume: Vol. 18 no. 2, Permutation Patterns 2015

Section: Permutation Patterns

Published on: February 11, 2016

Submitted on: February 11, 2016

Keywords: Mathematics - Combinatorics,05A05

Version2

This page has been seen 508 times.

This article's PDF has been downloaded 224 times.