In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. A representation for an even cut matroid is a pair formed by a graph together with a special set of vertices of the graph. Such a pair is called a graft. We show that two signed graphs representing the same even cycle matroid relate to two grafts representing the same even cut matroid. We then present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that any two representations of the same even cycle matroid are either in one of these two classes, or are related by a local modification of a known operation, or form a sporadic example. The second problem we consider is finding the excluded minors for these classes of matroids. A difficulty when looking for excluded minors for these classes arises from the fact that in general the matroids may have an arbitrarily large number of representations. We define degenerate even cycle and even cut matroids. We show that a 3-connected even cycle matroid containing a 3-connected non-degenerate minor has, up to a simple equivalence relation, at most twice as many representations as the minor. We strengthen this result for a particular class of non-degenerate even cycle matroids. We also prove analogous results for even cut matroids.

Thesis (Ph. D.)--State University of New York at Binghamton, Department of Mathematical Sciences, 2008. / Includes bibliographical references.

Thesis (Ph. D.)--State University of New York at Binghamton, Department of Mathematical Sciences, 2005. / Includes bibliographical references.

The hypertoric variety M_A defined by an arrangement A of affine hyperplanes admits a natural tropicalization, induced by its embedding in a Lawrence toric variety. In this thesis, we explicitly describe the polyhedral structure of this tropicalization and calculate the fibers of the tropicalization map. Using a recent result of Gubler, Rabinoff, and Werner, we prove that there is a continuous section of the tropicalization map.

The approach to a theory of non-finitary matroids, as outlined by the author in [20], is here extended to the case in which the relevant closure operators are defined on arbitrary complete Boolean algebras, rather than on the power sets of sets. As a preliminary to this study, the theory of derivatives of operators on complete Boolean algebras is developed and the notion, having interest in its own right, of an analytic closure operator is introduced . The class of B-matroidal closure operators is singled out for especial attention and it is proved that this class is closed under Whitney duality. Also investigated is the class of those closure operators which are both matroidal and topological. / Thesis / Doctor of Philosophy (PhD)

Notre étude se concentre sur les techniques qui offrent un support automatique pour l'adaptation et la révision des modèles dynamiques. <br />L'objectif est d'étudier comment l'outil bond graph peut aider à concevoir des systèmes innovants répondant à un cahier des charges exprimé en termes de comportement temporel ou fréquentiel.<br />Construire un modèle revient toujours à faire une abstraction du système initial. Faire une abstraction du système à modéliser signifie trouver les propriétés les plus pertinentes pour la tâche à résoudre. Pour un modélisateur peu expérimenté c'est une étape difficile, car s'il n'a pas fait les bons choix son modèle se montrera faux, étant trop grossier ou trop simple. <br />Avec notre approche, l'intention est d'indiquer une autre capacité de la méthodologie bond graph, celle d'un outil de reconstruction, qui pourrait suggérer des solutions dans le cas d'un dispositif inconsistant avec les spécifications. <br />Comme applications nous décrirons un instrument médical avec un problème fréquentiel observé après la phase de construction et un actionneur électro-hydrostatique dont on n'a pas modélisé un mécanisme physique qui influençait son comportement dynamique. On démontrera que l'outil de reconstruction présenté peut suggérer aux designers peu expérimentés des modifications à apporter aux modèles d'ordres insuffisants.<br />Nous désirons aussi que le système proposé dans cette étude puisse être utilisé comme outil dans la phase de conception des dispositifs technologiques soumis à un cahier des charges. En vue de la conception nous proposons un algorithme qui permet de retrouver les solutions proposées par les ingénieurs et si c'est possible des modèles alternatifs.<br />L'algorithme sera adapté au domaine des matériaux viscoélastiques pour obtenir, à partir des données expérimentales, tous les modèles qui correspondent à un matériau identifié.<br />Nous traiterons aussi le cas d'un nouveau concept pour un capteur de vitesse très sensible aux spécifications fréquentielles. Notre système est capable de proposer plusieurs architectures qui aideront l'ingénieur à choisir celle qui lui convient le mieux vis-à-vis de son cahier des charges.<br />Parce que les bond graphs permettent une représentation unifiée des systèmes physiques, à partir des modèles proposés, nous pouvons choisir des implémentations technologiques dans des domaine physiques différents.

Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices covered by a matching in the associated graph. The branching matrix, a representation of a directed graph, has rank equal to the maximum number of vertices covered by a branching in the associated graph. A mixed graph has both undirected and directed edges, and the matching forest problem for mixed graphs, introduced by Giles, is a generalization of the matching problem and the branching problem. A mixed graph can be represented by the matching forest matrix, and the rank of the matching forest matrix is related to the size of a matching forest in the associated mixed graph. The Tutte matrix and the branching matrix have indeterminate entries, and we describe algorithms that evaluate the indeterminates as rationals in such a way that the rank of the evaluated matrix is equal to the rank of the indeterminate matrix. Matroids in the context of graphs are discussed, and matroid formulations for the matching, branching, and matching forest problems are given.

We summarize and present recent results in the field of infinite matroid theory. We define and prove basic properties of infinite matroids and we discuss known classes of examples of these structures. We focus on the topic of connectivity of infinite matroids and we link some matroid properties to connectivity. The main result of this work is the proof of existence of infinite matroids with arbitrary finite connectivity, but without finite circuits or cocircuits. Powered by TCPDF (www.tcpdf.org)

We consider the computational complexity of evaluating the Tutte polynomial of three particular classes of greedoid, namely rooted graphs, rooted digraphs and binary greedoids. Furthermore we construct polynomial-time algorithms to evaluate the Tutte polynomial of these classes of greedoid when they're of bounded tree-width. We also construct a Möbius function formulation for the characteristic polynomial of a rooted graph and determine the computational complexity of computing the coefficients of the Tutte polynomial of a rooted graph.

Designing self-assembling DNA nanostructures often requires the identification of a route for a scaffolding strand of DNA through the target structure. When the target structure is modeled as a graph, these scaffolding routes correspond to Eulerian circuits subject to turning restrictions imposed by physical constraints on the strands of DNA. Existence of such Eulerian circuits is an NP-hard problem, which can be approached by adapting solutions to a version of the Traveling Salesperson Problem. However, the author and collaborators have demonstrated that even Eulerian circuits obeying these turning restrictions are not necessarily feasible as scaffolding routes by giving examples of nontrivially knotted circuits which cannot be traced by the unknotted scaffolding strand. Often, targets of DNA nanostructure self-assembly are modeled as graphs embedded on surfaces in space. In this case, Eulerian circuits obeying the turning restrictions correspond to A-trails, circuits which turn immediately left or right at each vertex. In any graph embedded on the sphere, all A-trails are unknotted regardless of the embedding of the sphere in space. We show that this does not hold in general for graphs on the torus. However, we show this property does hold for checkerboard-colorable graphs on the torus, that is, those graphs whose faces can be properly 2-colored, and provide a partial converse to this result. As a consequence, we characterize (with one exceptional family) regular triangulations of the torus containing unknotted A-trails. By developing a theory of sums of A-trails, we lift constructions from the torus to arbitrary n-tori, and by generalizing our work on A-trails to smooth circuit decompositions, we construct all torus links and certain sums of torus links from circuit decompositions of rectangular torus grids. Graphs embedded on surfaces are equivalent to ribbon graphs, which are particularly well-suited to modeling DNA nanostructures, as their boundary components correspond to strands of DNA and their twisted ribbons correspond to double-helices. Every ribbon graph has a corresponding delta-matroid, a combinatorial object encoding the structure of the ribbon-graph's spanning quasi-trees (substructures having exactly one boundary component). We show that interlacement with respect to quasi-trees can be generalized to delta-matroids, and use the resulting structure on delta-matroids to provide feasible-set expansions for a family of delta-matroid polynomials, both recovering well-known expansions of this type (such as the spanning-tree expansion of the Tutte polynnomial) as well as providing several previously unknown expansions. Among these are expansions for the transition polynomial, a version of which has been used to study DNA nanostructure self-assembly, and the interlace polynomial, which solves a problem in DNA recombination.