In dieser Arbeit wird das Fraïssé-Hrushowskis Amalgamationsverfahren in Zusammenhang mit nilpotenten graduierten Lie Algebren über einem endlichen Körper untersucht. Die Prädimensionen die in der Konstruktion auftauchen sind mit dem gruppentheoretischen Begriff der Defizienz zu vergleichen, welche auf homologische Methoden zurückgeführt werden kann. Darüber hinaus wird die Magnus-Lazardsche Korrespondenz zwischen den oben genannten Lie Algebren und nilpotenten Gruppen von Primzahl-Exponenten beschrieben. Dabei werden solche Gruppen durch die Baker-Haussdorfsche Formel in den entsprechenden Algebren definierbar interpretiert. Es wird eine omega-stabile Lie Algebra von Nilpotenzklasse 2 und Morleyrang omega + omega erhalten, indem man eine unkollabierte Version der von Baudisch konstruierten "new uncountably categorical group" betrachtet. Diese wird genau analysiert. Unter anderem wird die Unabhängigkeitsrelation des Nicht-Gabelns durch die Konfiguration des freien Amalgams charakterisiert. Mittels eines induktiven Ansatzes werden die Grundlagen entwickelt, um neue Prädimensionen für Lie Algebren der Nilpotenzklassen größer als zwei zu schaffen. Dies erweist sich als wesentlich schwieriger als im Fall 2. Wir konzentrieren uns daher auf die Nilpotenzklasse 3, als Induktionsbasis des oben genannten Prozesses. In diesem Fall wird die Invariante der Defizienz auf endlich erzeugte Lie Algebren adaptiert. Erstes Hauptergebnis der Arbeit ist der Nachweis dass diese Definition zu einem vernüftigen Begriff selbst-genügender Erweiterungen von Lie Algebren führt und sehr nah einer gewünschten Prädimension im Hrushovskischen Sinn ist. Wir zeigen – als zweites Hauptergebnis – ein erstes Amalgamationslemma bezüglich selbst-genügender Einbettungen. / In this work, the so called Fraïssé-Hrushowski amalgamation is applied to nilpotent graded Lie algebras over the p-elements field with p a prime. We are mainly concerned with the uncollapsed version of the original process. The predimension used in the construction is compared with the group theoretical notion of deficiency, arising from group Homology. We also describe in detail the Magnus-Lazard correspondence, to switch between the aforementioned Lie algebras and nilpotent groups of prime exponent. In this context, the Baker-Hausdorff formula allows such groups to be definably interpreted in the corresponding algebras. Starting from the structures which led to Baudisch’ new uncountably categorical group, we obtain an omega-stable Lie algebra of nilpotency class 2, as the countable rich Fraïssé limit of a suitable class of finite Lie algebras. We study the theory of this structure in detail: we show its Morley rank is omega+omega and a complete description of non-forking independence is given, in terms of free amalgams. In a second part, we develop a new framework for the construction of deficiency-predimensions among graded Lie algebras of nilpotency class higher than 2. This turns out to be considerably harder than the previous case. The nil-3 case in particular has been extensively treated, as the starting point of an inductive procedure. In this nilpotency class, our main results concern a suitable deficiency function, which behaves for many aspects like a Hrushovski predimension. A related notion of self-sufficient extension is given. We also prove a first amalgamation lemma with respect to self-sufficient embeddings.

Die Arbeit untersucht lokale Geometrien, die Twistorspinoren zulassen auf pseudo-Riemannschen Mannigfaltigkeiten beliebiger Signatur. Hierzu entwickeln wir die benötigten Methoden, nämlich das konforme Traktorkalkül, welches eine konform-invariante Beschreibung von Twistorspinoren als parallele Objekte ermöglicht, weiter. In diesem Zusammenhang ist unser erstes zentrales Resultat ein Klassifikationssatz für konforme Strukturen, deren Holonomiegruppen einen total ausgearteten Unterraum beliebiger Dimension invariant lassen. Hierauf aufbauend können wir einen partiellen Klassifikationssatz für konforme Strukturen mit Twistorspinoren beweisen. Weiterhin studieren wir die Nullstellenmenge eines Twistorspinors unter Nutzung der Theorie der Orbitzerlegungen für parabolische Geometrien. Wir können die lokale geometrische Struktur der Nullstellenmenge vollständig beschreiben und zeigen, dass lokal jeder Twistorspinor mit Nullstelle konform äquivalent zu einem parallelem Spinor ist. Eine Anwendung dieser Resultate auf niedrig-dimensionale Split-Signaturen führt zu einer vollständigen geometrischen Beschreibung von Mannigfaltigkeiten mit nicht-generischen Twistorspinoren in den Signaturen (3,2) und (3,3) durch parallele Spinoren, was die schon bekannte Analyse des generischen Falls komplementiert. Darüberhinaus wenden wir das Traktorkalkül an, um einer konformen Spin- Mannigfaltigkeit auf natürliche Weise eine konforme Superalgebra zuzuordnen. Dieser Zugang führt zu verschiedenen Resultaten, die algebraische Eigenschaften dieser Superalgebra mit speziellen Geometrien auf der zugrundeliegenden Mannigfaltigkeit in Verbindung bringen. Weiterhin erhält man so neue Konstruktionsprinzipien für Twistorspinoren und konforme Killingformen. Zuletzt führen wir den Begriff der konformen Spin-c-Geometrie ein. Unter anderem liefern spezielle Spin-c-Twistorspinoren eine neue Charakterisierung von Fefferman-Räumen. / The present thesis studies local geometries admitting twistor spinors on pseudo- Riemannian manifolds of arbitrary signature. To this end, we refine and extend the necessary machinery of first prolongation of conformal structures and conformal tractor calculus which allows a conformally-invariant description of twistor spinors as parallel objects. In this context, our first main theorem is a classification result for conformal geometries whose conformal holonomy group admits a totally degenerate invariant subspace of arbitrary dimension. Based on this we are able to prove a partial classification result for conformal structures admitting twistor spinors. Moreover, we study the zero set of a twistor spinor using the theory of curved orbit decompositions for parabolic geometries. We can completely describe the local geometric structure of the zero set and show that locally every twistor spinor with zero is equivalent to a parallel spinor off the zero set. An application of these results in low-dimensional split-signatures leads to a complete geometric description of manifolds admitting non-generic twistor spinors in signatures (3,2) and (3,3) in terms of parallel spinors which complements the well-known analysis of the generic case. Moreover, we apply tractor calculus for the construction of a conformal superalgebra naturally associated to a conformal spin structure. This approach leads to various results linking algebraic properties of the superalgebra to special geometric structures on the underlying manifold. It also exhibits new construction principles for twistor spinors and conformal Killing forms. Finally, we introduce and elaborate on the notion of conformal Spin-c-geometry. Among other aspects, this gives rise to a new characterization of Fefferman spaces in terms of distinguished Spin-c-twistor spinors.

Gegenstand dieser Arbeit sind stochastische Kontrollprobleme im Kontext von optimaler Portfolioliquidierung in illiquiden Märkten. Dabei betrachten wir sowohl Markovsche sowie nicht-Markovsche Preiseinflussfunktionale und berücksichtigen den Handel sowohl im Primärmarkt als auch in Dark Pools. Besonderes Merkmal von Liquidierungsproblemen ist die durch die Liquidierungsbedingung induzierte singuläre Endbedingung an die Wertfunktion. Der Standardansatz für linear-quadratische Probleme reduziert die HJB-Gleichungen für die Wertfunktion - je nach Zustandsdynamik - auf (ein System) partielle(r) Differentialgleichungen, stochastische(r) Rückwärtsdifferentialgleichungen beziehungsweise stochastische(r) partielle(r) Rückwärtsdifferentialgleichungen (BSPDE). Wir beweisen neue Existenz-, Eindeutigkeits- und Regularitätsresultate für diese zur Lösung optimaler Liquidierungsprobleme verwendeten Differentialgleichungen mit singulärer Endbedingung, verifizieren die Charakterisierung der zugehörigen Wertfunktion anhand dieser Differentalgleichungen und geben die optimale Handelsstrategie in Feedbackform. Für Markovsche und nicht-Markovsche Preiseinflussmodelle wird eine neuartiger Ansatz basierend auf der genauen singulären Asymptotik der Wertfunktion vorgelegt. Für vollständig Markovsche Liquidierungsprobleme erlaubt uns dieser, die Existenz glatter Lösungen der singulären partiellen Differentialgleichungen zu zeigen. Für eine Klasse von Problemen mit Markovscher/nicht-Markovscher Struktur charakterisieren wir die HJB-Gleichungen durch eine singuläre BSPDE, für die wir die Existenz und Eindeutigkeit einer Lösung über einen Bestrafungsansatz herleiten. / We study stochastic optimal control problems arising in the framework of optimal portfolio liquidation under limited liquidity. Our framework is flexible enough to allow for Markovian and non-Markovian impact functions and for simultaneous trading in primary venues and dark pools. The key characteristic of portfolio liquidation models is the singular terminal condition of the value function that is induced by the liquidation constraint. For linear-quadratic models, the standard ansatz reduces the HJB equation for the value to a (system of) partial differential equation(s), backward stochastic differential equation(s) or backward stochastic partial differential equation(s) with singular terminal condition, depending on the choice of the cost coefficients. We establish novel existence, uniqueness and regularity results for (BS)PDEs with singular terminal conditions arising in models of optimal portfolio liquidation, prove that the respective value functions can indeed be described by a (BS)PDE, and give the optimal trading strategies in feedback form. For Markovian and non-Markovian impact models we establish a novel approach based on the precise asymptotics of the value function at the terminal time. For purely Markovian liquidation problems this allows us to establish the existence smooth solutions to singular PDEs. For a class mixed Markovian/non-Markovian models we characterize the HJB equation in terms of a singular BSPDE for which we establish existence and uniqueness of a solution using a stochastic penalization method.

Diese Arbeit widmet sich der Untersuchung von zwei Problemen der abzählenden Geometrie im Zusammenhang mit linearen Systemen auf algebraischen Kurven. Das erste Problem besteht darin, die Frage der Gültigkeit der Jonquières-Formeln zu klären. Diese Formeln berechnen die Anzahl von Divisoren mit vorgeschriebener Multiplizität, genannt de Jonquières-Divisoren, die in einem linearen System auf einer glatten projektiven Kurve enthalten sind. Um dies zu tun, konstruieren wir den Raum der de Jonquières-Divisoren als einen Determinantenzyklus des symmetrischen Produkts der Kurve und beweisen, dass er für eine allgemeine Kurve die erwartete Dimension hat. Dabei beschreiben wir die Degenerationen der Jonquières-Divisoren zu den Knotenkurven sowohl mit linearen Systemen als auch mit kompaktifizierten Picard-Schemata. Das zweite Problem behandelt Zyklen von Untergeordneten-, oder allgemeiner, Sekanten-Divisoren zu einem gegebenen linearen System auf einer Kurve. Wir betrachten den Durchschnitt zweier solcher Zyklen, die Sekanten-Divisoren von zwei verschiedenen linearen Systemen auf der gleichen Kurve entsprechen, und untersuchen die Gültigkeit der enumerativen Formeln, die die Anzahl der Teiler im Durchschnitt zählen. Wir untersuchen einige interessante Fälle mit unerwarteten Transversalitätseigenschaften und etablieren eine allgemeine Methode, um zu überprüfen, wann dieser Durchschnitt leer ist. / This thesis is dedicated to the study of two enumerative geometry problems in the context of linear series on algebraic curves. The first problem is that of settling the issue of the validity of the de Jonquières formulas. These formulas compute the number of divisors with prescribed multiplicity, or de Jonquières divisors, contained in a linear series on a smooth projective curve. To do so, we construct the space of de Jonquières divisors as a determinantal cycle of the symmetric product of the curve and prove that, for a general curve with a general linear series, it is of expected dimension. In doing so, we describe the degenerations of de Jonquières divisors to nodal curves using both limit linear series and compactified Picard schemes. The second problem deals with cycles of subordinate or, more generally, secant divisors to a given linear series on a curve. We consider the intersection of two such cycles corresponding to secant divisors of two different linear series on the same curve and investigate the validity of the enumerative formulas counting the number of divisors in the intersection. We study some interesting cases, with unexpected transversality properties, and establish a general method to verify when this intersection is empty.

Binary Decision Diagrams (BDDs) sind eine Datenstruktur für Boolesche Funktionen, die auch unter dem Namen branching program bekannt ist. In ordered binary decision diagrams (OBDDs) müssen die Tests einer festen Variablenordnung genügen. In free binary decision diagrams (FBDDs) darf jede Variable höchstens einmal getestet werden. Die Effizienz neuer Varianten des BDD-Konzepts wird gewöhnlich anhand spektakulärer (worst-case) Beispiele aufgezeigt. Wir verfolgen einen anderen Ansatz und vergleichen die Darstellungsgrößen für fast alle Booleschen Funktionen. Während I. Wegener bewiesen hat, daß für die `meisten' n die erwartete OBDD-Größe einer zufälligen Booleschen Funktion von n Variablen gleich der worst-case Größe bis auf Terme kleinerer Ordnung ist, zeigen wir daß dies nicht der Fall ist für n innerhalb von Intervallen konstanter Länge um die Werte n = 2h + h. Ferner gibt es Bereiche von n, in denen minimale FBDDs fast immer um mindestens einen konstanten Faktor kleiner sind als minimale OBDDs. Unsere Hauptsätze ha ben doppelt exponentielle Wahrschein- lichkeitsschranken (in n). Außerdem untersuchen wir die Entwicklung zufälliger OBDDs und ihrer worst-case Größe und decken dabei ein oszillierendes Verhalten auf, das erklärt, warum gewisse Aussagen im allgemeinen nicht verstärkt werden können. / Binary Decision Diagrams (BDDs) are a data structure for Boolean functions which are also known as branching programs. In ordered binary decision diagrams (OBDDs), the tests have to obey a fixed variable ordering. In free binary decision diagrams (FBDDs), each variable can be tested at most once. The efficiency of new variants of the BDD concept is usually demonstrated with spectacular (worst-case) examples. We pursue another approach and compare the representation sizes of almost all Boolean functions. Whereas I. Wegener proved that for `most' values of n the expected OBDD size of a random Boolean function of n variables is equal to the worst-case size up to terms of lower order, we show that this is not the case for n within intervals of constant length around the values n = 2h + h. Furthermore, ranges of n exist for which minimal FBDDs are almost always at least a constant factor smaller than minimal OBDDs. Our main theorems have doubly exponentially small probability bounds (in n). We also investigate the evolution of random OBDDs and their worst-case size, revealing an oscillating behaviour that explains why certain results cannot be improved in general.

Ziel dieser Arbeit ist es, die Rolle von Pfaden für die Ausbreitung von Infektionskrankheiten auf komplexen Netzwerken zu untersuchen. Wir zeigen die Relevanz von Pfaden im Kontext der Epidemiologie in statischen und zeitabhängigen Netzwerken. Ein zentrales Ergebnis ist hierbei die Erreichbarkeitsentwicklung, die eine Analyse der Pfadstruktur zeitabhängiger Netzwerke erlaubt. In dieser Dissertation wird der Einfluss zweier bestimmter Merkmale statischer Netzwerke auf die Eigenschaften ihrer Pfadstruktur untersucht. Als Fallbeispiel analysieren wir hierfür ein Viehhandelsnetzwerk in Deutschland. Dieses Netzwerk besitzt eine Riesenkomponente und eine modulare Struktur. Die wichtigsten Ergebnisse sind hierbei, dass Netzwerke, die nahe an der Perkolationsschwelle liegen, mit großer Wahrscheinlichkeit zwei disjunkte Risikoklassen für Knoten aufweisen und, dass eine modulare Struktur eine signifikante Verzögerung von Krankheitsausbrüchen zur Folge hat. Hervorzuheben sind außerdem die Methoden, die hier zur Analyse zeitabhängiger Netzwerke vorgestellt werden. Das sind Systeme, in denen das Auftreten von Kanten mit der Zeit variiert. In dieser Arbeit stellen wir eine neue Methode vor, mit der die kausale Erreichbarkeit eines zeitabhängigen Netzwerks berechnet werden kann. Darüber hinaus stellen wir Erreichbarkeitsentwicklung als eine neue Methode zur Berechnung kürzester Pfaddauern in zeitabhängigen Netzwerken vor. Diese Herangehensweise ermöglicht es, charakteristische Zeitskalen für das Durchqueren von zeitabhängigen Netzwerken aufzuzeigen. Die Kenntnis solcher Zeitskalen ist von fundamentaler Wichtigkeit für die Abschätzung von Zeiten, die für die Verbreitung von Epidemien benötigt werden. Die Erreichbarkeit eines zeitabhängigen Netzwerks kann mit ihrem aggregierten Gegenstück verglichen werden. Damit definieren wir die Kausalitätstreue, die die Güte einer statischen Approximation eines zeitabhängigen Netzwerks quantifiziert. / The objective of this thesis is to examine the role of paths for the spread of infectious diseases on complex networks. We demonstrate the importance of paths in the context of epidemiology for the case of static and temporal networks. As a central result, we introduce the unfolding accessibility method, that allows for the analysis of the path structure of temporal networks. In this thesis, we analyze the impact of two particular attributes of static networks on the properties of their path structure. As a case study, we analyze the properties of a livestock trade network in Germany. This network exhibits a giant component and a modular structure. The main findings here are that networks close to the percolation threshold are likely to show two disjoint risk classes for the nodes and, a modular structure causes a significant delay for disease outbreaks. Furthermore, special emphasis should be placed on the methods introduced in this thesis for the analysis of temporal networks, i.e. systems where the occurrence of edges varies over time. In this work we introduce a novel method to obtain the causal accessibility graph of a temporal network. Moreover, we introduce unfolding accessibility as a novel formalism for the evaluation of shortest path durations in temporal networks. This approach is able to reveal characteristic timescales for the traversal of temporal networks. Knowledge of these timescales is of fundamental importance for the estimation of times needed for the spread of infectious diseases. The accessibility graph of a temporal network can be compared to its aggregated counterpart. Hence we define the causal fidelity, which quantifies the goodness of the static approximation of a temporal network from the causal point of view.

Das globale Klimasystem ist ein ausgesprochen komplexes und hochgradig nichtlineares System mit einer Vielzahl von Einflüssen und Interaktionen zwischen Variablen und Parametern. Komplementär zu der Beschreibung des Systems mit globalen Klimamodellen, kann Klima anhand der Interaktionsstruktur des Gesamtsystems durch Netzwerke beschrieben werden. Statt Details so genau wie möglich zu modellieren, werden hier Zeitreihendaten verwendet um zugrundeliegende Strukturen zu finden. Die Herausforderung liegt dann in der Interpretation dieser Strukturen. Um mich der Frage nach der Interpretation von Netzwerkmaßen zu nähern, suche ich nach einem allgemeinen Zusammenhang zwischen Eigenschaften der Netzwerktopologie und Eigenschaften des zugrundeliegenden physikalischen Systems. Dafür werden im Wesentlichen zwei Methoden entwickelt, die auf der Analyse von Temperaturentwicklungen gemäß der Advektions-Diffusions-Gleichung (ADE) basieren. Für die erste Methode wird die ADE mit offenen Randbedingungen und δ-peak Anfangsbedingungen gelöst. Die resultierenden lokalen Temperaturprofile werden verwendet um eine Korrelationsfunktion und damit ein Netzwerk zu definieren. Diese Netzwerke werden analysiert und mit Klimanetzen aus Daten verglichen. Die zweite Methode basiert auf der Diskretisierung der stochastischen ADE. Die resultierende lineare, stochastische Rekursionsgleichung wird verwendet um eine Korrelationsmatrix zu definieren, die nur von der Übergangsmatrix und der Varianz des stochastischen Störungsterms abhängt. Ich konstruiere gewichtete und ungewichtete Netzwerke für vier verschiedene Fälle und schlage Netzwerkmaße vor, die zwischen diesen Systemen zu unterscheiden helfen, wenn nur das Netzwerk und die Knotenpositionen gegeben sind. Die präsentierten Rekonstruktionsmethoden generieren Netzwerke, die konzeptionell und strukturell Klimanetzwerken ähneln und können somit als "proof of concept" der Methode der Klimanetzwerke, sowie als Interpretationshilfe betrachtet werden. / The earth’s climate is an extraordinarily complex, highly non-linear system with a multitude of influences and interactions between a very large number of variables and parameters. Complementary to the description of the system using global climate models, in recent years, a description based on the system’s interaction structure has been developed. Rather than modelling the system in as much detail as possible, here time series data is used to identify underlying large scale structures. The challenge then lies in the interpretation of these structures. In this thesis I approach the question of the interpretation of network measures from a general perspective, in order to derive a correspondence between properties of the network topology and properties of the underlying physical system. To this end I develop two methods of network construction from a velocity field, using the advection-diffusion-equation (ADE) for temperature-dissipation in the system. For the first method, the ADE is solved for δ-peak-shaped initial and open boundary conditions. The resulting local temperature profiles are used to define a correlation function and thereby a network. Those networks are analysed and compared to climate networks from data. Despite the simplicity of the model, it captures some of the most salient features of climate networks. The second network construction method relies on a discretisation of the ADE with a stochastic term. I construct weighted and unweighted networks for four different cases and suggest network measures, that can be used to distinguish between the different systems, based on the topology of the network and the node locations. The reconstruction methods presented in this thesis successfully model many features, found in climate networks from well-understood physical mechanisms. This can be regarded as a justification of the use of climate networks, as well as a tool for their interpretation.

Eine almost Einstein-Struktur (M,g,sigma) ist eine n-dimensionale zusammenhängende Mannigfaltigkeit M mit einer pseudo-riemannschen Metrik g und einer glatten Skalenfunktion sigma deren almost Einstein-Tensor A[g,sigma] (der spurfreie Anteil von Hess[g] sigma + sigma P[g], wobei P[g] den Schouten-Tensor bezeichnet) verschwindet. Sie verallgemeinert die Idee einer Einsteinmannigfaltigkeit in dem Sinne, dass die konform geänderte Metrik 1/sigma^2 g außerhalb der Nullstellenmenge Sigma = sigma^(-1)(0) eine Einstein-Metrik ist. Ziel dieser Doktorarbeit ist es, ein detailiertes Bild von Sigma in Lorentzsignatur (-+...+) zu erhalten. Teil dieser Arbeit ist zudem eine indexfreie Darstellung ausgewählter Resultate für konform kompaktifizierbare Einsteinmannigfaltigkeiten in Lorentzsignatur im Rahmen von almost Einstein-Strukturen. Diese Umformulierung wird dann benutzt, um eine Verallgemeinerung der konformen Wellengleichungen für beliebige gerade Dimensionen n = 2m > 4 vorzuschlagen. / An almost Einstein structure (M,g,sigma) is an n-dimensional connected manifold M equipped with a pseudo-Riemannian metric g and a scale factor sigma in C^infty(M) such that the almost Einstein tensor A[g,sigma] (the trace-free part of Hess[g] sigma + sigma P[g], with Schouten tensor P[g]) vanishes. It generalises the idea of an Einstein manifold in the way that 1/sigma^2 g is an Einstein metric away from the singularity set Sigma = sigma^(-1)(0). The purpose of this thesis is to get a detailed picture of Sigma in Lorentzian signature (-+...+). Part of this thesis is also an index-free survey of selected results on conformally compact Einstein manifolds in Lorentzian signature in the framework of almost Einstein structures. This reformulation is used to suggest a generalisation of the conformal wave equations to arbitrary even dimensions n = 2m > 4.

Viele Probleme der Kombinatorik, Zahlentheorie, Wahrscheinlichkeitstheorie, Zuverlässigkeitstheorie und Statistik lassen sich durch Anwendung einer einheitlichen Methode lösen, die als Prinzip der Inklusion-Exklusion bekannt ist. Das Prinzip der Inklusion-Exklusion drückt die Indikatorfunktion einer Vereinigung endlich vieler Ereignisse als alternierende Summe der Indikatorfunktionen ihrer Durchschnitte aus. Die vorliegende Schrift befasst sich mit verbesserten Inklusions-Exklusions-Identitäten und verbesserten Bonferroni-Ungleichungen, die voraussetzen, dass die Ereignisfamilie gewissen strukturellen Anforderungen genügt. Solche wohl-strukturierten Ereignisfamilien finden sich u.a. in der schließenden Statistik, der kombinatorischen Zuverlässigkeitstheorie und der chromatischen Graphentheorie. / Many problems in combinatorics, number theory, probability theory , reliability theory and statistics can be solved by applying a unifying method, which is known as the principle of inclusion-exclusion. The principle of inclusion-exclusion expresses the indicator function of a union of finitely many events as an alternating sum of indicator functions of their intersections. This thesis deals with improved inclusion-exclusion identities and improved Bonferroni inequalities that require the family of events to satisfy some structural restrictions. Examples of such well-structured families arise in problems of statistical inference, combinatorial reliability theory and chromatic graph theory.

In dieser Arbeit wird zuerst das Theorem von Chung, Graham und Wilson über quasi-zufällige Graphen zur sogenannten schwachen Quasi-Zufälligkeit für k-uniforme Hypergraphen verallgemeinert und somit eine Reihe äquivalenter Eigenschaften bestimmt. Basierend auf diesen Resultaten werden nichtbipartite Graphen gefunden, welche die Quasi-Zufälligkeit für Graphen ``forcieren''''. Zuvor waren nur bipartite Graphen mit dieser Eigenschaft bekannt. Desweiteren ist ein konzeptionell einfacher Algorithmus zum Verifizieren nicht erfüllbarer zufälliger k-SAT Formeln angegeben. Dann richtet sich der Fokus auf Anwendungen verschiedener Regularitätslemmata für Hypergraphen. Zuerst wird die Menge aller bezeichneten 3-uniformen Hypergraphen auf n Knoten, die keine Kopie des Hypergraphen der Fano Ebene enthalten, studiert. Es wird gezeigt, dass fast jedes Element aus dieser Menge ein bipartiter Hypergraph ist. Dies führt zu einem Algorithmus, der in polynomiell erwarteter Zeit einen zufälligen Fano-freien (und somit einen zufälligen bipartiten 3-uniformen) Hypergraphen richtig färbt. Schließlich wird die folgende extremale Funktion studiert. Es sind r Farben gegeben sowie ein k-uniformer Hypergraph F. Auf wie viele verschiedene Arten kann man die Kanten eines k-uniformen Hypergraphen H färben, so dass keine monochromatische Kopie von F entsteht? Welche Hypergraphen H maximieren die Anzahl erlaubter Kantenfärbungen? Hier wird ein strukturelles Resultat für eine natürliche Klasse von Hypergraphen bewiesen. Es wird für viele Hypergraphen F, deren extremaler Hypergraph bekannt ist, gezeigt, dass im Falle von zwei oder drei Farben die extremalen Hypergraphen die oben beschriebene Funktion maximieren, während für vier oder mehr Farben andere Hypergraphen mehr Kantenfärbungen zulassen. / This thesis presents first one possible generalization of the result of Chung, Graham and Wilson to k-uniform hypergraphs, and studies the so-called weak quasi-randomness. As applications we obtain a simple strong refutation algorithm for random sparse k-SAT formulas and we identify first non-bipartite forcing pairs for quasi-random graphs. Our focus then shifts from the study of quasi-random objects to applications of different versions of the hypergraph regularity lemmas; all these versions assert decompositions of hypergraphs into constantly many quasi-random parts, where the meaning of ``quasi-random'''' takes different contexts in different situations. We study the family of hypergraphs not containing the hypergraph of the Fano plane as a subhypergraph, and show that almost all members of this family are bipartite. As a consequence an algorithm for coloring bipartite 3-uniform hypergraphs with average polynomial running time is given. Then the following combinatorial extremal problem is considered. Suppose one is given r colors and a fixed hypergraph F. The question is: In at most how many ways can one color the hyperedges of a hypergraph H on n vertices such that no monochromatic copy of F is created? What are the extremal hypergraphs for this function? Here a structural result for a natural family of hypergraphs F is proven. For some special classes of hypergraphs we show that their extremal hypergraphs (for large n) maximize the number of edge colorings for 2 and 3 colors, while for at least 4 colors other hypergraphs are optimal.