Content area
Abstract
A linear extension of a partially ordered set is simply a total ordering of the poset that is consistent with the original ordering. The linear extension diameter is a measure of how different two linear extensions could be, that is, the number of pairs of elements that are ordered differently by the two extensions. In this dissertation, we calculate the linear extension diameter of grids. This also gives us a nice characterization of the linear extensions that are the farthest from each other, and allows us to conclude that grids are diametrally reversing.
A linear extension of a poset might be considered "good" if incomparable elements appear near to one another. The linear discrepancy of a poset is a natural way of measuring just how good the best linear extension of that poset can be, i.e. [special characters omitted] where L ranges over all linear extensions of P mapping P to {1, 2, …, |P|}. In certain situations, it makes sense to weaken the definition of a linear extension by allowing elements of the poset to be sent to the same integer, while still requiring that x < y implies L(x) < L( y). This is known as a weak labeling. Similar to linear discrepancy, the weak discrepancy measures how nicely we can weakly label the elements of the poset. In this dissertation, we calculate the weak discrepancy of grids, the permutohedron, the partition lattice, and the two-dimensional Young's lattice.
