Shape and Other Properties of 1324-Avoiding Permutations

Of the three Wilf classes of permutations avoiding a single pattern of length 4, the exact enumerations for two of them were found by Gessel (1990) and Bona (1997). More recently, the Stanley-Wilf conjecture was proved by Marcus and Tardos (2004) relying on work by Furedi and Hajnal (1992), and work by Klazar (2000). Work by Arratia (1999) shows that this implies the existence of an exponential growth rate for any of these classes of permutations. 1324-avoiding permutations belong to the final Wilf class of permutations avoiding a single pattern of length 4. Unlike the other two, not only is the exact enumeration yet to be found, the growth rate is also unknown. We explore the known bounds to the growth rate of this class as well as discuss possible approaches to improving them. There has also been recent work done by Dokos and Pak (2014) and Miner and Pak (2014) regarding the shape of other classes of permutations. In the second part of this thesis, we explore the shape of 1324-avoiding permutations, and show that there are two regions that decay to 0 exponentially, which has a size that depends on the growth rate of the class.

Author dc:creator

• Poh, Wei Quan Julius

Advisor dc:contributor.advisor

• Robin Pemantle

Statement dc:rights

• Wei Quan Julius Poh

Language dc:language

en

Repository record dc:identifier.uri

https://repository.upenn.edu/handle/20.500.14332/28815

OAI identifier oai:identifier

oai:repository.upenn.edu:20.500.14332/28815