Pattern avoiding permutations and independent sets in graphs

2015/12/26 by Christian Bean, Bean, Christian, Murray Tannock +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1512.08155

21 pages, 14 figures, 3 tables

arxiv created 2019/12/12 · arxiv updated 2019/12/13

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)-, (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.

Related

• Resolving Two Conjectures on Staircase Encodings and Boundary Grids of 132 and 123-avoiding permutations
• Generalised Pattern Avoidance
• Tree decompositions with bounded independence number: beyond independent sets
• Factoring Pattern-Free Permutations into Separable ones
• Pattern Avoiding Permutations Enumerated by Inversions