Phase transitions in the evolution of partially ordered sets

Abstract

Unter dem Evolutionsprozeß eines Objekts, das aus einer gegebenen Klasse zufällig ausgewählt wird, versteht man das folgende Gedankenexperiment. Zu einem geeigneten Parameter der Objekte der Klasse betrachtet man die Teilklasse derjenigen Objekte, bei denen dieser Parameter einen bestimmten Wert x annimmt. Dadurch stellen sich die folgenden Fragen: Wie sieht ein typisches Objekt dieser Teilklasse aus? Wieviele Objekte gibt es in der Teilklasse? Und: Wie verändern sich die Antworten auf die ersten beiden Fragen, wenn sich x verändert? Die vorliegende Dissertation behandelt Phasenübergänge im Evolutionsprozeß teilweiser Ordnungen und bestimmt die Anzahl teilweiser Ordnungen mit einer gegebenen Anzahl vergleichbarer Paare. Wir bezeichnen durch Pn,d die Klasse aller teilweisen Ordnungen mit n Punkten und dn2 vergleichbaren Paaren. 1978 bestimmte Dhar |Pn,d| im Intervall 1/8 < d < 3/16 und zeigte, daß hier eine typische Ordnung aus drei "Ebenen" besteht. 1979 bestimmten Kleitman und Rothschild |Pn,d| im Intervall 0 < d < 1/8 und zeigten, daß hier eine typische Ordnung aus zwei Ebenen besteht, also bipartit ist. Das Hauptergebnis der Dissertation ist es, ein vollständiges Bild des Evolutionsprozesses zu geben. Wir bestimmen |Pn,d| im gesamten Intervall 0 < d < 1/2 und zeigen, daß es unendlich viele Phasenübergänge gibt. Abschließend beschreiben wir, wie sich die Struktur einer typischen Ordnung während dieser Phasen verändert.

The evolution process of a random structure from a certain class denotes the following "experiment". Choose a parameter of the objects in the class under consideration and consider only the subclass of those objects where the parameter is equal to a fixed value x. Then the following questions arise quite naturally: What does a typical object from this subclass look like? How many objects are there in this subclass? And how do the answers to the first two questions change when x changes? This thesis investigates the phase transitions in the evolution of partially ordered sets and determines the number of partially ordered sets with a given number of comparable pairs. Denote by Pn,d the class of all n-point posets with dn2 comparable pairs. In 1978, Dhar determined |Pn,d| in the range 1/8 < d < 3/16 and showed that here a typical poset consists of three layers. In 1979, Kleitman and Rothschild determined |Pn,d| in the range 0 < d < 1/8 and showed that here a typical poset consists of two layers, i.e. it is bipartite. The main result of this thesis is to complete the picture by describing the whole evolution process of Pn,d in the range 0 < d < 1/2. We determine |Pn,d| for any d and show that there exist an infinite number of phase transitions. Finally we describe how the structure of a typical partially ordered set changes during these phases.