Pattern avoidance in extensions of comb-like posets

This paper investigates pattern avoidance in linear extensions of particular partially ordered sets (posets). Since the problem of enumerating pattern-avoiding linear extensions of posets without any additional restrictions is a very hard one, we focus on the class of posets called combs. A comb consists of a fully ordered spine and several fully ordered teeth, where the first element of 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$ and type-$\beta$ combs. In this paper, we enumerate the linear extensions of type-$\alpha$ and type-$\beta$ combs that avoid some of the length-3 patterns $w \in S_3$. Most notably, we shown the number of linear extensions of type-$\beta$ combs that avoid $312$ to be the same as the number $\frac{1}{st+1} (\begin{smallmatrix} s(t+1) \\ s \end{smallmatrix})$ 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 that avoid multiple length-$3$ patterns simultaneously.

Keywords

partially ordered sets, pattern avoidance, combs

Full Text (PDF format)

Published 20 March 2015