Pattern avoiding permutations and independent sets in graphs

Christian Bean, Murray Tannock, Henning Ulfarsson

Published 2015-12-26Version 1

We encode certain pattern avoiding permutations as weighted independent sets in a family of graphs we call cores. For the classical case of 132-avoiding permutations we establish a bijection between the vertices of the cores and edges in a fully connected graph drawn on a convex polygon. We prove that independent sets in the core correspond to non-crossing subgraphs on the polygon, and then the well-known enumeration of these subgraphs transfers to an enumeration of 132-avoiding permutations according to left-to-right minima. We extend our results to the 123-, (1324, 2143)-, (1234, 1324, 2143)-, (1234, 1324, 1432, 3214)-avoiding permutations. We end by enumerating certain subsets of 1324-avoiding permutations that satisfy particular conditions on their left-to-right minima and right-to-left maxima.