Contents Online

# Journal of Combinatorics

## Volume 6 (2015)

### Number 1–2

### Pattern avoidance in extensions of comb-like posets

Pages: 249 – 272

DOI: http://dx.doi.org/10.4310/JOC.2015.v6.n1.a13

#### Author

#### Abstract

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