2012/11/29 by Hjalti Magnússon, Magnusson, Hjalti, Henning Úlfarsson +1
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Mathematics · #05A05 #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #Biochemical and Structural Characterization #Botanical Research and Chemistry #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Software (cs.MS)
paper · pdf · doi:10.48550/arxiv.1211.7110
openalex publication_date 2012/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an algorithm, called BiSC, that describes the patterns avoided by\na given set of permutations. It automatically conjectures the statements of\nknown theorems such as the descriptions of stack-sortable (Knuth 1975) and\nWest-2-stack-sortable permutations (West 1990), smooth (Lakshmibai and Sandhya\n1990) and forest-like permutations (Bousquet-Melou and Butler 2007), and simsun\npermutations (Branden and Claesson 2011). The algorithm has also been used to\ndiscover new theorems and conjectures related to Young tableaux,\nWilf-equivalences and sorting devices. We further give algorithms to prove a\ncomplete description of preimages of pattern classes under certain sorting\ndevices. These generalize an algorithm of Claesson and Ulfarsson (2012) and\nallow us to prove a linear time algorithm for finding occurrences of the\npattern 4312.\n