2013/10/10 by Sophia Yakoubov, Yakoubov, Sophia
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1310.2979
Work presented at Permutation Patterns 2013. 01/29/2014: fixed minor typos. 12/19/2014: minor cosmetic edits
arxiv created 2014/12/19 · arxiv updated 2014/12/23
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.