Pattern Avoidance in Extensions of Comb-Like

This paper investigates pattern avoidance in linear extensions of particular partially ordered sets (posets). Since the problem of enu-merating pattern avoiding linear extensions of posets without any ad-ditional restrictions is a very hard one, we focus on the class of posets called combs. Combs consist of a fully ordered spine and several fully ordered teeth, where an element of each tooth coincides with a cor-responding element of the spine, as described in Section 2. We con-sider two natural assignments of integers to elements of the combs; we refer to the resulting integer posets as type-α and type-β combs, as described in Section 3. In this paper, we enumerate the linear exten-sions of type-α and type-β combs that avoid some of the length-three patterns w ∈ S3. Most notably, the number of linear extensions of type-β combs that avoid 312 is shown to be the same as the number 1 st+1 s(t+1