Graph polynomials are polynomials associated to graphs that encode the number of subgraphs with given properties. We list different frameworks used to define graph polynomials in the literature. We present the edge elimination polynomial and introduce several graph polynomials equivalent to it. Thereby, we connect a recursive definition to the counting of colorings and to the counting of (spanning) subgraphs. Furthermore, we define a graph polynomial that not only generalizes the mentioned, but also many of the well-known graph polynomials, including the Potts model, the matching polynomial, the trivariate chromatic polynomial and the subgraph component polynomial. We proof a recurrence relation for this graph polynomial using edge and vertex operation. The definitions and statements are given in such a way that most of them are also valid in the case of hypergraphs.

Techn. University, Diss., 2007--Darmstadt.

Techn. University, Diss., 2002--Darmstadt.

In this thesis, we undertake a combinatorial study of certain aspects of triangulations of cartesian products of simplices, particularly in relation to their relevance in toric algebra and to their underlying product structure. The first chapter reports joint work with Samu Potka. The object of study is a class of homogeneous toric ideals called cut ideals of graphs, that were introduced by Sturmfels and Sullivant 2006. Apart from their inherent appeal to combinatorial commutative algebra, these ideals also generalize graph statistical models for binary data and are related to some statistical models for phylogenetic trees. Specifically, we consider minimal free resolutions for the cut ideals of trees. We propose a method to combinatorially estimate the Betti numbers of the ideals in this class. Using this method, we derive upper bounds for some of the Betti numbers, given by formulas exponential in the number of vertices of the tree. Our method is based on a common technique in commutative algebra whereby arbitrary homogeneous ideals are deformed to initial monomial ideals, which are easier to analyze while conserving some of the information of the original ideals. The cut ideal of a tree on n vertices turns out to be isomorphic to the Segre product of the cut ideals of its n-1 edges (in particular, its algebraic properties do not depend on its shape). We exploit this product structure to deform the cut ideal of a tree to an initial monomial ideal with a simple combinatorial description: it coincides with the edge ideal of the incomparability graph of the power set of the edges of the tree. The vertices of the incomparability graph are subsets of the edges of the tree, and two subsets form an edge whenever they are incomparable. In order to obtain algebraic information about these edge ideals, we apply an idea introduced by Dochtermann and Engström in 2009 that consists in regarding the edge ideal of a graph as the (monomial) Stanley-Reisner ideal of the independence complex of the graph. Using Hochster\''s formula for computting Betti numbers of Stanley-Reisner ideals by means of simplicial homology, the computation of the Betti numbers of these monomial ideals is turned to the enumeration of induced subgraphs of the incomparability graph. That the resulting values give upper bounds for the Betti numbers of the cut ideals of trees is an important well-known result in commutative algebra. In the second chapter, we focus on some combinatorial features of triangulations of the point configuration obtained as the cartesian product of two standard simplices. These were explored in collaboration with César Ceballos and Arnau Padrol, and had a two-fold motivation. On the one hand, we intended to understand the influence of the product structure on the set of triangulations of the cartesian product of two point configurations; on the other hand, the set of all triangulations of the product of two simplices is an intricate and interesting object that has attracted attention both in discrete geometry and in other fields of mathematics such as commutative algebra, algebraic geometry, enumerative geometry or tropical geometry. Our approach to both objectives is to examine the circumstances under which a triangulation of the polyhedral complex given by the the product of an (n-1)-simplex times the (k-1)-skeleton of a (d-1)-simplex extends to a triangulation of an (n-1)-simplex times a (d-1)-simplex. We refer to the former as a partial triangulation of the product of two simplices. Our main result says that if d >= k > n, a partial triangulation always extends to a uniquely determined triangulation of the product of two simplices. A somewhat unexpected interpretation of this result is as a finiteness statement: it asserts that if d is sufficiently larger than n, then all partial triangulations are uniquely determined by the (compatible) triangulations of its faces of the form “(n-1)-simplex times n-simplex”. Consequently, one can say that in this situation ‘\''triangulations of an (n-1)-simplex times a (d-1)-simplex are not much more complicated than triangulations of an (n-1)-simplex times an n-simplex\''\''. The uniqueness assertion of our main result holds already when d>=k>=n. However, the same is not true for the existence assertion; namely, there are non extendable triangulations of an (n-1)-simplex times the boundary of an n-simplex that we explicitly construct. A key ingredient towards this construction is a triangulation of the product of two (n-1)-simplices that can be seen as its ``second simplest triangulation\''\'' (the simplest being its staircase triangulation). It seems to be knew, and we call it the Dyck path triangulation. This triangulation displays symmetry under the cyclic group of order n that acts by simultaneously cycling the indices of the points in both factors of the product. Next, we exhibit a natural extension of the Dyck path triangulation to a triangulation of an (n-1)-simplex times an n-simplex that, in a sense, enjoys some sort of ‘\''rigidity\''\'' (it also seems new). Performing a ‘\''local modification\''\'' on the restriction of this extended triangulation to the polyhedral complex given by (n-1)-simplex times the boundary of an n-simplex yields the non-extendable partial triangulation. The thesis includes two appendices on basic commutative algebra and triangulations of point configuration, included to make it slightly self-contained.

This thesis deals with the exact solution of large-scale minimum bisection problems via a semidefinite relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope a study of new facet-defining inequalities is presented. They are derived from the known knapsack tree inequalities. We investigate strengthenings based on the new cluster weight polytope and present polynomial separation algorithms for special cases. The dual of the semidefinite relaxation of the minimum bisection problem is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Implementational details regarding primal heuristics, branching rules, so-called support extensions for cutting planes and warm start are presented. We conclude with a computational study in which we show that our approach is competetive to state-of-the-art implementations using linear programming or semidefinite programming relaxations. / Diese Dissertation befasst sich mit der exakten Lösung großer Minimum Bisection Probleme über eine semidefinite Relaxierung in einem Branch-and-Cut Zugang. Nachdem bekannte Resultate zum zugrundeliegenden Bisection Cut Polytop dargestellt wurden, wird eine Studie neuer facettendefinierender Ungleichungen präsentiert. Diese werden von den bekannten Knapsack Tree Ungleichungen abgeleitet. Wir untersuchen Verstärkungen basierend auf dem neuen Cluster Weight Polytop und zeigen polynomiale Separierungsalgorithmen für Spezialfälle. Die Duale der semidefiniten Relaxierung des Minumum Bisection Problems wird in ihrer äquivalenten Form als Eigenwertoptimierungsproblem mit dem Spektralen Bündelverfahren bearbeitet. Details der Implementierung bezüglich primaler Heuristiken, Branchingregeln, sogenannter Supporterweiterungen für die Schnittebenen und Warmstart werden präsentiert. Wir beenden die Arbeit mit einer numerischen Studie, in der wir zeigen, dass unser Zugang konkurrenzfähig zu aktuellen Implementationen basierend auf linearen und semidefiniten Relaxierungen ist.

In dieser Arbeit wird ein durch eine passive Matrix angesteuertes Sensorarray vorgestellt. Das Sensorarray besteht aus zwei parallel zueinander angeordneten Leiterplatten mit jeweils vier Leiterbahnen, die als Arbeits- und Gegenelektroden verwendet werden. Die Leiterbahnen kreuzen sich in einem Winkel von 90°, wobei an jedem Kreuzungspunkt ein Sensorelement gebildet wird. Ein selektives Auslesen der Sensorelemente wird durch eine mechanische oder auf Kapillarkräften basierenden Unterteilung des Elektrolyten sowie eine spezielle elektrotechnische Auslesemethode erreicht. Durch die Verwendung einer aus Preußisch Blau bestehenden kombinierten Gegen- und Referenzelektrode können in dem Zwei Elektrodensystem Bedingungen, die denen eines Drei Elektrodensystems sehr nahe kommen, realisiert werden.Mit diesem einfach aufzubauenden Sensorarray konnte die Lücke zwischen den, in der Größe limitierten Sensoren mit Einzeladressierung und den wesentlich aufwändigeren, aber eine hohe Packungsdichte aufweisenden CMOS Sensoren geschlossen werden. Die Funktionalität dieses Sensorarrays wurde anhand von zwei unterschiedlichen Anwendungsbeispielen aus dem Bereich der Kombinatorischen Chemie unter Beweis gestellt.

Durch parallele SPOT-Synthese wurden trisamino- und amino-oxo-substituierte [1,3,5]-Triazine auf Zellulose- und Polypropylenmembranen dargestellt. Neben der Entwicklung geeigneter Linkerstrategien und dem Einsatz von Aminen und Phenolaten als Bausteine konnte eine Mikrowellenbestrahlung für die Substitution an den membrangebundenen Monochlor-[1,3,5]-triazinen nutzbar gemacht werden. Der Einsatz von gasförmiger TFA zur Abspaltung der Syntheseprodukte von den planaren Oberflächen erlaubte den Erhalt der örtlichen Adressierbarkeit der Verbindungen für Analyse und Screening. Zusätzlich wurde ein neues Konzept für die Synthese von makrocyclischen Peptidmimetika entwickelt. Diese Methode bedient sich der sequenziellen SNAr-Reaktion von ursprünglich orthogonal geschützten Aminogruppen eines Peptides und anderer linearer Oligomere an halogenierten Heteroaromaten wie 2,4,6-Trichloro-[1,3,5]-triazin, 2,4,6-Trichloropyrimidin, 4,6-Dichloro-5-nitropyrimidin und 2,6,8-Trichloro-7-methyl-7H-purin. Die Möglichkeiten dieses neuen Zugangs zu Makrocyclen wurde systematisch mittels SPOT-Synthese untersucht. So wurden Fragen wie zugängliche Ringgrössen, Kompatibilität mit Aminosäuren, Cyclisierungsrichtungen und Verwendung von unterschiedlichen linearen Oligomeren adressiert. Es stellte sich heraus, dass eine Reihe von Peptidmimetika mit unterschiedlichen Ringgrössen (11- bis 37-gliedrige Ringe) und verschiedenen chemischen Strukturen des Rückgrades erhalten werden können. Die erhaltenden [1,3,5]-Triazin-Bibliotheken wurden sowohl in einem Festphasen-Screening als auch in einem Assay in Lösung eingesetzt. Es gelang, de novo Bindungspartner für den monoklonalen Antikörper TAB-2 aus einer Bibliothek aus 8000-zellulosegebundenen [1,3,5]-Triazinen zu finden und neuartige cyclische Peptid-Triazinderivate als Agonisten für einen Somatostatinrezeptor zu entwickeln. / Effective spatially addressed parallel assembly of trisamino- and amino-oxy-1,3,5-triazines was achieved by applying the SPOT-synthesis technique on cellulose and polypropylene membranes. In addition to developing a suitable linker strategy and employing amines and phenolate ions as building blocks, a highly effective microwave assisted nucleophilic substitution procedure at membrane-bound monochlorotriazines was developed. The 1,3,5-triazines obtained could be cleaved in parallel from the solid support by TFA-vapor to give compounds adsorbed on the membrane surface in a conserved spatially addressed format for analysis and screening. A novel concept for the synthesis of macrocyclic peptidomimetics which incorporate heteroaromatic units was developed. The method involves sequential SNAr reactions of former orthogonally protected amino groups of peptides and other linear oligomers on halo-genated heterocycles such as 2,4,6-trichloro-[1,3,5]-triazine, 2,4,6-trichloropyrimidine, 4,6-dichloro-5-nitropyrimidine and 2,6,8-trichloro-7-methyl-7H-purine. The scope of this novel solid phase approach was systematically evaluated by means of the SPOT-synthesis metho-dology. Besides the question of the accessibility of different ring sizes and the compatibility with protecting groups of commonly used amino acids, cyclization direction and the applicability of the technique towards peptidomimetics was studied. It was found that the procedure is well suited to assemble a wide variety of cyclic peptidomimetics differing in both size (11 to 37-membered rings) and chemical nature of the assembled backbones. The obtained [1,3,5]-triazine libraries were subjected to heterogeneous and homogeneous screening assays. De novo binding partners for the monoclonal antibody Tab2 were detected from a 8000-membered library of cellulose-bound 1,3,5-trazines. In addition novel cyclic peptide-triazine derivatives were identified as agonists for a somatostatin receptor.

No description available.

School of Economics and Political Science, Diss.--London, 2005. / Literaturverz. S. [143] - 145. The work originates from the author's PhD thesis at the London School of Economics and Political Science. (Preface).

Omic science is rapidly growing and one of the most employed techniques to explore differential patterns in omic datasets is principal component analysis (PCA). However, a method to enlighten the network of omic features that mostly contribute to the sample separation obtained by PCA is missing. An alternative is to build correlation networks between univariately-selected significant omic features, but this neglects the multivariate unsupervised feature compression responsible for the PCA sample segregation. Biologists and medical researchers often prefer effective methods that offer an immediate interpretation to complicated algorithms that in principle promise an improvement but in practice are difficult to be applied and interpreted. Here we present PC-corr: a simple algorithm that associates to any PCA segregation a discriminative network of features. Such network can be inspected in search of functional modules useful in the definition of combinatorial and multiscale biomarkers from multifaceted omic data in systems and precision biomedicine. We offer proofs of PC-corr efficacy on lipidomic, metagenomic, developmental genomic, population genetic, cancer promoteromic and cancer stem-cell mechanomic data. Finally, PC-corr is a general functional network inference approach that can be easily adopted for big data exploration in computer science and analysis of complex systems in physics.