Journal of Combinatorics

Volume 6 (2015)

Pattern avoidance in extensions of comb-like posets

Pages: 249 – 272

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

Author

Sophia Yakoubov (Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

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

Published 20 March 2015