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

Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3. The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove an asymptotic minimum degree condition for an arbitrary bipartite graph G to be tiled by another arbitrary bipartite graph H. This proves a conjecture of Zhao and also implies an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.

Bacteriophages (viruses that infect bacteria) are the most abundant biological life-forms on Earth. However, very little is known regarding the structure of phage-bacteria infections. In a recent study we showed that phage-bacteria infection assay datasets are statistically nested in small scale communities while modularity is not statistically present. We predicted that at large macroevolutionary scales, phage-bacteria infection assay datasets should be typified by a modular structure, even if there is nested structure at smaller scales. We evaluate and confirm this hypothesis using the largest study of the kind to date. The study in question represents a phage-bacteria infection assay dataset in the Atlantic Ocean region between the European continental shelf and the Sargasso Sea. We present here a digitized version of this study that consist of a bipartite network with 286 bacteria and 215 phages including 1332 positive interactions, together with an exhaustive structural analysis of this network. We evaluated the modularity and nestedness of the network and its communities using a variety of algorithms including BRIM (Bipartite, Recursively Induced Modules), NTC (Nestedness Temperature Calculator) and NODF (Nestedness Metric based on Overlap and Decreasing Filling). We also developed extensions of these standard methods to identify multi-scale structure in large phage-bacteria interaction datasets. In addition, we performed an analysis of the degree of geographical diversity and specialization among all the hosts and phages. We find that the largest-scale ocean dataset study, as anticipated by Flores et al. 2013, is highly modular and not significantly nested (computed in comparison to null models). More importantly is the fact that some of the communities extracted from Moebus and Nattkemper dataset were found to be nested. We examine the role of geography in driving these modular patterns and find evidence that phage-bacteria interactions can exhibit strong similarity despite large distances between sites. We discuss how models can help determine how coevolutionary dynamics between strains, within a site and across sites, drives the emergence of nested, modular and other complex phage-bacteria interaction networks. Finally, we releases a computational library (BiMAT)to help to help the ecology research community to perform bipartite network analysis of the same nature I did during my PhD.

Orientadore: Amir Ordacgi Caldeira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Física Gleb Wataghin / Made available in DSpace on 2018-08-19T10:34:18Z (GMT). No. of bitstreams: 1 DuarteMunoz_OscarSalomon_D.pdf: 2976449 bytes, checksum: 637bc7ead779ce89597e095cc7f2470c (MD5) Previous issue date: 2011 / Resumo: Usamos o modelo "sistema-mais-reservatório" para estudar a dinâmica quântica de um sistema de duas partículas imersas em um reservatório em equilíbrio térmico. Analisamos as consequências, para o caso de duas partículas, de usarmos uma extensão direta do modelo usado para uma partícula. Em particular, enfatizamos que uma modelagem adequada do contratermo é fundamental para obtermos a dinâmica apropriada no limite clássico. Usamos uma extensão do banho de osciladores capaz de induzir um acoplamento efetivo entre as partículas brownianas dependendo da escolha feita para a função espectral dos osciladores que compõem o banho. O acoplamento é não - linear nas variáveis de interesse e impomos uma dependência exponencial nestas variáveis para garantir a invariância translacional do modelo. A dinâmica quântica é estudada através do operador densidade reduzido das duas partículas. Obtivemos a evolução do operador densidade para dois sistemas de interesse: o primeiro deles é formado por duas partículas livres preparadas em um estado inicial gaussiano e o segundo é formado por dois osciladores harmônicos preparados inicialmente em um estado não gaussiano formado pela superposição de pacotes de onda gaussianos. A in uência do ambiente foi observada através da evolução do emaranhamento. Nosso modelo fornece um critério de distância para identicar em que casos um ambiente comum pode induzir emaranhamento. Três regimes foram encontrados: o regime de distâncias curtas, equivalente ao encontrado no modelo sistema-mais-reservatório com acoplamento bilinear, o regime de distâncias longas em que as partículas atuam como se estivessem acopladas com reservatórios independentes, e o regime de distâncias intermediárias em que existe uma competição entre os efeitos de decoerência e indução de emaranhamento / Abstract: We use the system-plus-reservoir model to study the dynamics of a system of two particles that interact with a heat bath in thermal equilibrium. We analyze the effects, for the two particle case, of a direct generalization of the usual model for one brownian particle. We particularly call for attention to the fundamental role of the counterterm in order to obtain the proper dynamics in the classical limit. We use an extension of the bath of oscillators capable of inducing an effective coupling between the brownian particles depending on the choice made to the spectral function of the oscillators components of the bath. The coupling is non-linear in the variables of interest and an exponential dependence is imposed in order to guarantee the translational invariance of the model. The quantum dynamics is studied through the reduce density operator of the two particles. We obtain the evolution of the reduce density operator for two systems of interest: the first one is composed by two free particles initially prepared in a gaussian state and the second one is composed by two harmonic oscillators prepared initially in a non-gaussian state formed by superposition of gaussian packets. The environment in uence is observed through the evolution of entanglement. Our model provides a criterion of distance for identifying in which cases a common environment can induce entanglement. Three regimes are found: the short distance regime, equivalent to a bilinear system-reservoir coupling, the long distance regime in which the particles act like coupled to independent reservoirs and the intermediate regime suitable for the coexistence between decoherence and induced-entanglement / Doutorado / Física / Doutor em Ciências

In their recent paper ``Edge-transitive products," Hammack, Imrich, and Klavzar showed that the direct product of connected, non-bipartite graphs is edge-transitive if and only if both factors are edge-transitive, and at least one is arc-transitive. However, little is known when the product is bipartite. This thesis extends this result (in part) for the case of bipartite graphs using a new technique called "stacking." For R-thin, connected, bipartite graphs A and B, we show that A x B is arc-transitive if and only if A and B are both arc-transitive. Further, we show A x B is edge-transitive only if at least one of A, B is also edge-transitive, and give evidence that strongly suggests that in fact both factors must be edge-transitive.

abstract: Models using feature interactions have been applied successfully in many areas such as biomedical analysis, recommender systems. The popularity of using feature interactions mainly lies in (1) they are able to capture the nonlinearity of the data compared with linear effects and (2) they enjoy great interpretability. In this thesis, I propose a series of formulations using feature interactions for real world problems and develop efficient algorithms for solving them. Specifically, I first propose to directly solve the non-convex formulation of the weak hierarchical Lasso which imposes weak hierarchy on individual features and interactions but can only be approximately solved by a convex relaxation in existing studies. I further propose to use the non-convex weak hierarchical Lasso formulation for hypothesis testing on the interaction features with hierarchical assumptions. Secondly, I propose a type of bi-linear models that take advantage of interactions of features for drug discovery problems where specific drug-drug pairs or drug-disease pairs are of interest. These models are learned by maximizing the number of positive data pairs that rank above the average score of unlabeled data pairs. Then I generalize the method to the case of using the top-ranked unlabeled data pairs for representative construction and derive an efficient algorithm for the extended formulation. Last but not least, motivated by a special form of bi-linear models, I propose a framework that enables simultaneously subgrouping data points and building specific models on the subgroups for learning on massive and heterogeneous datasets. Experiments on synthetic and real datasets are conducted to demonstrate the effectiveness or efficiency of the proposed methods. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2018

<p>This thesis consists of two papers.</p><p>The first paper is a study of the structure of the k-assignment polytope, whose vertices are the <em>m x n</em> (0; 1)-matrices with exactly <em>k</em> 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. Two equivalent representations of the faces are given, one as (0; 1)-matrices and one as ear decompositions of bipartite graphs. These tools are used to describe properties of the polytope, especially a complete description of the cover relation in the face lattice of the polytope and an exact expression for the diameter.</p><p>The second paper studies the edge-product space <em>Є(X)</em> for trees on <em>X</em>. This space is generated by the set of edge-weighted finite trees on <em>X</em>, and arises by multiplying the weights of edges on paths in trees. These spaces are closely connected to tree-indexed Markov processes in molecular evolutionary biology. It is known that <em>Є(X)</em> has a natural <em>CW</em>-complex structure, and a combinatorial description of the associated face poset exists which is a poset <em>S(X)</em> of <em>X</em>-forests. In this paper it is shown that the edge-product space is a regular cell complex. One important part in showing that is to conclude that all intervals <em>[Ô, Г], Г </em>Є<em> S(X),</em> have recursive coatom orderings.</p> / Report code: LiU-TEK-LIC-2004:46.

<p>Large scale geometric data is ubiquitous. In this dissertation, we design algorithms and data structures to process large scale geometric data efficiently. We design algorithms for some fundamental geometric optimization problems that arise in motion planning, machine learning and computer vision.</p><p>For a stream S of n points in d-dimensional space, we develop (single-pass) streaming algorithms for maintaining extent measures such as the minimum enclosing ball and diameter. Our streaming algorithms have a work space that is polynomial in d and sub-linear in n. For problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses polynomial in d space. On the positive side, we design a summary called the blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent</p><p>of n.</p><p>For a set P of k pairwise-disjoint convex obstacles in 3-dimensions, we design algorithms and data structures for computing Euclidean shortest path between source s and destination t. The running time of our algorithm is linear in n and the size and query time of our data structure is independent of n. We follow a summary based approach, i.e., quickly compute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q.</p><p>For d-dimensional point sets A and B, |A| |B| n, and for a parameter &epsilon > 0,</p><p>We give an algorithm to compute &epsilon-approximate minimum weight perfect matching of A and B under d(. , .) in time O(n<super>1.5</super>&tau(n)) ; here &tau(n) is the query/update time of a dynamic weighted nearest neighbor under d(. , .). When A, B are point sets from</p><p>a bounded integer grid, for L₁ and L_infinity-norms, our algorithm computes minimum weight</p><p>perfect matching of A and B in time O(n<super>1.5</super>). Our algorithm also extends to a generalization of matching called the transportation problem.</p><p>We also present an O(n polylog n ) time algorithm that computes under any L_p-</p><p>norm, an &epsilon-approximate minimum weight perfect matching of A and B with high probability; all previous algorithms take </p><p>O(n<super>1.5</super> time. We approximate the L_p norm using a distance function, based on a randomly shifted quad-tree. The algorithm iteratively generates an approximate minimum-cost augmenting path under the new distance function in</p><p>time proportional to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O(n log n) implying a near-linear running time.</p><p>All the problems mentioned above have a history of more than two decades and algorithms presented here improve previous work by an order of magnitude. Many of these improvements are obtained by new geometric techniques that might have broader applications</p><p>and are of independent interest.</p> / Dissertation

No description available.

The minimum degree spanning tree problem is a widely studied NP-hard variation of the minimum spanning tree problem, and a generalization of the Hamiltonian path problem. Most of the work done on the minimum degree spanning tree problem has been on approximation algorithms, and very little work has been done studying graph classes where this problem may be polynomial time solvable. The Hamiltonian path problem has been widely studied on graph classes, and we use classes with polynomial time results for the Hamiltonian path problem as a starting point for graph class results for the minimum degree spanning tree problem. We show the minimum degree spanning tree problem is polynomial time solvable for chain graphs. We then show this problem is polynomial time solvable on bipartite permutation graphs, and that there exist minimum degree spanning trees of these graphs that are caterpillars, and that have other particular structural properties.