Genau wie Borges’ Bibliothekar, der in den Meilen sinnloser Kakophonien, sprachlichen Kauderwelschs, zusammenhanglosen Zeugs von aus 25 orthografischen Symbolen zufällig zusammengestellten Kombinationen in den physisch normierten Büchern einer zyklisch und periodisch gedachten Bibliothek nach Sinn sucht, bewegt sich ein Musiker beim Komponieren auch in einem endlichen System von Kombinationsmöglichkeiten musikalischer Zeichen. Jede Menge an Tönen, sei sie durch die Schranken des Tonraums von Γ–ee oder die Hörgrenzen des Rezipienten definiert, ist endlich, wodurch die Anzahl der einzelnen Kombinationsmöglichkeiten dieser Klänge an sich – und durch einen zugrundeliegenden Regelkanon verschärft – beschränkt ist. Was negativ als Einschränkung gedeutet werden könnte, wurde als Chance zur vollständigen Darstellung kompositorischer Handlungsoptionen in Kompositionslehren genutzt. Auf der Grundlage des endlichen Systems an Kombinationsmöglichkeiten wurden Modelle entwickelt, die einen im Sinne des zugrundeliegenden Regelkanons richtigen Satz garantieren. Im Hinblick auf die Vermittlung endlicher Kombinationsmöglichkeiten scheint dabei die Evolution von der Idee einer ›Tavola del Contrapunto‹ über die Lehre von Intervallklassen über bestimmten Solmisationsstufen im Bass zur Oktavregel nur folgerichtig und die Entwicklung einer Generalbass-Maschine bzw. die Aussage, dass eine Vielzahl von Kompositionen, die an verschiedenen Orten Europas von unterschiedlichen Personen komponiert wurden, sich in Hinblick auf die ›Modulation‹ genau glichen, nur konsequent. / Similar to Borges’ librarian, who searches for meaning in the miles of meaningless cacophonies, linguistic gibberish and incoherent stuff that consists of 25 randomly combined orthographic symbols within the physically normed books of a library thought to be cyclic and periodic, a musician also moves inside a finite system of possible combinations of musical characters during the act of composing. Every quantity of tones – no matter if defined by the barriers of tonal space from Γ to ee or by the recipient’s auditory threshold – is finite. Hence, the amount of individual possible combinations of these tones – additionally tightened by an underlying canon of rules – is also limited. What could be negatively interpreted as a limitation was rather understood as a chance for an exposition of all possible compositional actions within contemporary treatises. Ultimately, models were developed that were built upon this concept of a finite system of possible combinations and ensured a correct composition in terms of an underlying canon of rules. Regarding the finite possibilities of combinations, the evolution starting with the idea of a »Tavola del Contrapunto« via the doctrine of classes of intervals above particular steps of solmization to the rule of the octave seems to be logical. The development of a »thorough-bass-machine« or the statement that a multitude of compositions, composed in different places in Europe by different people, resemble each other exactly with regard to their »modulation« is only consequent.

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.

Dyson-Schwinger-Gleichungen sind Fixpunktgleichungen, die in der Quantenfeldtheorie auftauchen. Obwohl es bekannt ist, wie die Kombinatorik vor der Anwendung von Feynman-Regeln aussieht, war die Kombinatorik der resultierenden analytischen Dyson-Schwinger-Gleichungen bisher unbekannt. Wir verallgemeinern die Arbeiten von Yeats et.al. auf diesem Gebiet zu einer Klasse von unendlich vielen Dyson-Schwinger-Gleichungen mit Hilfe von Sehnen-Diagrammen. / In quantum field theory, Dyson-Schwinger equations are fixed-point equations that come from self insertion properties of Feynman graphs. While the combinatorics of these are well understood, the combinatorics are still mysterious after applying the Feynman rules. We generalize the work of Yeats et.al. in this field to an infinite number of Dyson-Schwinger equations with the help of chord diagrams.

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.

My thesis is mostly concerned with algebraic and combinatorial aspects of the theory of hyperplane arrangements. More specifically, I study the Orlik-Terao algebra of a hyperplane arrangement and the broken circuit complex of a matroid. The Orlik-Terao algebra is a useful tool for studying hyperplane arrangements, especially for characterizing some non-combinatorial properties. The broken circuit complex, on the one hand, is closely related to the Orlik-Terao algebra, and on the other hand, plays a crucial role in the study of many combinatorial problem: the coefficients of the characteristic polynomial of a matroid are encoded in the f-vector of the broken circuit complex of the matroid. Among main results of the thesis are characterizations of the complete intersection and Gorenstein properties of the broken circuit complex and the Orlik-Terao algebra. I also study the h-vector of the broken circuit complex of a series-parallel network and relate certain entries of that vector to ear decompositions of the network. An application of the Orlik-Terao algebra in studying the relation space of a hyperplane arrangement is also included in the thesis.

The quadratic traveling salesman problem (QTSP) is an extension of the (classical) Traveling Salesman Problem (TSP) where the costs depend on each two nodes that are traversed in succession, i. e., on the edges in the symmetric (STSP) and on the arcs in the asymmetric case (ATSP). The QTSP is motivated by an application in bioinformatics. It can be used in the solution of certain Permuted Markov models that are set up for the recognition of transcription factor binding sites and of splice sites in gene regulation. Important special cases are the Angular-Metric TSP used in robotics and the TSP with Reload Costs used in the planning of telecommunication and transport networks. The SQTSP and the AQTSP can be formulated as integer optimization problems over the polytope associated with the STSP resp. ATSP together with a quadratic cost function. We study the polytopes arising from a linearization of the respective quadratic integer programming formulations. Based on the proof of the dimension of the polytopes using the so called direct method we can prove the facetness of several valid inequalities. These facets and valid inequalities can be divided into three large groups. Some are related to the Boolean quadric polytope. Furthermore we introduce the conflicting edges/arc inequalities that forbid certain configurations of edges and 2-edges resp. of arcs and 2-arcs. Finally, we strengthen valid inequalities of STSP and ATSP in order to get stronger inequalities in the quadratic case. We present two general lifting approaches. One is applicable to all inequalities with nonnegative coefficients and the second allows to strengthen clique tree inequalities. Applying these approaches to the subtour elimination constraints leads to facets in most cases, but in general facetness is not preserved. In addition, the complexity of the separation problems for some of the facet classes is studied. Finally, we present some computational results using a branch-and-cut framework, which is improved by some of the newly derived cutting planes. The tested instances from biology could be solved surprisingly well. Instances with up to 100 nodes could be solved in less than 700 seconds improving the results in the literature by several orders of magnitude. For most of the randomly generated instances using some additional separators allowed to reduce the root gaps and the numbers of nodes in the branch-and-cut tree significantly, often even the running times.

In this thesis, we study the following three types of periodic string patterns and some of their variants. Firstly, we consider maximal d-repetitions. These are substrings that are at least 2+d times as long as their minimum period. Secondly, we consider 3-cadences. These are arithmetic subsequence of three equal characters. Lastly, we consider maximal pairs. These are pairs of identical substrings. Maximal d-repetitions and maximal pairs of uncompressed strings are already well-researched. However, no non-trivial upper bound for distinct occurrences of these patterns that take the compressed size of the underlying strings into account were known prior to this research. We provide upper bounds for several variants of these two patterns that depend on the compressed size of the string, the logarithm of the string's length, the highest allowed power and d. These results also lead to upper bounds and new insights for the compacted directed acyclic word graph and the run-length encoded Burrows-Wheeler transform. We prove that cadences with three elements can be efficiently counted in uncompressed strings and can even be efficiently detected on grammar-compressed binary strings. We also show that even slightly more difficult variants of this problem are already NP-hard on compressed strings. Along the way, we extend the underlying geometry of the convolution from rectangles to arbitrary polygons. We also prove that this non-rectangular convolution can still be efficiently computed.:1 Introduction 2 Preliminaries 3 Non-Rectangular Convolution 4 Alphabet Reduction 39 5 Maximal (Sub-)Repetitions 6 Cadences 7 Maximal Pairs A Propositions

Diese Dissertation befasst sich mit Fragen über den Modulraum M_{0,n} der stabilen punktierten rationalen Kurven, die durch das Mori-Programm motiviert sind. Insbesondere studieren wir den nef-Kegel (Chapter 2), den Cox-Ring (Chapter 3), und den Kegel der beweglichen Kurven (Chapter 4). In Kapitel 2 beweisen wir Fultons Vermutung für M_{0,n}, n / We investigate questions motivated by Mori''s program for the moduli space of stable pointed rational curves, M_{0,n}. In particular, we study its nef cone (Chapter 2), its Cox ring (Chapter 3), and its cone of movable curves (Chapter 4). In Chapter 2, we prove Fulton''s conjecture for M_{0,n} for n less than or equal to 7, which states that any divisor on these moduli spaces non-negatively intersecting all so-called F-curves is linearly equivalent to an effective sum of boundary divisors. As a corollary, it follows that a divisor is nef if and only if the divisor intersects all F-curves non-negatively. By duality, we thus recover Keel and McKernan''s result that the F-curves generate the closed cone of curves when n is less than or equal to seven, but with methods that do not rely on negativity properties of the canonical bundle that fail for higher n. Chapter 3 initiates a study of relations among generators of the Cox ring of M_{0,n}. We first prove a `relation-free'' result that exhibits polynomial subrings of the Cox ring in boundary section variables. In the opposite direction, we exhibit multidegrees such that the corresponding graded parts meet the ideal of relations non-trivially. In Chapter 4, we study the so-called complete intersection cone for the three-fold M_{0,6}. For a smooth projective variety X, this cone is defined as the closure of curve classes obtained as intersections of the dimension of X minus one very ample divisors. The complete intersection cone is contained in the cone of movable curves, which is dual to the cone of pseudoeffective divisors. We show that, for a series of toric birational models for M_{0,6}, the complete intersection and movable cones coincide, while for M_{0,6}, there is strict containment.

Inspired by Happel's question, whether the exchange graph and the simplicial complex of tilting modules over a quiver algebra are independent from the multiplicities of multiple arrows in the quiver, we study quantitative aspects of Fomin and Zelevinsky's quiver mutation rule. Our results turn out to be very useful in the mutation-infinite case for understanding combinatorial structures as the cluster exchange graph or the simplicial complex of tilting modules, which are governed by quiver mutation. Using a class of quivers we call forks we can show that any such quiver yields a tree in the exchange graph. This allows us to provide a good global description of the exchange graphs of arbitrary mutation-infinite quivers. In particular we show that the exchange graph of an acyclic quiver is a tree if (and in fact only if) any two vertices are connected by at least two arrows. Furthermore we give classification results for the simplicial complexes and thereby obtain a partial positive answer to Happel's question. Another consequence of our findings is a confirmation of Unger's conjecture about the infinite number of components of the tilting exchange graph in all but finitely many cases. Finally we generalise and conceptualise our results by introducing what we call "polynomial quivers", stating several conjectures about "polynomial quiver mutation", and giving proofs in special cases.

This thesis concerns two topics. The first topic, that is related to the Dedekind-Mertens Lemma, the notion of the so-called content algebra, is discussed in chapter 2. Let $R$ be a commutative ring with identity and $M$ be a unitary $R$-module and $c$ the function from $M$ to the ideals of $R$ defined by $c(x) = \cap \lbrace I \colon I \text{~is an ideal of~} R \text{~and~} x \in IM \rbrace $. $M$ is said to be a \textit{content} $R$-module if $x \in c(x)M $, for all $x \in M$. The $R$-algebra $B$ is called a \textit{content} $R$-algebra, if it is a faithfully flat and content $R$-module and it satisfies the Dedekind-Mertens content formula. In chapter 2, it is proved that in content extensions, minimal primes extend to minimal primes, and zero-divisors of a content algebra over a ring which has Property (A) or whose set of zero-divisors is a finite union of prime ideals are discussed. The preservation of diameter of zero-divisor graph under content extensions is also examined. Gaussian and Armendariz algebras and localization of content algebras at the multiplicatively closed set $S^ \prime = \lbrace f \in B \colon c(f) = R \rbrace$ are considered as well. In chapter 3, the second topic of the thesis, that is about the grade of the zero-divisor modules, is discussed. Let $R$ be a commutative ring, $I$ a finitely generated ideal of $R$, and $M$ a zero-divisor $R$-module. It is shown that the $M$-grade of $I$ defined by the Koszul complex is consistent with the definition of $M$-grade of $I$ defined by the length of maximal $M$-sequences in I$. Chapter 1 is a preliminarily chapter and dedicated to the introduction of content modules and also locally Nakayama modules.