Statistics on monotonically ordered non-crossing partitions

Natasha Blitvic, Thomas Bray, Jacob Campbell, Alexandru Nica · 2025

Read Statistics on monotonically ordered non-crossing partitions by Natasha Blitvic, Thomas Bray, Jacob Campbell, Alexandru Nica (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-2502-12032.txt.

Introduction

Natasha Blitvic, Thomas Bray, Jacob Campbell, and Alexandru Nica count traits of a tidy kind of split called a non-crossing partition. In such a split, blocks are drawn so no two cross, and here the blocks are kept in a strict rising order. Past counts were known for the plain, unordered kind. Counts for the ordered kind had not been done.

Means and spreads for block counts in the ordered kind grow with a slow log curve, not the pace of the plain kind. The same log pace rules the mean area under ordered pair splits. A tree built across all sizes of the set eases the proofs. A last part puts the counts to work on chance steps of a monotone kind. The paper gives the ordered kind its first full trait map.

Catalog record

CREATORNatasha Blitvic, Thomas Bray, Jacob Campbell, Alexandru Nica
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-12032

Browse the full library · About the Tower of Babel

Full text

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

Statistics on monotonically ordered non-crossing partitions Thanks: NB: research supported by grant EP/V048902 from EPSRC, UK Thanks: AN: research supported by a Discovery Grant from NSERC, Canada. Natasha Blitvic, Thomas Bray, Jacob Campbell, Alexandru Nica Abstract . We study some combinatorial statistics defined on the set N ​ C ( mton ) ​ ( n ) NC^{\mathrm{(mton)}}(n) of monotonically ordered non-crossing partitions of { 1 , … , n } \{1,\ldots,n\} , and on the set N ​ C 2 ( mton ) ​ ( 2 ​ n ) NC^{\mathrm{(mton)}}_{2}(2n) of monotonically ordered non-crossing pair-partitions of { 1 , … , 2 ​ n } \{1,\ldots,2n\} . Unlike in the analogous results known for unordered non-crossing partitions, the computations of expectations and variances for natural block-counting statistics on N ​ C ( mton ) ​ ( n ) NC^{\mathrm{(mton)}}(n) and for the expectation of the area statistic on N ​ C 2 ( mton ) ​ ( 2 ​ n ) NC^{\mathrm{(mton)}}_{2}(2n) turn out to yield a logarithmic regime. An important role in our study is played by a nice tree structure on the disjoint union of the N ​ C ( mton ) ​ ( n ) NC^{\mathrm{(mton)}}(n) ’s, which we use to streamline our arguments. As an illustration of how these ideas can be applied to calculations of cumulants in monotone probability, we discuss some combinatorial aspects of the monotonic Poisson process. 1. Introduction 1.1. NC(n) and NC^{\mathrm{(mton)}}(n) . The NC^{\mathrm{(mton)}} -tree structure. We will use the customary notation NC(n) for the set of non-crossing partitions of \{1,\ldots,n\} . The elements of NC(n) are thus of the form \pi=\{V_{1},\ldots,V_{k}\} , where V_{1},\ldots,V_{k} (the blocks of the partition \pi ) are non-empty pairwise disjoint subsets of \{1,\ldots,n\} , with V_{1}\cup\cdots\cup V_{k}=\{1,\ldots,n\} , and where it is not possible to find a_{1}<a_{2}<a_{3}<a_{4} in \{1,\ldots,n\} such that a_{1},a_{3}\in V_{i} and a_{2},a_{4}\in V_{j} for some i\neq j . The NC(n) ’s are one of the many combinatorial structures counted by Catalan numbers. For a quick introduction to some of their basic properties, one can e.g. consult [ 10 , Lecture 9] . This paper is concerned with sets of monotonically ordered non-crossing partitions. Definition 1.1 . Let n be a positive integer. 1^{o} Let \pi=\{V_{1},\ldots,V_{k}\}\in NC(n) . One has a nesting relation among the blocks of \pi , where “ V_{i} nested inside V_{j} ” means, by definition, that \min(V_{i})>\min(V_{j}) and \max(V_{i})<\max(V_{j}) . We will use the term monotonic ordering of \pi to refer to a bijection u:\pi\to\{1,\ldots,k\} having the property that \bigl[\mbox{$V_{i}$ nested inside $V_{j}$}\bigr]\,\Rightarrow\,\bigl[\,u(V_{i})>u(V_{j})\,\bigr]. 2^{o} We denote NC^{\mathrm{(mton)}}(n):=\bigl\{(\pi,u)\mid\pi\in NC(n)\mbox{ and $u$ is a monotonic ordering of }\pi\bigr\} . Remark 1.2 . For (\pi,u)\in NC^{\mathrm{(mton)}}(n) , one can think of u as “a possible history of how \pi was created, via successive insertions of intervals”. In order to clarify what this means, let us write explicitly \pi=\{V_{1},\ldots,V_{k}\} and let us note that the block V_{j_{o}}:=u^{-1}(k)\in\pi is an interval of \{1,\ldots,n\} . (If not, then there would exist i\neq j_{o} in \{1,\ldots,k\} such that V_{i} is nested inside V_{j_{o}} , hence such that u(V_{i})>u(V_{j_{o}})=k , in contradiction with u(V_{i})\in\{1,\ldots,k\} .) One can view the insertion of the interval V_{j_{o}} as the last step in a k -step process which created \pi , via successive insertions of intervals which eventually became the blocks u^{-1}(1),\ldots,u^{-1}(k) , in this order. For illustration, Figure 1 shows how this process works to create a monotonically ordered partition with 4 blocks in NC(9) . On a heuristic level, one could say that the relation between a (\pi,u)\in NC^{\mathrm{(mton)}}(n) and the underlying \pi\in NC(n) is akin to the relation one has, in the representation theory of symmetric groups, between a standard Young tableau and the underlying Young diagram – the tableau records a possible history of how the Young diagram was created, via addition of boxes. From this perspective, the NC^{\mathrm{(mton)}} -tree that we will next look at is an analogue of the tree of monotonic paths of the well-known Young graph (as presented, for instance, in Section 3.1 of the monograph [ 5 ] ). 1 \rightarrow 1 2 \rightarrow 1 3 2 \rightarrow 4 1 3 2 Figure 1. \pi=\bigl\{\,\{1,2\},\,\{3,4,7,9\},\,\{5,6\},\,\{8\}\,\bigr\}\in NC(9) built in 4 steps, by inserting intervals. The building process gives a monotonic ordering u of \pi : every block of \pi retains the label assigned to it (in boldface font) at the moment when it was inserted in the picture, thus giving u(\,\{3,4,7,9\}\,)=1 , u(\,\{8\}\,)=2 , u(\,\{5,6\}\,)=3 , u(\,\{1,2\}\,)=4 . Remark 1.3 . (The NC^{\mathrm{(mton)}} -tree.) In the considerations of the present paper, a crucial role will be played by a tree structure with vertex set NC^{\mathrm{(mton)}}:=\sqcup_{n=1}^{\infty}NC^{\mathrm{(mton)}}(n) (disjoint union), where the unique element of NC^{\mathrm{(mton)}}(1) serves as root and where, for every n\in\mathbb{N} , the elements of NC^{\mathrm{(mton)}}(n) are at distance n-1 from the root. The formal description of the edges of this NC^{\mathrm{(mton)}} -tree is given in Section 2.1 below. Roughly speaking, it is based on the interpretation of every (\pi,u)\in NC^{\mathrm{(mton)}}(n) as possible history for how the underlying \pi=\{V_{1},\ldots,V_{k}\}\in NC(n) was created, but where we amend the k -step creation process described in Remark 1.2 , and make it become an n -step creation process (use the number n of points that are being partitioned, rather than the number k of blocks of \pi ). That is: instead of “intervals inserted from above” as in Figure 1, we will now look at insertions of individual points, as shown in Figure 2. At every step, the new incoming point: either starts a new block of the partition which is being built, or appends itself to the highest-numbered block (necessarily an interval block) that already existed in the picture. Specifically, Figure 2 shows the same partition \pi\in NC^{\mathrm{(mton)}}(9) as in Figure 1, where the construction of \pi now takes 9 steps (rather than 4 steps, as before). 1 \longrightarrow 1 \longrightarrow 1 \longrightarrow 1 \Big\downarrow 1 2 \longleftarrow 1 3 2 \longleftarrow 1 3 2 \Big\downarrow 4 1 3 2 \longrightarrow 4 1 3 2 Figure 2. \pi=\bigl\{\,\{1,2\},\,\{3,4,7,9\},\,\{5,6\},\,\{8\}\,\bigr\}\in NC(9) built in 9 steps, by inserting points. The building process gives the path in the NC^{\mathrm{(mton)}} -tree which starts at the root of the tree and arrives at the monotonically ordered non-crossing partition from Figure 1. Remark 1.4 . (Homogeneity property of the NC^{\mathrm{(mton)}} -tree.) One has that: (1.1) \left\{\begin{array}[]{c}\mbox{for every $n\in\mathbb{N}$, every $(\pi,u)\in NC^{\mathrm{(mton)}}(n)$}\\ \mbox{has precisely $n+2$ children in the $NC^{\mathrm{(mton)}}$-tree.}\end{array}\right. This is a fact that is easy to verify (cf. Remark 2.5 below), but nevertheless has great benefits towards the study of block-counting statistics on NC^{\mathrm{(mton)}}(n) , because it provides recursions satisfied by such statistics. A number of results obtained in this way are described in the next subsection. We note that, as a byproduct, the homogeneity from ( 1.1 ) can be used as an entry point towards some non-commutative probability considerations. It is relevant to mention here that NC(n) and NC^{\mathrm{(mton)}}(n) play crucial roles in the combinatorics of two brands of independence for non-commutative random variables, free independence and respectively monotonic independence . In particular, each of these of two brands of independence uses a notion of cumulants for the non-commutative random variables that are considered, where the cumulants of free probability

Read the complete text