Flexible Schemes and Beyond: Experimental Enumeration of Pattern Avoidance Classes (Thesis Defense)

Date: March 24, 2020

Speaker: Yonah Biers-Ariel

Abstract: This thesis demonstrates several applications of experimental methods to the enumeration of pattern-avoiding permutations. First, we introduce flexible schemes -- a new extension of enumeration schemes. We show how a computer can find flexible schemes and use them to count permutations. We establish sufficient conditions for the existence of finite flexible schemes, and in particular show that they exist whenever finite enumeration schemes or regular insertion encodings do. Next, we combine enumeration schemes with structural arguments to give a new algorithm for counting 1342-avoiding permutations. We find a recurrence for the number of permutations avoiding four dashed patterns, and finally generalize Claude Lenormand's "raboter" sequence. We have implemented all the algorithms described here in Maple and provide links to the Maple code in each section.