In 1972, professor Grigore Moisil, the most famous Romanian academician for Mathematics, said about Combinatorics, that it is “an opportunity of a renewed gladness”, because “each problem in the domain asks for its solving, an expenditure without any economy of the human intelligence”. More, the research methods, used in Combinatorics, are different from a problem to the other! This is the explanation for the existence of my actual paper, in which I propose to teach Combinatorics, using selected problems. MS classification: 05A05, 97D50.

The rapid developments in the field of DNA computing reflects two substantial questions: 1. Which models for DNA based computation are really universal? 2. Which model fulfills the requirements to a universal lab-practicable programmable DNA computer that is based on one of these models? This paper introduces the functional model DNA-HASKELL focussing its lab-practicability. This aim could be reached by specifying the DNA based operations in accordiance to an analysis of molecular biological processes. The specification is determined by an abstraction level that includes nucleotides and strand end labels like 5'-phosphate. Our model is able to describe DNA algorithms for any NP-complete problem - here exemplified by the knapsacik problem - as well as it is able to simulate some established mathematical models for computation. We point out the splicing operation as an example. The computational completeness of DNA-HASKELL can be supposed. This paper is based on discussions about the potenzial and limits of DNA computing, in particular the practicability of a universal DNA computer.

In 1972, professor Grigore Moisil, the most famous Romanian academician for Mathematics, said about Combinatorics, that it is “an opportunity of a renewed gladness”, because “each problem in the domain asks for its solving, an expenditure without any economy of the human intelligence”. More, the research methods, used in Combinatorics, are different from a problem to the other! This is the explanation for the existence of my actual paper, in which I propose to teach Combinatorics, using selected problems. MS classification: 05A05, 97D50.

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.

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.

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

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.