Algorithms for discovering and proving theorems about permutation patterns
Preprint 2012
We present an algorithm, called BiSC, that describes the patterns avoided by a given set of permutations. It automatically conjectures the statements of known theorems such as the descriptions of stack-sortable (Knuth 1975) and West-2-stack-sortable permutations (West 1990), smooth (Lakshmibai and Sandhya 1990) and forest-like permutations (Bousquet-Melou and Butler 2007), and simsun permutations (Branden and Claesson 2011). The algorithm has also been used to discover new theorems and conjectures related to Young tableaux, Wilf-equivalences and sorting devices. We further give algorithms to prove a complete description of preimages of pattern classes under certain sorting devices. These generalize an algorithm of Claesson and Ulfarsson (2012) and allow us to prove a linear time algorithm for finding occurrences of the pattern 4312.
@misc{magnusson2012algdisc,
author = {Magnusson, Hjalti and Ulfarsson, Henning},
title = {Algorithms for discovering and proving theorems about permutation patterns},
year = {2012},
eprint = {1211.7110},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://arxiv.org/abs/1211.7110},
}
Download the paper
This paper is a part of the following projects: