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

Receive updates for this collection

Colouring complexes of planar triangulations and the line graphs of cubic graphs

Author: 
Date created: 
2020-08-17
Abstract: 

In order to study the parity of a k-colouring, Tutte introduced the notion of a k-colouring complex in 1969. Given a k-colourable graph X, the k-colouring complex Bk(X) is the graph which has all the independent sets which are colour classes of X as its vertices and two vertices A and B in V (Bk(X)) joined by an edge if the colour classes A and B appear together in a k-colouring of X. Subsequently, Fisk proved that the graph Bk(X) is k-colourable and discovered infinite families of graphs for which Bk(Bk(X)) is isomorphic to X. In this thesis, we resolve a question Tutte posed about the 4-colouring complex at one of his final public lectures in 1999. He asked whether the 4-colouring complex of a planar triangulation could have two components in which all colourings have the same parity. In response, we construct triangulations of the plane whose 4-colouring complexes have arbitrarily many even and odd components. Furthermore, we exhibit an infinite family of 4-connected triangulations of the plane whose 4-colouring complexes have an arbitrarily large number of even components, as well as a number of 5-connected triangulations of the plane whose 4-colouring complexes have at least two components in which all colourings have the same parity. In the later chapters of this thesis, we continue our study of the k-colouring complex, discovering many new infinite families of graphs X for which Bk(Bk(X)) is isomorphic to X. We call these graphs reflexive graphs. Most notably, if G is a 3-edge-colourable, connected, cubic (possibly including half-edges) outerplanar graph, we prove that L(G) is reflexive if and only if G is triangle-free. In order to establish this result, we show how to reduce questions about the reflexivity of a connected graph to questions about the reflexivity of its 2-edge-connected components. Then we determine conditions under which subdividing an edge preserves reflexivity. These two novel theorems are of independent interest. In particular, we apply the latter theorem to prove that theta graphs have reflexive line graphs.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Bojan Mohar
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Toric degenerations of rational curves of degree n+2 in P^n

Author: 
Date created: 
2020-08-11
Abstract: 

A common technique for studying a projective variety relies on finding a flat degeneration to a toric variety, which is a variety described by combinatorial data. However, it is not clear in general how to find such a degeneration or even if one exists. Ilten and Wrobel have shown that a very general rational plane curve of degree at least four does not admit this degeneration. In this thesis, we investigate the existence of toric degenerations for the special case of projective rational curves of degree n+2 in P^n where n≥3. Using work of Buczyński, Ilten, and Ventura, we obtain explicit parametrizations for all rational curves of degree n+2 in P^n and characterize which of these admit such a degeneration. Our results show that for these curves, the problem of having a toric degeneration can be decided algorithmically.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Nathan Ilten
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Safe coverage of compact domains for second order dynamical systems

Author: 
Date created: 
2020-08-07
Abstract: 

Autonomous systems operating in close proximity with each other to cover a specified area has many potential applications, but coordination and safety are two fundamental challenges. For coordination, we propose a locally asymptotically stable distributed coverage controller for moving compact domains for two types of vehicles with second order dynamics (double integrator and fixed-wing aircraft) with bounded input forces. This control policy is based on artificial potentials and consensus forces designed to promote desired vehicle-domain and inter-vehicle separations and relative velocities. We prove that certain coverage configurations are locally asymptotically stable. For safety, we establish minimal energy conditions for collision free motion and we utilize Hamilton-Jacobi (HJ) reachability theory for pairwise collision avoidance. Rather than computing numerical solutions of the associated HJ partial differential equation, we derive an analytical solution for the double integrator vehicle. We demonstrate our approach in several numerical simulations involving convex and non-convex moving domains.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Razvan Fetecau
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Algebraic hyperbolicity for surfaces in smooth complete toric threefolds with Picard rank 2 and 3

Author: 
Date created: 
2020-08-11
Abstract: 

Algebraic hyperbolicity serves as a bridge between differential geometry and algebraic geometry. Generally, it is difficult to show that a given projective variety is algebraically hyperbolic. However, it was established recently that a very general surface of degree at least five in projective space is algebraically hyperbolic. In this thesis, we are interested in generalizing the study of surfaces in projective space to surfaces in toric threefolds with Picard rank 2 or 3. Towards this goal, we explored the combinatorial description of toric threefolds with Picard rank 2 and 3 by following the works of Kleinschmidt and Batyrev. Then we used the method of finding algebraically hyperbolic surfaces in toric threefolds by Haase and Ilten. As a result, we were able to determine several algebraically hyperbolic surfaces in each of these varieties.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Nathan Ilten
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Weighted l1 minimization techniques for compressed sensing and their applications

Author: 
Date created: 
2020-04-17
Abstract: 

Compressed sensing (CS) provides effective techniques for the recovery of a sparse vector from a small number of measurements by finding a solution to an underdetermined linear system. In recent years, CS has attracted substantial attention in applied mathematics, computer science and electrical engineering, and it has the potential to improve many applications, such as medical imaging and function approximation. One standard technique for solving the CS problem is l1 minimization; however, the performance of l1 minimization might be limited for many practical applications. Hence, in the past few years, there are many investigations into how to modify the l1 minimization approach so that better performance can be achieved. One such approach is weighted l1 minimization. In this thesis, we extend the weighted l1 minimization technique, traditionally used to solve the standard CS problem, to other applications. First, we develop a variance-based joint sparse (VBJS) algorithm based on weighted l1 minimization to solve the multiple measurement vector (MMV) problem. Unlike the standard l2,1 minimization method for this problem, the VBJS method is easily parallelizable. Moreover, we observe through various numerical experiments that the VBJS method often uses fewer measurements to reach the same accuracy as the l2,1 minimization method. Second, we apply weighted l1 minimization to the high-dimensional function approximation problem, focusing on the case of gradient-augmented measurements. The high-dimensional function approximation problem has many applications, including uncertainty quantification (UQ), where it arises in the task of approximating a quantity of interest (QoI) of a parametric differential equation (DE). For a fixed amount of computational cost, we see in various examples that, with additional gradient information, better approximation results are often achieved compared to non-gradient augmented sampling. Theoretically, we prove that, with the same sample complexity as the case of function samples only, the gradient-augmented problem gives a better error bound in a stronger Sobolev norm as opposed to an L2 norm. Finally, we use the adjoint sensitivity analysis method to compute the gradient information. As we show, this method computes the gradient samples of the QoI of a parametric DE with around the same computational cost as computing the samples of the QoI itself. We apply this approach to several parametric DE problems, and numerically demonstrate the benefits of incorporating gradient information into the approximation procedure.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Ben Adcock
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Lattice walks in cones: Combinatorial and probabilistic aspects

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

Lattice walks in cones have many applications in combinatorics and probability theory. While walks restricted to the first quadrant have been well studied, the case of non-convex cones and three-dimensional walks has been systematically approached recently. In this thesis, we extend the analytic method of the study of walks and its discrete harmonic functions in the quarter plane to the three-quarter plane applying the strategy of splitting the domain into two symmetric convex cones. This method is composed of three main steps: write a system of functional equations satisfied by the generating function, which may be simplified into one single equation under symmetry conditions; transform the functional equation into a boundary value problem; and solve this problem using conformal mappings. We obtain explicit expressions for the generating functions of walks and its associated harmonic functions. The advantage of this method is the uniform treatment of models corresponding to different step sets. In a second part of this thesis, we explore the asymptotic enumeration of three-dimensional excursions confined to the positive octant. The critical exponent is related to the smallest eigenvalue of a Dirichlet problem in a spherical triangle. Combinatorial properties of the step set are related to geometric and analytic properties of the associate spherical triangle.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Marni Mishna
Kilian Raschel
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Neural style transfer with primitive features

Author: 
Date created: 
2019-11-21
Abstract: 

Neural Style Transfer (NST) is an algorithm that creates an image by combining the stylistic features of a piece of artwork with the content features of a photograph. The defining characteristic of NST which sets it apart from other image stylization techniques is the use of Deep Neural Networks trained for image recognition. First derived in 2016 by Leon Gatys and Matthias Bethge, the algorithm uses a single neural network to extract and recombine the content of one image with the artistic style of another. Now a field unto itself, NST has shown an uncanny ability to produce approximations to human artistic style. However, the exact process in which style is represented in the model is highly unintuitive and is still not well understood. Moreover, there is little reasoning given towards the choice of network architecture, size or training environment. This leads to questions like: can any network designed for image recognition preform NST? Will the network's depth or training set have an affect on NST? To explore these questions this thesis presents several experiments on Neural Style Transfer using networks that have been trained on small image recognition tasks. In this simplified setting we assess various aspects of the NST algorithm with these primitive networks. The results of our experiments show that certain architectures do not have the capacity for NST while other networks can produce NST-like results but suffer in visual quality.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Paul Tupper
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Cops and robbers with speed restrictions

Date created: 
2019-09-24
Abstract: 

The game of Cops and Robbers is a pursuit-evasion game played on graphs with two players, the cops and the robber, who take turns moving on the graph. In each turn, they may move to a vertex adjacent to their current position or stay where they are. The cops’ objective is to get to the same position where the robber is, which we refer to as to capture the robber, and the robber’s goal is to evade capture indefinitely. The basic question is to find the minimum number of cops that can guarantee capturing the robber in a given graph. A very fruitful research area has been developed around the idea of modifying the way in which the cops or the robber move and analysing how these changes affect the strategies and outcome of the game. In this thesis we will study the game when we impose additional speed restrictions on the players, variants of the game popularly known as “lazy-cops and robbers” and “active cops and robbers”. In order to do so, we introduce the concept of the wide shadow, aiming to improve known results and obtain new tools and techniques which may provide further insight into other open problems in the area.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Bojan Mohar
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

A new bivariate Hensel lifting algorithm for n factors

Author: 
Date created: 
2019-08-13
Abstract: 

We present a new algorithm for performing Linear Hensel Lifting of bivariate polynomials over the finite field F_p for some prime p. Our algorithm lifts n monic, univariate polynomials to recover the factors of a polynomial A(x,y) in F_p[x,y] which is monic in x, and bounded by degrees d_x = deg(A,x) and d_y = deg(A,y). Our algorithm improves upon Bernardin's algorithm in [2] and reduces the number of arithmetic operations in F_p from O(n d_x^2 d_y^2) to O(d_x^2 d_y + d_x d_y^2) for p >= d_x. Experimental results in C verify that our algorithm compares favorably with Bernardin's for large degree polynomials.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Michael Monagan
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Computation of mountain wave clouds in a moist Boussinesq fluid model

Author: 
Date created: 
2019-08-07
Abstract: 

This thesis presents computations of time-steady 2D clouds forming over mountain topography, with an interest in resolving the fine-scale physics at the cloud edge. The underlying model takes the incompressible Euler equations as its basis, and couples the atmospheric fluid flows to the physics of phase change in order to compute cloud-edge boundary locations in a vertically-stratified atmosphere. This coupling gives rise to a free-boundary problem for the cloud edge. This model has been employed here to successfully recover mountain cloud behaviour for a variety of atmospheric conditions, including computations of the well-known lens shape of the lenticular cloud. The problem of time-steady, density-stratified flow over ground topography can be reduced to a 2D Helmholtz problem for the streamfunction due to Long's theory. The domain of this PDE is a perturbed 2D half-space, and the streamfunction is specified by a bottom boundary that follows a localized mountain terrain. This thesis presents a new extension of Long's theory to include cloudy air, where the derived Helmholtz equation now includes localized forcing associated with small regions of cloud. The nature of the PDE domain makes the problem well-suited for a boundary method application. The scheme used in this work utilizes the method of fundamental solutions (MFS), a numerical approach related to the boundary integral equation method, which approximates the solutions to elliptic problems by finite sums of fundamental solutions of the PDE operator. The MFS is coupled with an iterative solver to resolve the free-boundary problem for the cloud geometry, and the numerical performance of this scheme is analyzed.

Document type: 
Thesis
File(s): 
Supervisor(s): 
David Muraki
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.