Pattern avoidance in extensions of comb-like posets

Abstract: This paper investigates pattern avoidance in linear extensions of a certain class of partially ordered set. Since the question of enumerating pattern avoiding linear extensions of posets in general is a very hard one, we focus instead on certain partially ordered sets called combs. Combs consist of a fully ordered spine, and several fully ordered teeth, where each tooth coincides with a corresponding element of the spine. We consider two natural assignments of integers to elements of the combs; we refer to the resulting integer posets as type-alpha combs and type-beta combs. In this paper, we enumerate the linear extensions of type-alpha and type-beta combs which avoid some of the length-three pattern. Most notably, the number of linear extensions of type-beta combs which avoid 312 is shown to be the same as the number 1/(st + 1)*(s(t+1) choose s) of (t+1)-ary trees on s nodes, where t is the length of each tooth, and s is the length of the comb spine, or equivalently, the number of its teeth. We also investigate the enumeration of linear extensions of type-alpha and type-beta combs avoiding multiple length-three patterns.

Review text

A linear extension of a partially ordered set (poset) is a permutation of the poset's elements that respects the poset's relations. A permutation \(v\) is said to be \(w\)-avoiding if no subsequence of \(v\) has the same relative order as \(w\). Special posets, called combs are considered. A comb consists of a spine (a fully ordered set) and several teeth (fully ordered sets too), where the first element of each tooth coincides with a corresponding element of the spine. Enumerations of linear extensions for two special type of integer posets (namely type-\(\alpha\) and type-\(\beta\)) that avoid some length-3 patterns are considered. If \(A_w(P)\) denotes the number of linear extensions of the poset \(P\) avoiding \(w\), and \(K_{s,t}^\alpha\) (resp. \(K_{s,t}^\beta\)) denotes the number of combs with spine of length \(s\) and teeth of length \(t\) of type-\(\alpha\) (resp. type-\(\beta\)), then the main results of the paper can be written as: \(\displaystyle A_{312}\big(K_{s,t}^\beta\big) = \frac{1}{ts+1}{ s(t+1) \choose s}\) for \(t>1\) (the number of \((t+1)\)-ary trees) and \(\displaystyle A_{213}\big(K_{s,t}^\alpha\big) = \frac{1}{s+1}{ 2s \choose s}\) for \(t > 1\) (the number of binary trees).

Recommendations

Cited in

(6)

This page was built for publication: Pattern avoidance in extensions of comb-like posets

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