Mathematisch-Naturwissenschaftliche Fakultät

Institut für Mathematik

Fachgebiet: Diskrete Mathematik

Betreuer: Prof. Dr. Hans-Dietrich Gronau



Matthias Böhm
(e-mail: matthias.boehm2@uni-rostock.de )

Regular Antichains

Diese Arbeit zum Thema "Regular Antichains" ist in die mathematischen Teilgebiete der Sperner- und Designtheorie einzuordnen, formal eher zur ersteren, inhaltlich eher zur zweiteren. Die duale Struktur und der Ursprung des Themengegenstands sind Completely Separating Systems (CSSs). Dabei ist man vor allem an CSSs auf n Punkten und einer konstanten Blockgröße k interessiert, die eine minimale Größe R(n,k) haben. Das Hauptziel dieser Arbeit ist es, neue Erkenntnisse im Bereich der regulären Antiketten zu gewinnen, die insbesondere helfen sollen, unbekannte Werte R(n,k) zu bestimmen. Mithilfe neuer Konstruktionsmethoden wird dies zum Beispiel für k=13 und k=14 komplett erledigt. Allgemein werden außerdem notwendige und hinreichende Existenzbedingungen für reguläre Antiketten hergeleitet. Desweiteren untersuchen wir, welche Werte die Regularität k in Abhängigkeit der Grundmenge überhaupt annehmen kann. Überdies betrachten wir reguläre Antiketten mit den zusätzlichen Eigenschaften, flach und maximal zu sein. Wir verallgemeinern außerdem auf natürliche Weise CSSs und leiten Resultate sowie Konstruktionen für diese allgemeinere Struktur her, die dann insbesondere auch für den Spezialfall der CSS Anwendung finden.

This thesis "Regular Antichains" belongs to the mathematical areas of Sperner theory and design theory, formally rather to the first, with regard to the content more to the second. Completely Separating Systems (CSSs) are the dual structure and the origin of this topic. For given values n and k, an important problem is to determine the minimal size R(n,k) of a CSS on n points and constant block size k. It is the main goal of this thesis to reach new results for regular antichains, which are particularly useful to determine unknown values R(n,k). Using new constructions, we complete the unknown cases for k=13 and k=14. Furthermore, we offer necessary and sufficient conditions for the existence of regular antichains. We analyze if k-regular antichains on {1,...,m} exist for given values k and m. We also have a look at regular antichains which are flat and maximal in addition. Moreover, we generalize CSSs in a natural way, and obtain results and constructions for this generalized structure, which can also be used in the case of CSSs.