Enumeration of interval-closed sets via Motzkin paths and quarter-plane walks

Sergi Elizalde, Nadia Lafrenière, Joel Brewster Lewis, Erin McNicholas, Jessica Striker, Amanda Welch · 2024

Read Enumeration of interval-closed sets via Motzkin paths and quarter-plane walks by Sergi Elizalde, Nadia Lafrenière, Joel Brewster Lewis, Erin McNicholas, Jessica Striker, Amanda Welch (2024) 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-2412-16368.txt.

Introduction

Sergi Elizalde, Nadia Lafreniere, and colleagues count special set families in grid-shaped orders in a 2024 combinatorics study. An interval-closed set in a partially ordered set is one that traps everything between any two of its members. The authors study these sets in the product of two chains, a grid of points ranked by both coordinates.

A bijection to two-colored Motzkin paths, walks that never dip below the axis, yields a generating function for the count. For truncated rectangle orders, including a root poset from Lie theory, a bijection to walks in a quarter plane gives a functional equation instead. Bijection turns counting into walk enumeration.

Catalog record

CREATORSergi Elizalde, Nadia Lafrenière, Joel Brewster Lewis, Erin McNicholas, Jessica Striker, Amanda Welch
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-16368

Browse the full library · About the Tower of Babel

Full text

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

Enumeration of interval-closed sets via Motzkin paths and quarter-plane walks Sergi Elizalde, Nadia Lafrenière, Joel Brewster Lewis, Erin McNicholas, Jessica Striker, Amanda Welch Abstract We find a generating function for interval-closed sets of the product of two chains poset by constructing a bijection to certain bicolored Motzkin paths. We also find a functional equation for the generating function of interval-closed sets of truncated rectangle posets, including the type A A root poset, by constructing a bijection to certain quarter-plane walks. 1 Introduction Interval-closed sets of partially ordered sets, or posets, are an interesting generalization of both order ideals (downward-closed subsets) and order filters (upward-closed subsets). Also called convex subsets, the interval-closed sets of a poset P are defined to be the subsets I\subseteq P such that if x,y\in I and there is an element z with x<z<y , then z\in I . In other words, I contains all elements of P between any two elements of I . Interval-closed sets are important in operations research and arise in applications such as project scheduling and assembly line balance [ 8 ] . Although order ideals of posets have been well studied from enumerative, bijective, and dynamical perspectives, interval-closed sets have not received as much attention. A recent paper [ 3 ] initiated the study of interval-closed sets of various families of posets from enumerative and dynamical perspectives. In this paper, we continue to study the enumeration of interval-closed sets of specific families of posets, finding useful bijections along the way, while in the companion paper [ 6 ] , we extend the study of interval-closed set rowmotion dynamics. The main results of the present paper include a generating function for interval-closed sets of the product of two chains poset [m]\times[n] , from which we extract explicit formulas for small values of m , and functional equations for the generating functions of interval-closed sets of truncated rectangle posets, a family that includes the type A root posets. In both cases, we define bijections from interval-closed sets to various kinds of lattice paths, namely, certain bicolored Motzkin paths and quarter-plane walks. Our first main result, stated as Theorem 3.3 , is a bijection between the set of interval-closed sets of [m]\times[n] and the set of bicolored Motzkin paths with certain restrictions; specifically, the number of up steps and horizontal steps of the first color is m , the number of down steps and horizontal steps of the second color is n , and no horizontal step of the second color on the x -axis is followed by a horizontal step of the first color. We use this bijection to find the following generating function. Theorem 3.5 . The generating function of interval-closed sets of [m]\times[n] is given by \sum_{m,n\geq 0}\left|\mathcal{IC}([m]\times[n])\right|\,x^{m}y^{n}=\frac{2}{1-x-y+2xy+\sqrt{(1-x-y)^{2}-4xy}}. One may use this generating function to extract counting formulas for fixed values of m , such as the following result. Corollary 3.6 . The cardinality of \mathcal{IC}([3]\times[n]) is \frac{n^{6}+9n^{5}+61n^{4}+159n^{3}+370n^{2}+264n+144}{144}. Let \mathfrak{B}_{n} denote the type B_{n} minuscule poset (illustrated in Figure 7 ), whose interval-closed sets are in bijection with vertically symmetric interval-closed sets of [n]\times[n] . Theorem 3.9 . The generating function of interval-closed sets of \mathfrak{B}_{n} is given by \sum_{n\geq 0}\left|\mathcal{IC}(\mathfrak{B}_{n})\right|\,x^{n}=\frac{4-10x+8x^{2}}{2-11x+14x^{2}-8x^{3}-(2-3x)\sqrt{1-4x}}. Let \mathbf{A}_{n} denote the type A_{n} positive root poset (illustrated in Figure 8 ). In Theorem 4.1 , we construct a bijection between the set of interval-closed sets of \mathbf{A}_{n-1} and the set of lattice walks in the first quadrant that start and end at the origin and consist of 2n steps from the set \{(1,0),(-1,0),(1,-1),(-1,1)\} , where no (-1,0) step on the x -axis is immediately followed by a (1,0) step. We use this bijection to derive the following functional equation for the generating function. Theorem 4.3 . The generating function of interval-closed sets of \mathbf{A}_{n-1} can be expressed as \sum_{n\geq 0}\left|\mathcal{IC}(\mathbf{A}_{n-1})\right|z^{2n}=F(0,0,z), where F(x,y):=F(x,y,z) satisfies the functional equation F(x,y)=1+z\left(x+\frac{1}{x}+\frac{x}{y}+\frac{y}{x}\right)F(x,y)-z\left(\frac{1}{x}+\frac{y}{x}\right)F(0,y)-z\,\frac{x}{y}F(x,0)-z^{2}\,\left(F(x,0)-F(0,0)\right). We derive in Theorems 4.5 and 4.7 generalizations of these theorems to the poset obtained by truncating the bottom d ranks from [m]\times[n] . (Note that \mathbf{A}_{n-1} may be obtained by truncating the bottom n ranks from [n]\times[n] .) We also find a similar functional equation in Theorem 4.4 for symmetric ICS of \mathbf{A}_{n-1} and use this to extract the enumeration of ICS of the type B positive root poset (illustrated in Figure 10 ). The paper is organized as follows. Section 2 gives necessary poset-theoretic definitions and states relevant enumerative theorems from [ 3 ] . Section 3 studies interval-closed sets of [m]\times[n] and their corresponding bicolored Motzkin paths, proving the bijection of Theorem 3.3 , and the generating functions of Theorems 3.5 and 3.9 . It also proves Theorem 3.7 , which translates statistics of interest on each side of the bijection. Section 4 studies interval-closed sets of the type A root posets and truncated rectangle posets, proving Theorems 4.1 and 4.3 on the poset \mathbf{A}_{n-1} , Theorem 4.4 on symmetric ICS of \mathbf{A}_{n-1} , and Theorems 4.5 and 4.7 on truncated rectangle posets. Section 4 also contains Theorem 4.8 , which again translates statistics across the relevant bijection. We end in Section 5 with some ideas for future work. 2 Definitions and background Let P be a partially ordered set (poset). All posets in this paper are finite. Below we introduce the poset-theoretic definitions that are most relevant to this paper, and refer to [ 10 , Ch. 3] for a more thorough discussion. Definition 2.1 . Let I\subseteq P . We say that I is an interval-closed set (ICS) of P if for all x,y\in I and z\in P such that x<z<y , we have z\in I . Let \mathcal{IC}(P) denote the set of all interval-closed sets of P . Definition 2.2 . A subset J\subseteq P is an order ideal if whenever b\in J and a\leq b , we have a\in J . A subset K is an order filter if whenever a\in K and a\leq b , we have b\in K . Given S\subseteq P , let \Delta(S) denote the smallest order ideal containing S , and let \nabla(S) denote the smallest order filter containing S . Definition 2.3 . The n -element chain poset has elements 1<2<\cdots<n and is denoted by [n] . In this paper, we study the poset constructed as the Cartesian product of two chains. Its elements are [m]\times[n]=\{(i,j)\ |\ 1\leq i\leq m,1\leq j\leq n\} , and the partial order is given by (a,b)\leq(c,d) if and only if a\leq c and b\leq d . Our convention is to draw the Hasse diagram of [m]\times[n] as a tilted rectangle with poset element (1,1) at the bottom, incrementing the first coordinate in the northeast direction and the second coordinate in the northwest direction, as in Figure 1 . (1,9) (7,1) m=7 n=9 Figure 1 : An interval-closed set of the poset [7]\times[9] Definition 2.4 . An antichain poset of m distinct, pairwise incomparable elements is denoted as \mathbf{m} . The ordinal sum of n antichains \mathbf{a}_{1}\oplus\mathbf{a}_{2}\oplus\cdots\oplus\mathbf{a}_{n} is the poset constructed using the elements from these antichain posets with order relation a\leq b whenever a\in\mathbf{a}_{i},b\in\mathbf{a}_{j} and i\leq j . In [ 3 ] , the authors enumerated interval-closed sets of various families of posets. Generalizing the simple fact that the cardinality of \mathcal{IC}([n])

Read the complete text