Widths of Finite Posets under the Majorization Ordering

Abstract

This dissertation focuses on the structural properties of two types of posets, \(P(n,m)\) and \(P'(n,m)\), both of which are ordered by the majorization ordering. Specifically, we consider those cases where \(1 \leq n \leq 4\). The poset \(P(n,m)\) consists of sequences of non-negative integers of length \(n\) that sum to \(m\), more formally defined as \(P(n,m) = \{x \in (\mathbb{Z}_{\geq 0})^n : \sum_{i=0}^{n-1} x_i =m\}\). The second poset, \(P'(n,m)\), is a subposet of \(P(n,m)\) where we restrict the sequences to be decreasing, i.e., \(P'(n,m) = \{x \in (\mathbb{Z}_{\geq 0})^n : \sum_{i=0}^{n-1} = m \text{ and } x_i \geq x_{i+1}\}\).

We define the majorization ordering to be: for any two sequences \(x,y \in (\mathbb{Z}_{\geq 0})^n\) we say that \(x\) is majorized by \(y\) if the following conditions hold: \[ \sum_{i=0}^{j-1}x_i \leq \sum_{i=0}^{j-1}y_i \hspace{15pt} \text{for } 0 \leq j - 1 < n-1 , \hspace{5pt} \sum_{i=0}^{n-1}x_i = \sum_{i=0}^{n-1}y_i \] We demonstrate that these posets exhibit Sperner-like properties. In particular, we show that the largest antichain in \(P(n,m)\) and \(P'(n,m)\) for \(1 \leq n \leq 4\) is realized by a ``middle'' ``level'', similar to that of the classical Sperner theorem. However since \(P'(n,m)\) is not a graded poset, it does not have true levels, which is why we refer to these properties as ``Sperner-like''. We also use the term ``middle'' loosely here, as there may be many levels or induced levels which are maximal, and they all generally occur in the middle section of these posets. Despite this, many of the structural properties of \(P(n,m)\) are inherited by \(P'(n,m)\).

In the case of \(P(n,m)\), we provide explicit chain decompositions, while for \(P'(n,m)\) we give explicit chain decompositions for \(n \in \{1,2\}\). For \(P'(n,m)\) when \(n \in \{3,4\}\), we give an inductive proof of the existence of a minimal chain decomposition on the outer layer(s), with induction handling the smaller poset.