Problems and results in partially ordered sets, graphs and geometry

Abstract

The thesis consist of three independent parts. In the first part, we investigate the height sequence of an element of a partially ordered set. Let $x$ be an element of the partially ordered set $P$. Then $h_i(x)$ is the number of linear extensions of $P$ in which $x$ is in the $i$th lowest position. The sequence ${h_i(x)}$ is called the height sequence of $x$ in $P$. Stanley proved in 1981 that the height sequence is log-concave, but no combinatorial proof has been found, and Stanley's proof does not reveal anything about the deeper structure of the height sequence. In this part of the thesis, we provide a combinatorial proof of a special case of Stanley's theorem. The proof of the inequality uses the Ahlswede--Daykin Four Functions Theorem.

In the second part, we study two classes of segment orders introduced by Shahrokhi. Both classes are natural generalizations of interval containment orders and interval orders. We prove several properties of the classes, and inspired by the observation, that the classes seem to be very similar, we attempt to find out if they actually contain the same partially ordered sets. We prove that the question is equivalent to a stretchability question involving certain sets of pseudoline arrangements. We also prove several facts about continuous universal functions that would transfer segment orders of the first kind into segments orders of the second kind.

In the third part, we consider the lattice whose elements are the subsets of ${1,2,ldots,n}$. Trotter and Felsner asked whether this subset lattice always contains a monotone Hamiltonian path. We make progress toward answering this question by constructing a path for all $n$ that satisfies the monotone properties and covers every set of size at most $3$. This portion of thesis represents joint work with David M.~Howard.