Mathematics - Theses, Dissertations, and other Required Graduate Degree Essays

Receive updates for this collection

Genome rearrangement problems accounting for duplicate genes

Author: 
Date created: 
2018-08-10
Abstract: 

We investigate certain genome rearrangement problems studied in relation to genome evolution. We introduce the SCJ-TD-FD rearrangement model to explain the directed evolution from an ancestor A to a descendant D, where D may contain multiple copies of genes from A. We study the pairwise genome distance problem that aims at finding the most parsimonious sequence of cuts, joins and single-gene duplications that transforms A to D, under this model. Next, we study the rooted median problem under the SCJ-TD-FD model, for which the problem is shown to be NP-hard. We provide an Integer Linear Program that, on simulated data, predicts an optimal median with high accuracy. Finally, we study the Small Parsimony Problem under the SCJ-TD-FD model that aims at finding the gene orders at the internal nodes of a given species tree. We define an ILP-based approach to reconstruct the ancestral gene orders and present our experiments on a data-set of Anopheles mosquito genomes.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Cedric Chauve
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Domain decomposition solvers and preconditioners for the implicit closest point method

Author: 
Date created: 
2018-07-17
Abstract: 

The numerical treatment of surface intrinsic elliptic PDE presents several interesting chal-lenges over those posed on flat space. The implicit closest point method, (iCPM) is an embedding method well suited to these problems, and allows the treatment of general sur-faces, S. An extension operator brings surface bound information into the embedding space, to be constant in the surface normal direction, and allows the solution of the problem by standard methods. The positive Helmholtz equation, (c − △S ) u = f, is considered with ten-sor product barycentric Lagrange interpolation defining the extension operator and stan-dard second-order centered di˙erences for the ambient Laplacian. Under this scheme, a non-symmetric system with poor sparsity is obtained, which reduces the performance of iterative solvers and motivates the development of specialized solvers. Optimized restricted additive Schwarz (ORAS) methods are well suited to this task and are formulated for these problems. The interesting geometry of the problem presents challenges for the construction of subdomains as well as the enforcement of Robin boundary conditions. The developed solvers perform well over a range of test problems with the optimized methods providing a distinct advantage. With Krylov acceleration, convergence is obtained rapidly with dimin-ished di˙erence between the optimized and non-optimized methods.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Steven Ruuth
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Efficient periodic graph traversal on graphs with a given rotation system

Author: 
Date created: 
2018-08-22
Abstract: 

We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The problem is to design an automaton A and a port labeling scheme L such that A (using L) performs on any undirected graph an infinite walk that periodically visit all vertices. The goal is to minimize the revisit time of any vertex over all graphs (traversal period) π. If the labeling scheme L is given by an adversary, it has been shown by Budach [6] that no such finite automaton A exists. If L does not need to be a permutation at every vertex, one can easily encode a spanning tree and A can perform traversal with period 2n − 2 even it is an oblivious agent. The problem is difficult when L is limited to be a permutation. The best known upper bound on the traversal period in such a case is 3.5n−2 by Czyzowicz et al. [11], where n is the number of vertices. It is an open problem whether it is possible to achieve traversal period of 2n − 2. In this thesis, we answer this question affirmatively under the assumption that the input graph G is given with a rotation system, where a rotation system, where a rotation system of a graph is given by lists of local orders of edges incident to each vertex the graph.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ladislav Stacho
Jan Manuch
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

2-Regular Digraphs on Surfaces

Author: 
Date created: 
2018-08-06
Abstract: 

A 2-regular digraph is one where every vertex has in-degree and out-degree 2. This thesis focuses on surface embeddings of 2-regular digraphs, one where the underlying graph is embedded in a surface and all faces are bounded by directed closed walks. Immersion acts as a natural minor-like containment relation for embedded 2-regular digraphs and this theory is linked to undirected graph minors by way of the directed medial graph. We parallel the theory of undirected graphs in surfaces by proving analogues of Whitney's Theorem and Tutte's peripheral cycles theorem for 2-regular digraphs in the sphere. Then, using a notion of branch-width and a 2-regular digraph grid theorem by Johnson, we prove that for each fixed surface S, the 2-regular digraphs embeddable in S are characterized by a finite list of immersion obstructions. We then present the current state of the art with regard to classification of obstructions for surfaces: Johnson characterized the sphere obstructions, we classify all projective plane obstructions, and we have a computer assisted partial list of obstructions for the torus and Klein bottle. We also consider two open problems in the world of undirected graphs on surfaces and resolve their analogues in the world of 2-regular digraphs on surfaces. The first conjecture by Negami we resolve in the affirmative, that a 2-regular digraph has a finite planar cover if and only if it is projective planar. The second, the strong embedding conjecture, is resolved in the negative and we provide an infinite family of well connected counter-examples.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Matt DeVos
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Aspects of the Arithmetic of Uniquely Trigonal Genus Four Curves: Arithmetic Invariant Theory and Class Groups of Cubic Number Fields

Author: 
Peer reviewed: 
No, item is not peer reviewed.
Date created: 
2018-11-01
Abstract: 

In this thesis, we study the family of uniquely trigonal genus 4 curves via their connection to del Pezzo surfaces of degree 1. We consider two different aspects of these curves. First, we show how to construct any uniquely trigonal genus 4 curve whose Jacobian variety has fully rational 2-torsion and whose trigonal morphism has a prescribed totally ramified fibre. Using this construction, we find an infinite family of cubic number fields whose class group has 2-rank at least 8. We also consider genus 4 curves that are superelliptic of degree 3, and prove sharp results on the size of the 2-torsion subgroup of their Jacobian varieties over the rationals. Our second result is a contribution to arithmetic invariant theory. We consider the moduli space of uniquely trigonal genus 4 curves whose trigonal morphism has a marked ramification point, originally studied by Coble, from a modern perspective.We then show under a technical hypothesis how to construct an assignment from the rational points on the Jacobian variety of such a curve to a fixed orbit space that is independent of the curve. The assignment is compatible with base extensions of the field, and over an algebraically closed field our assignment reduces to the assignment of a marked (in the aforementioned sense) uniquely trigonal genus 4 curve to its moduli point. The orbit space is constructed from the split algebraic group of type E8.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Nils Bruin
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Connectedness of Certain Random Graphs

Peer reviewed: 
No, item is not peer reviewed.
Date created: 
1973
Document type: 
Thesis
File(s): 
Senior supervisor: 
T. Brown
Department: 
Simon Fraser University. Theses (Dept. of Mathematics)
Thesis type: 
Thesis (M.Sc.)

The genus of generalized random and quasirandom graphs

Author: 
Date created: 
2018-06-12
Abstract: 

The genus of a graph $G$ is the minimum integer $h$ such that $G$ has an embedding in some surface (closed compact 2-manifold) $S_h$ of genus $h$. In this thesis, we will discuss the genus of generalized random and quasirandom graphs. First, by developing a general notion of random graphs, we determine the genus of generalized random graphs. Next, we approximate the genus of dense generalized quasirandom graphs. Based on analysis of minimum genus embeddings of quasirandom graphs, we provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. More precisely, we provide an algorithm that for a given (dense) graph $G$ of order $n$ and given $\varepsilon>0$, returns an integer $g$ such that $G$ has an embedding into a surface of genus $g$, and this is $\varepsilon$-close to a minimum genus embedding in the sense that the minimum genus $\g(G)$ of $G$ satisfies: $\g(G)\le g\le (1+\varepsilon)\g(G)$. The running time of the algorithm is $O(f(\varepsilon) n^2)$, where $f(\cdot)$ is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) of genus $g$. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time $O(f_1(\varepsilon)\,n^2)$. The last part of the thesis studies the genus of complete $3$-uniform hypergraphs, which is a special case of genus of random bipartite graphs, and also a natural generalization of Ringel--Youngs Theorem. Embeddings of a hypergraph $H$ are defined as the embeddings of its associated Levi graph $L_H$ with vertex set $V(H)\cup E(H)$, in which $v\in V(H)$ and $e\in E(H)$ are adjacent if and only if $v$ and $e$ are incident in $H$. The construction in the proof may be of independent interest as a design-type problem.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Bojan Mohar
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Parameter estimation and uncertainty quantification applied to advection-diffusion problems arising in atmospheric source inversion

Date created: 
2018-04-10
Abstract: 

In this thesis we present a method to obtain an efficient algorithm to perform parameter estimation with uncertainty quantification of mathematical models that are complex and computationally expensive. We achieve this with a combination of emulation of the mathematical model using Gaussian processes and Bayesian statistics and inversion for the parameter estimation and uncertainty quantification. In particular we apply these ideas to a source inversion problem in atmospheric dispersion. We explain the theory and ideas behind each relevant part of the process in the emulation and parameter estimation. The concepts and methodology presented in this work are general and can be applied to a wide range of problems where it is necessary to estimate parameters but the underlying mathematical model is expensive, rendering more classical approaches unfeasible. To validate the concepts used, we perform a parameter estimation study in a model that is relatively cheap to compute and whose parameter values are known in advance. Finally we perform a parameter estimation withuncertainty quantification of a much more expensive atmospheric dispersion model using real data from a lead-zinc smelter in Trail, British Columbia. The parameter estimation includes approximating high-dimensional integrals with Markov chain Monte Carlo methods and solving the source inversion problem in atmospheric dispersion using the Bayesian framework.

Document type: 
Thesis
File(s): 
Senior supervisor: 
John Stockie
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

On the Nikolaevskiy equation and the fractal dimension of its attractor

Author: 
Date created: 
2018-04-23
Abstract: 

We investigate the attractor of the Nikolaevskiy equation, a sixth-order partial differential equation (PDE) containing a small parameter whose solutions exhibit spatiotemporal chaos with strong scale separation. We first prove well-posedness and regularity of the solutions, and derive asymptotic bounds on their derivatives, to put the subsequent results on a firm footing. The rest of the work focuses on showing that the dynamical system associated with the Nikolaevskiy equation possesses an attractor with a finite fractal dimension. Bounds on this dimension are both derived analytically and computed numerically, paying particular attention to their scaling with the parameters. We describe the numerical methods, and present computational results that include the scaling of various norms of the solutions, as well as of the power spectrum and the spectrum of Lyapunov exponents of the PDE.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Ralf Wittenberg
Weiran Sun
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

The unrestricted linear fractional assignment problem

Author: 
Date created: 
2018-04-20
Abstract: 

The linear fractional assignment problem (LFAP) is a well-studied combinatorial optimization problem with various applications. It attempts to minimize ratio of two linear functions subject to standard assignment constraints. When the denominator of the objective function is positive, LFAP is solvable in polynomial time. However, when the denominator of the objective function is allowed to take positive and negative values, LFAP is known to be NP-hard. In this thesis, we present two 0-1 programming formulations of LFAP and compare their relative merits using experimental analysis. We also show that LFAP can be solved as a polynomialy bounded sequence of constrained assignment problems. Experimental results using this methodology are also given. Finally, some local search heuristics are developed and analyzed their efficiency using systematic experimental analysis. Our algorithms are able to solve reasonably large size problems within acceptable computational time.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Abraham Punnen
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.