Butiran eJurnal
$2\times 2$ monotone grid classes are finitely based
HARVEST (oa)
oa1546265
Tarikh
2015-11-02
Pencipta
Albert, Michael
Subjek
Combinatorics; 05A05
Jenis
text
Pengenal (Identifier)
http://arxiv.org/abs/1511.00473 Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 2, Permutation Patterns 2015, Permutation Patterns (February 11, 2016) dmtcs:1325; doi:10.46298/dmtcs.1325
Sumber Harvest
ARXIV
Deskripsi
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