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

zbMATH Open1420.05008arXiv1802.06345MaRDI QIDQ2325762FDOQ2325762

Authors: Shyam Narayanan 

Publication date: 30 September 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1802.06345

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

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

zbMATH Keywords

graphs on boundary gridsgraphs on staircase grids

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating trees and forbidden subsequences
• Equivalence classes of mesh patterns with a dominating pattern

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)