Pattern avoiding permutations and independent sets in graphs
Journal of Combinatorics, Volume 11 (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.
Download the paper
Presentations
- British Combinatorial Conference 2015, presented by Murray abstract slides
- MIT Combinatorics Seminar October 2015 abstract
- Permutation Patterns 2015, presented by Murray abstract slides
Later work (last updated 3 October 2026)
- S. S. Narayanan, Resolving two conjectures on staircase encodings and boundary grids of 132 and 123-avoiding permutations, Electron. J. Combin. 26 (2019). Proves two conjectures of this paper: it enumerates a family of staircase encodings, and shows that the downcore graph of the boundary grid is pure if and only if the permutation avoids 123 and 2143.
- C. Bean, É. Nadeau and H. Úlfarsson, Enumeration of permutation classes and weighted labelled independent sets, Discrete Math. Theor. Comput. Sci. 22 (2021). Refines the encoding of this paper with weighted independent sets, recovering its results for Av(123) and Av(132), and uses its updown core graph to enumerate Av(2314, 3124, 2413, 3142).
- All citing papers on Google Scholar (6)