Journal of Combinatorics

Volume 11 (2020)

Number 4

Pattern avoiding permutations and independent sets in graphs

Pages: 705 – 732

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n4.a7

Authors

Christian Bean (Department of Computer Science, Reykjavik University, Reykjavik, Iceland)

Murray Tannock (Department of Computer Science, Reykjavik University, Reykjavik, Iceland)

Henning Ulfarsson (Department of Computer Science, Reykjavik University, Reykjavik, Iceland)

Abstract

We introduce a new method for encoding permutations as weighted independent sets in a family of graphs we call cores. The encoding allows us to enumerate $(1324, 2143)$-, $(1234, 1324, 2143)$-, and $(1234, 1324, 1432, 3214)$-avoiding permutations, with respect to their number of “boundary points” and the size of the independent set in the graph they correspond to.

Keywords

permutation patterns, non-crossing subgraphs, independent sets

2010 Mathematics Subject Classification

Primary 05A05. Secondary 05A15.

Full Text (PDF format)

The authors’ research was partially supported by grant 141761-051 from the Icelandic Research Fund.

Received 12 January 2016

Accepted 19 March 2020

Published 9 October 2020