Orientation of ordered sets: Their structure and enumeration.

Abstract

The aim of this thesis is to enumerate and classify order diagrams. Some new characterizations will be proved. We also obtain new upper bounds and lower bounds, asymptotic estimation and even precise formulas. The proofs use deep ideas from combinatorial optimization, graph theory and the theory of ordered sets. After a brief account of some basic definitions, notation and terminology that will be used in this thesis, we investigate. In Chapter 2, a new and efficient characterization for inversions will be given. In chapter 3, we study two important properties or ordered sets--planarity and s-genus. In Chapter 4, we enumerate the number of reorientations of an ordered set. Some interesting counter examples are provided. In the last chapter, we will consider some problems in computational geometry. To summarize, here are the main new results that will be proved in this thesis. Theorem 2.2.1. An ordered set Q is an inversion of an ordered set P if and only if the reversed edges can be partitioned into cuts. Theorem 2.2.2. There is an algorithm with complexity $O(ISI\sp5)$ to test whether an ordered set is an inversion of another. Theorem 3.2.9. A bipartite ordered set is planar if and only if its covering graph is planar. Theorem 3.3.1. Any n-element outerplanar covering graph has at least $2\sp{\rm n/2}$ planar orientations. Theorem 4.2.1. There is a covering graph G some of whose independent sets cannot be the set of maximal elements of some orientation of G. Theorem 4.2.4. There is an ordered set such that for some matching M and a subset $M\sp\prime$ of M, there is not reorientation which reverses the edges of $M\sp\prime$ and none of M-M$\sp\prime$. Theorem 4.4.1. Almost any n-element covering graph has at least $2\sp{\rm n/3}$ orientations. Theorem 4.4.3. Any n-element planar covering graph has at least $2\sp{\rm n/3}$ orientations. Theorem 4.4.7. Any n-element lattice with girth at least seven has at least $2\sp{\rm n/3}$ orientations.