Ordinal and disjoint sums of partially ordered patterns

Sucharita Biswas, Umesh Shankar, Sivaramakrishnan Sivasubramanian · 2025

Read Ordinal and disjoint sums of partially ordered patterns by Sucharita Biswas, Umesh Shankar, Sivaramakrishnan Sivasubramanian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18761.txt.

Introduction

Sucharita Biswas, Umesh Shankar, and Sivaramakrishnan Sivasubramanian work in pattern avoidance. It asks which patterns a permutation can avoid. Partially ordered patterns extend the classic idea. The pattern itself carries an order structure. Recent work defined a refined equivalence for pattern sets. It is called shape-Wilf-equivalence. This paper builds tools to compare such sets. The tools are ordinal sums and disjoint sums of labeled posets.

With those tools, a recent theorem gets a new reading. It becomes a counterpart of a classical result. Matching theorems for disjoint sums are proved. The theory extends to classes with isolated vertices. One prize is a proof about two triples of patterns. The triples have length three, and they are shown equivalent. A bijection built on an encoding does the work. The paper fully classifies small patterns whose parts are chains. A conjecture from a 2024 conference is confirmed.

Catalog record

CREATORSucharita Biswas, Umesh Shankar, Sivaramakrishnan Sivasubramanian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18761

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ordinal and disjoint sums of partially ordered patterns Sucharita Biswas, Umesh Shankar, Sivaramakrishnan Sivasubramanian Abstract Partially ordered patterns (POPs) generalize the classical notion of permutation patterns within the framework of pattern avoidance. Building on recent work by Burstein, Han, Kitaev, and Zhang, which introduced the concept of shape-Wilf-equivalence of sets of patterns, we develop the notions of ordinal and disjoint sums of labeled posets. This framework enables us to reinterpret their main result as an ordinal sum analogue of the classical theorem by Backelin, West, and Xin. We establish analogous results for disjoint sums of POPs and further extend their results to prove Wilf-equivalence for classes of POPs that include isolated vertices. In particular, we prove the shape-Wilf-equivalence of the sets of patterns { 123,213,312 } \{123,213,312\} and { 132,231,321 } \{132,231,321\} . Our proof strategy involves a bijection that filters through an encoding scheme for the transversals avoiding these patterns. We use these results to completely classify the partially ordered patterns of size 3 , 4 , 5 3,4,5 whose connected components are all chains. This classification also confirms a conjecture posed by Dimitrov at the problem session of the British Combinatorics Conference 2024 (BCC30). Keyword: partially ordered pattern, shape-Wilf-equivalence, Wilf-equivalence, poset operation, isolated vertex † † footnotetext: 2020 Mathematics Subject Classification . Primary: 05A05, 05A15. 1 Introduction Let \mathbb{N} denote the set of natural numbers. Let [n]\coloneqq\{1,\dots,n\} and \mathfrak{S}_{n} denote the set of permutations of [n] . An occurrence of a (classical) permutation pattern p=p_{1},p_{2},\ldots,p_{k} in a permutation \pi=\pi_{1}\dots\pi_{n}\in\mathfrak{S}_{n} is a subsequence \pi_{i_{1}}\dots\pi_{i_{k}} that is order isomorphic to p (i.e. \pi_{i_{j}}<\pi_{i_{m}} if and only if p_{j}<p_{m} ). Permutation patterns are very well studied and have many connections to computer science, algebra, geometry and mathematical biology (see the text by Kitaev [ 19 ] and the references therein). Partially order patterns were introduced by Kitaev [ 17 ] and have been extensively studied in words and compositions (see, for example, [ 18 ] , [ 20 ] , [ 15 ] ). A partially ordered pattern (POP) p of size k is defined by a k -element partially ordered set (poset) P labeled by the elements in \{1,\dots,k\} . An occurrence of such a POP p in a permutation \pi=\pi_{1}\dots\pi_{n} is a subsequence \pi_{i_{1}}\dots\pi_{i_{k}} , where 1\leq i_{1}<\dots<i_{k}\leq n , such that \pi_{i_{j}}<\pi_{i_{m}} if and only if j<m in P . We will use the word “pattern” to mean a classical or partially ordered pattern. A permutation \pi is said to avoid a pattern p if it does not contain any occurrences of the pattern p . We denote by \mathfrak{S}_{n}(p) the set of permutations in \mathfrak{S}_{n} that avoid the pattern p . We say that two pattern p,q are Wilf-equivalent , denoted by p\sim q , if \lvert\mathfrak{S}_{n}(p)\rvert=\lvert\mathfrak{S}_{n}(q)\rvert for all n\geq 1 . Alternatively, from the work of Bean et al [ 6 ] , one can define the avoidance of a POP p as a simultaneous avoidance of the set of patterns S that present as (group-theoretic) inverses of linear extensions of p . Therefore, we will not distinguish between a POP and the set of patterns that generate \mathfrak{S}_{n}(p) . In the following, we review the definition of the notion of shape-Wilf-equivalence for POPs. Let us first review some terminology related to pattern avoiding transversals. Throughout the paper, we draw Ferrers boards in French notation (rows increasing in length from top to bottom), and number columns from left to right and rows from bottom to top. We use the square (i,j) to represent the square located in row i and column j . A transversal of a Ferrers board \lambda=(\lambda_{1},\lambda_{2},\dots,\lambda_{n}) with \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}>0 is a 01 -filling of the squares of \lambda with 1 ’s and 0 ’s such that every row and every column contains exactly one 1 . A permutation \pi=\pi_{1}\pi_{2}\dots\pi_{n} can be regarded as a transversal of the n by n square diagram, in which the square (\pi_{i},i) is filled with a 1 for all 1\leq i\leq n and all the other squares are filled with 0 ’s. The transversal corresponding to the permutation \pi is also called the permutation matrix of \pi . Let \mathfrak{S}_{\lambda} denote the set of transversals of the Ferrers board \lambda . For example, let us consider the Ferrers board \lambda=(5,5,4,3,3) and the permutation \pi=45231 . Then \pi can be regarded as the transversal 0 0 1 0 0 1 0 0 0 1 . Given a permutation \alpha of \mathfrak{S}_{m} , let M be its permutation matrix. A transversal T of a Ferrers board \lambda with n columns and n rows will be said to contain the pattern \alpha if there exists two subsets of the index set [n] , namely, R=\{r_{1},r_{2},\dots,r_{m}\} and C=\{c_{1},c_{2},\dots,c_{m}\} , such that the matrix M^{\prime} on the set R of rows and the set C of columns is a copy of M and each of the squares (r_{i},c_{j}) falls within the Ferrers board. In this context, we say that the matrix M^{\prime} is isomorphic to \alpha or the matrix M^{\prime} is an occurrence of \alpha . Otherwise, we say that T avoids the pattern \alpha and T is \alpha -avoiding. Given a set P of patterns, let \mathfrak{S}_{\lambda}(P) denote the set of transversals of the Ferrers board \lambda that avoid each pattern in P . Given two sets P and Q of patterns, we say that P and Q are shape-Wilf-equivalent if \lvert\mathfrak{S}_{\lambda}(P)\rvert=\lvert\mathfrak{S}_{\lambda}(Q)\rvert holds for any Ferrers board \lambda . In this context, we write P\sim_{s}Q . If \{\sigma\}\sim_{s}\{\tau\} , we simply write \sigma\sim_{s}\tau . Clearly, the shape-Wilf-equivalence would imply the Wilf-equivalence. We define the ordinal sum of two labeled posets. First, we recall the ordinal sum of two posets. Let p=(T,\leq_{p}) and q=(T^{\prime},\leq_{q}) be two posets. The ordinal sum p\oplus q is the relation on T\bigsqcup T^{\prime} that satisfies 1. if x,y\in T such that x\leq_{p}y , then x\leq y in p\oplus q ; 2. if x,y\in T^{\prime} such that x\leq_{q}y , then x\leq y in p\oplus q ; 3. if x\in T and y\in T^{\prime} , then x\leq y in p\oplus q . To extend this notion to labeled posets, we specify what happens to the labels of p , q in p\oplus q . The labels L_{p}\subset\mathbb{Z}_{>0} of the poset T in p\oplus q are unchanged while the labels L_{q}\subset\mathbb{Z}_{\geq 0} of the poset T^{\prime} in p\oplus q are all raised by \max(L_{p}) , that is, i is replaced by i+\max(L_{p}) for all i\in L_{q} . In this work, the labeled posets will have labels from \mathbb{Z}_{>0} and no two vertices will have the same label. For example, if p= 1 2 and q=\hbox to28.74pt{\vbox to41.56pt{\pgfpicture\makeatletter\hbox{\hskip 14.36891pt\lower-20.7816pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 0 7.87 M 2.77 7.87 C 2.77 9.4 1.53 10.64 0 10.64 C -1.53 10.64 -2.77 9.4 -2.77 7.87 C -2.77 6.35 -1.53 5.11 0 5.11 C 1.53 5.11 2.77 6.35 2.77 7.87 Z M 0 7.87}{} \lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M -7.87 -7.87 M -5.11 -7.87 C -5.11 -6.35 -6.35 -5.11 -7.87 -5.11 C -9.4 -5.11 -10.64 -6.35 -10.64 -7.87 C -10.64 -9.4 -9.4 -10.64 -7.87 -10.64 C -6.35 -10.64 -5.11 -9.4 -5.11 -7.87 Z M -7.87 -7.87}{} \lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{}\lxSVG@fillstroke\lxSVG@drawpath@unclipped{M 7.87 -7.87 M 10.64 -7.87 C 10.64 -6.35

Read the complete text