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
| CREATOR | Sergi Elizalde, Nadia Lafrenière, Joel Brewster Lewis, Erin McNicholas, Jessica Striker, Amanda Welch |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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])