THE WEAK DISCREPANCY AND LINEAR EXTENSION DIAMETER OF GRIDS AND OTHER POSETS

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. ld(P) = min L max x | | y |L(x) − L(y)|