Resolving two conjectures on staircase encodings and boundary grids of 132 and 123-avoiding permutations

MaRDI QIDQ2325762zbMATH OpenFDO

Authors Shyam Narayanan

Publication date 30 September 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.06345, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i3p62

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graphs on boundary gridsgraphs on staircase grids

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

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.

Review text

Summary: This paper analyzes relations between pattern avoidance of certain permutations and graphs on staircase grids and boundary grids, and proves two conjectures posed by \textit{C. Bean}, \textit{M. Tannock} and \textit{H. Ulfarsson} [``Pattern avoiding permutations and independent sets in graphs, Preprint, \url{https://arxiv.org/abs/1512.08155}]. 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\).

Recommendations

• Pattern avoiding permutations and independent sets in graphs
• Enumerating permutations avoiding three Babson-Steingrímsson patterns
• A relation on 132-avoiding permutation patterns
• Enumeration of permutation classes and weighted labelled independent sets
• On the diagram of 132-avoiding permutations

Cites work

• Equivalence classes of mesh patterns with a dominating pattern
• Generating trees and forbidden subsequences
• scientific article; zbMATH DE number 3165539 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)

Cited in

(2)

• Pattern avoiding permutations and independent sets in graphs
• Enumeration of permutation classes and weighted labelled independent sets

This page was built for publication: Resolving two conjectures on staircase encodings and boundary grids of \(132\) and \(123\)-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325762)