- / -

<p> In this thesis we introduce the concept of a dense extension of a partially ordered set and study some of the properties of the resulting class of extensions. In particular we study the dense distributive extensions, dense Boolean extensions and dense meet continuous extensions of distributive, Boolean and meet continuous lattices respectively.</p> / Thesis / Doctor of Philosophy (PhD)

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.

Data on (economic) institutions are often available only as observations on ordinal, inherently incomparable properties, which are then typically aggregated to a composite index in the empirical social science literature. From a methodological perspective, the present paper advocates the application of partially ordered set (POSET) theory as an alternative approach. Its main virtue is that it takes the ordinal nature of the data seriously and dispenses with the unavoidably subjective assignment of weights to incomparable properties, maintains a high standard of objectivity, and can be applied in various fields of economics. As an application, the POSET approach is then used to calculate new indices on the stringency of fiscal rules for 81 countries over the period 1985 to 2012 based on recent data by the IMF (2012). The derived measures of fiscal rules are used to test their significance for public finances in a fiscal reaction function and compare the POSET with the composite index approach. (authors' abstract)

abstract: A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs. / Dissertation/Thesis / Ph.D. Mathematics 2012

In this paper we consider the enumeration of ordered set partitions avoiding a permutation pattern of length 2 or 3. We provide an exact enumeration for avoiding the permutation 12. We also give exact enumeration for ordered partitions with 3 blocks and ordered partitions with n-1 blocks avoiding a permutation of length 3. We use enumeration schemes to recursively enumerate 123-avoiding ordered partitions with any block sizes. Finally, we give some asymptotic results for the growth rates of the number of ordered set partitions avoiding a single pattern; including a Stanley-Wilf type result that exhibits existence of such growth rates.

Convex geometries are combinatorial structures; they capture in an abstract way the essential features of convexity in Euclidean space, graphs or posets for instance. A convex geometry consists of a finite ground set plus a collection of subsets, called the convex sets and satisfying certain axioms. In this work, we study two natural problems on convex geometries. First, we consider the maximum-weight convex set problem. After proving a hardness result for the problem, we study a special family of convex geometries built on split graphs. We show that the convex sets of such a convex geometry relate to poset convex geometries constructed from the split graph. We discuss a few consequences, obtaining a simple polynomial-time algorithm to solve the problem on split graphs. Next, we generalize those results and design the first polynomial-time algorithm for the maximum-weight convex set problem in chordal graphs. Second, we consider the realizability problem. We show that deciding if a given convex geometry (encoded by its copoints) results from a point set in the plane is ER-hard. We complete our text with a brief discussion of potential further work. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

The widespread use of composite indices has often been motivated by their practicality to quantify qualitative data in an easy and intuitive way. At the same time, this approach has been challenged due to the subjective and partly ad hoc nature of computation, aggregation and weighting techniques as well as the handling of missing data. Partially ordered set (POSET) theory offers an alternative approach for summarizing qualitative data in terms of quantitative indices, which relies on a computation scheme that fully exploits the available information and does not require the subjective assignment of weights. The present paper makes the case for an increased use of POSET theory in the social sciences and provides a comparison of POSET indices and composite indices (from previous studies) measuring the 'stringency' of fiscal frameworks using data from the OECD Budget Practices and Procedures survey (2007/08). (authors' abstract) / Series: Department of Economics Working Paper Series

The thesis focuses on two open problems on finite partially ordered sets: the structure of order polytopes and the approximation of the number of linear extensions of a poset by mean of graph entropy. The polytopes considered here are the linear ordering polytope, the semiorder polytope, the interval order polytope, the partial order polytope and also a generalisation of the linear ordering polytope: the linear extension polytope of a fixed poset P. Various results on the structure of theses polytopes are proved in the first part of the thesis. In the second part of the thesis, we improve the existing bounds linking the entropy of the incomparability graph of the poset P and its number of linear extension. / Le but de la thèse est d'étudier deux problèmes ouverts sur les ensembles ordonnés finis: la structure des polytopes d'ordre et l'approximation du nombre d'extensions linéaires d'un ordre partiel au moyen de la notion d'entropie de graphe. Les polytopes considérés sont le polytope des ordres totaux, le polytope des semiordres, le polytope des ordres d'intervalles, le polytope des ordres partiels, ainsi qu'une généralisation du polytope des ordres totaux: le polytope des extensions linéaires d'un ensemble ordonné fixé P. Des résultats sur la structure de ces polytopes sont présentés dans la première partie de la thèse. Dans la deuxième partie de la thèse, nous améliorons les bornes existantes liant l'entropie du graphe d'incomparabilité d'un ordre partiel et son nombre d'extensions linéaires. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Masters of Science / The main purpose of this thesis is to study the interplay between relational structures and topology, and to portray pairings in terms of some finite poset models and order preserving maps. We show the interrelations between the categories of topological spaces, closure spaces and relational structures. We study the 4-point non-Hausdorff model S4 weakly homotopy equivalent to the circle s'. We study pairings of some objects in the category of relational structures, similar to the multiplication of Hopf spaces in topology. The multiplication S4 x S4 ---7 S4 fails to be order preserving for posets. Nevertheless, applying a single barycentric subdivision on S4 to get Ss, an 8-point model of the circle enables us to define an order preserving poset map Ss x Ss ---7 S4' Restricted to the axes, this map yields weak homotopy equivalences Ss ---7 S4' Hence it is a pairing. Further, using the non-Hausdorff join Ss ® Ss, we obtain a version of the Hopf map Ss ® Ss ---7 §S4. This model of the Hopf map is in fact a map of non-Hausdorff double mapping cylinders.