Ordinal and Disjoint Sums of Partially Ordered Patterns

Source abstract

Partially ordered patterns (POPs) extend the classical notion of permutation patterns within the framework of pattern avoidance. Building on recent work of Burstein, Han, Kitaev, and Zhang, who introduced the concept of shape-Wilf equivalence for sets of patterns, we develop the notions of ordinal sums and disjoint sums of labeled posets. This perspective allows us to reinterpret their main result as an ordinal-sum analogue of the classical theorem of Backelin, West, and Xin. We establish parallel results for disjoint sums of POPs and further extend their work by proving Wilf equivalence results for classes of POPs that include isolated vertices. In particular, we prove the shape-Wilf equivalence of the pattern sets $\{123,213,312\}$ and $\{132,231,321\}$, as well as $\{123,132,231\}$ and $\{213,312,321\}$. Our approach is based on a bijection using an encoding scheme for transversals avoiding these patterns. As an application of our results, we completely classify partially ordered patterns of sizes $3$, $4$, and $5$ whose connected components are chains, thereby confirming a conjecture of Dimitrov posed at the problem session of the British Combinatorics Conference 2024 (BCC30).