Combinatorial problems for graphs and partially ordered sets

Abstract

This dissertation has three principal components. The first component is about the connections between the dimension of posets and the size of matchings in comparability and incomparability graphs. In 1951, Hiraguchi proved that for any finite poset P, the dimension of P is at most half of the number of points in P. We develop some new inequalities for the dimension of finite posets. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d is at least 3, then there is a matching of size d in the comparability graph of P, and a matching of size d in the incomparability graph of P. The bounds in above theorems are best possible, and either result has Hiraguchi's theorem as an immediate corollary. In the second component, we focus on an extremal graph theory problem whose solution relied on the construction of a special kind of posets. In 1959, Paul Erdos, in a landmark paper, proved the existence of graphs with arbitrarily large girth and arbitrarily large chromatic number using probabilistic method. In a 1991 paper of Kriz and Nesetril, they introduced a new graph parameter eye(G). They show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most three. Answering a question of Kriz and Nesetril, we were able to strengthen their results and show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most two. The last component is about random posets--the poset version of the Erdos-Renyi random graphs. In 1991, Erdos, Kierstead and Trotter (EKT) investigated random height 2 posets and obtained several upper and lower bounds on the dimension of the random posets. Motivated by some extremal problems involving conditions which force a poset to contain a large standard example, we were compelled to revisit this subject. Our sharpened analysis allows us to conclude that as p approaches 1, the expected value of dimension first increases and then decreases, a subtlety not identified in EKT. Along the way, we establish connections with classical topics in analysis as well as with latin rectangles. Also, using structural insights drawn from this research, we are able to make progress on the motivating extremal problem with an application of the asymmetric form of the Lovasz Local Lemma.