Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Automatic discovery of structural rules of permutation classes


Authors: Christian Bean, Bjarki Gudmundsson and Henning Ulfarsson
Journal: Math. Comp. 88 (2019), 1967-1990
MSC (2010): Primary 05A05, 05A15; Secondary 68R15
DOI: https://doi.org/10.1090/mcom/3386
Published electronically: December 11, 2018
MathSciNet review: 3925493
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce an algorithm that produces conjectures regarding the structure of permutation classes. These conjectures take the form of a disjoint cover of ``rules'', each of which is similar to a generalized grid class. Such a cover is usually easily verified by a human and can often be translated directly into an enumeration. The algorithm is successful in many cases where other algorithms fail and is theoretically guaranteed to succeed on any polynomial permutation class. We apply it to every non-polynomial permutation class avoiding a set of length four patterns. The structures found by the algorithm sometimes allow one to enumerate a permutation class with respect to permutation statistics, and often yield a method for sampling uniformly at random from the class. We additionally sketch a second algorithm formalizing the human verification of the conjectured covers.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05A05, 05A15, 68R15

Retrieve articles in all journals with MSC (2010): 05A05, 05A15, 68R15


Additional Information

Christian Bean
Affiliation: School of Computer Science, Reykjavik University, Menntavegi 1, Reykjavik, Iceland
Email: christianbean@ru.is

Bjarki Gudmundsson
Affiliation: Department of Mathematics, University of Iceland, Saemundargata 2, 101 Reykjavik, Iceland
Email: bjarkig12@ru.is

Henning Ulfarsson
Affiliation: School of Computer Science, Reykjavik University, Menntavegi 1, Reykjavik, Iceland
Email: henningu@ru.is

DOI: https://doi.org/10.1090/mcom/3386
Received by editor(s): July 5, 2017
Received by editor(s) in revised form: February 7, 2018, May 8, 2018, and June 4, 2018
Published electronically: December 11, 2018
Article copyright: © Copyright 2018 American Mathematical Society