Sort-invariant non-messing-up

zbMATH Open1246.06003arXiv1009.4201MaRDI QIDQ665740FDOQ665740

Authors: Bridget Eileen Tenner 

Publication date: 6 March 2012

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

Abstract: A poset has the non-messing-up property if it has two covering sets of disjoint saturated chains so that for any labeling of the poset, sorting the labels along one set of chains and then sorting the labels along the other set yields a linear extension of the poset. The linear extension yielded by thus twice sorting a labeled non-messing-up poset may be independent of which sort was performed first. Here we characterize such sort-invariant labelings for convex subposets of a cylinder. They are completely determined by avoidance of a particular subpattern: a diamond of four elements whose smallest two labels appear at opposite points.

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

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

Recommendations

• A non-messing-up phenomenon for posets
• Partially ordered sets associated with permutations
• Balancing poset extensions
• Sorting probability for large Young diagrams
• A new matching property for posets and existence of disjoint chains

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Total orders (06A05)

This page was built for publication: Sort-invariant non-messing-up

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