Resolving Two Conjectures on Staircase Encodings and Boundary Grids of 132 and 123-avoiding permutations

2018/02/18 by Shyam Narayanan, Narayanan, Shyam
Mathematics · #05A05 #05A15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05 #msc:05A15

paper · pdf · doi:10.48550/arxiv.1802.06345

14 pages, 7 figures

arxiv created 2019/08/24 · arxiv updated 2019/08/27

Abstract

This paper analyzes relations between pattern avoidance of certain permutations and graphs on staircase grids and boundary grids, and proves two conjectures posed by Bean, Tannock, and Ulfarsson (2015). More specifically, this paper enumerates a certain family of staircase encodings and proves that the downcore graph, a certain graph established on the boundary grid, is pure if and only if the permutation corresponding to the boundary grid avoids the classical patterns 123 and 2143.

Related

• Pattern avoiding permutations and independent sets in graphs
• Pattern-avoiding modified ascent sequences
• Pattern avoidance in matchings and partitions
• Generalised Pattern Avoidance
• Sub-families of Baxter Permutations Based on Pattern Avoidance