Pattern avoiding permutations and independent sets in graphs
Journal of Combinatorics, Volume 4 (2020), Number 4
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.
Updates
- Shyam Narayanan proved two conjectures from the paper in Resolving Two Conjectures on Staircase Encodings and Boundary Grids of 132 and 123-avoiding permutations, Electronic Journal of Combinatorics, Volume 26, issue 3 (2019)
- There is a follow-up paper here