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

Receive updates for this collection

Game of Cops and Robbers on Eulerian Digraphs

Date created: 
2018-03-23
Abstract: 

Cops and Robbers is a well-known pursuit game played on a graph. There are two players, one controls the cops and the other controls the robber, who take turns moving along edges of the graph. The goal of the cops is to capture the robber, which is accomplished if a cop occupies the same vertex as the robber. The main question is to determine the minimum number of cops that can guarantee the robber’s capture on the given graph. This problem has been widely studied for the case of undirected graphs, but very little attention has been given to finding the cop number of digraphs. In the thesis we focus on this game on Eulerian digraphs, viewed as an extension of the game on undirected graphs. Some preliminary results, which were obtained for the special case of 4-regular quadrangulations of the torus and the Klein bottle, show that there is a possibility to develop rich results in this area.

Document type: 
Thesis
File(s): 
Senior supervisor: 
Bojan Mohar
Luis Goddyn
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Modelling tuberculosis in South Africa

Date created: 
2018-04-16
Abstract: 

Tuberculosis ranks alongside HIV/AIDS as one of the deadliest infectious diseases in the world, killing 1.4 million people in 2015. The World Health Organization and the Stop TB Partnership set targets to achieve a 90% reduction in incidence and a 95% reduction in mortality from the 2015 values by 2035. We investigate the global dynamics of a compartmental system of ordinary differential equations that models tuberculosis. A more detailed model is then calibrated to the HIV negative TB endemic in South Africa and used to evaluate the 2035 reduction targets. Optimal care and control strategies for fixed budgets are also identified. Model projections for South Africa show the mortality targets can be met through combined interventions, however due to relapse and latent progression the incidence targets are unrealistic. To minimize incidence in 20 years, funding should be prioritized into linking drug susceptible cases (over multi-drug resistant cases) onto care.

Document type: 
Thesis
File(s): 
Senior supervisor: 
JF Williams
Alexander Rutherford
Department: 
Science: Mathematics
Thesis type: 
(Thesis) M.Sc.

Spectral differentiation: Integration and inversion

Date created: 
2018-02-08
Abstract: 

Pseudospectral differentiation matrices suffer from large round-off error, and give rise to illconditioned systems used to solve differential equations numerically. This thesis presents two types of matrices designed to precondition these systems and improve robustness towards this round-off error for spectral methods on Chebyshev-Gauss-Lobatto points. The first of these is a generalization of a pseudospectral integration matrix described by Wang et al. [18]. The second uses this integration matrix to construct the matrix representing the inverse operator of the differential equation. Comparison is made between expected and calculated eigenvalues. Both preconditioners are tested on several examples. In many cases, accuracy is improved over the standard methodology by several orders of magnitude. Using these matrices on general sets of points is briefly discussed.

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

On the circuit diameters of polyhedra

Date created: 
2017-12-04
Abstract: 

In this thesis we develop a framework to study the circuit diameters of polyhedra. The circuit diameter is a generalization of the combinatorial (edge) diameter, where walks are permitted to enter the interior of the polyhedron as long as steps are parallel to its circuit directions. Because the circuit diameter is dependent on the specific realization of the polyhedron, many of the techniques used in the edge case do not transfer easily. We reformulate circuit analogues of the Hirsch conjecture, the d-step conjecture, and the non-revisiting conjecture, and recover some of the edge case relationships in the circuit case. To do this we adapt the notion of simplicity to work with circuit diameter, and so we define C-simplicity and wedge-simplicity. Then, we prove the circuit 4-step conjecture, including for unbounded polyhedra, by showing that the original counterexample U4 to the combinatorial analogue satisfies the Hirsch bound in the circuit case, independent of its realization. This was the first known counterexample to Hirsch, and several families of counterexamples are constructed from U4. In particular, the unbounded Hirsch conjecture could still hold in the circuit case. We also use computational methods to study Q4, the bounded counterpart to U4, and give two realizations with different circuit diameters. It remains open whether Q4 is circuit Hirsch-sharp; however, we are able to lower the distance bound for at least one direction between the two far vertices of Q4. Finally, we present some auxiliary results involving representations of polyhedra and circuit calculations.

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

Optimal Allocation of Treatment & Retention Resources for the Vancouver HIV Continuum of Care

Author: 
Date created: 
2017-12-14
Abstract: 

Vancouver’s continuum of HIV care involves testing, clinical assessment, engagement in care, highly active antiretroviral therapy (HAART), treatment support and retention in care. Effective delivery of these services can significantly impact the HIV epidemic, because patients adherent on HAART are essentially non-infectious. This work presents epidemiological modelling and optimization to assess the influence of a pilot project improving HAART access (STOP HIV/AIDS), and to optimize resource allocation among HIV treatment and retention programs for minimizing morbidity, mortality, and new HIV infections. Optimal solutions are obtained for men who have sex with men, injection drug users and female sex workers. The models are systems of ordinary differential equations. Parameters are estimated using data from the British Columbia Centre for Excellence in HIV/AIDS, Vancouver Coastal Health, published sources and expert opinion. The methods developed here are applicable to the optimization of health systems in various contexts and jurisdictions.

Document type: 
Thesis
File(s): 
Senior supervisor: 
JF Williams
Alexander Rutherford
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Double Triangle Descendants of K5

Author: 
Date created: 
2017-12-05
Abstract: 

Feynman diagrams in phi^4 theory can be represented as 4-regular graphs. The Feynman integral, or even the Feynman period, is very hard to calculate. A graph invariant, called the c2-invariant, is conjecturally thought to be equal for two graphs when their periods are equal. Double triangle reduction of 4-regular graphs is known to preserve the c2-invariant. Double triangle descendants of K5 all have a c2-invariant that is a constant -1, and conjecturally, are the only graphs with this c2-invariant. This thesis studies the structure of K5-descendants to gain insight on the c2-invariant, get closer to solving the conjecture, and to study what is an interesting combinatorial operation in its own right. It will be shown that the minimum number of triangles in a descendant is 4. Closed-form generating functions are found for three families of K5-descendants. Two encodings, one for n-zigzags, and a general one for all K5-descendants, are found.

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

Finding beauty in the dissonance: Analysis and applications of Bayesian inverse problems

Author: 
Date created: 
2017-10-27
Abstract: 

Inverse problems – the process of recovering unknown parameters from indirect measurements – are encountered in various areas of science, technology and engineering including image processing, medical imaging, geosciences, astronomy, aeronautics engineering and machine learning. Statistical and probabilistic methods are promising approaches to solving such problems. Of these, the Bayesian methods provide a principled approach to incorporating our existing beliefs about the parameters (the prior model) and randomness in the data. These approaches are at the forefront of extensive current investigation. Overwhelmingly, Gaussian prior models are used in Bayesian inverse problems since they provide mathematically simple and computationally efficient formulations of important inverse problems. Unfortunately, these priors fail to capture a range of important properties including sparsity and natural constraints such as positivity, and so we are motivated to study non-Gaussian priors. In this thesis we provide a systematic study of the theory and applications of Bayesian approaches to inverse problems with non-Gaussian priors. We develop the theory of well-posedness of infinite-dimensional Bayesian inverse problems with convex, heavy-tailed or infinitely divisible prior measures. We also introduce new prior measures that aim to model compressible or sparse parameters. Next, we demonstrate the applications of Bayesian approaches to important inverse problems in industrial applications: the estimation of emission rates of particulate matter, and the estimation of acoustic aberrations in ultrasound treatment. We propose two Bayesian approaches for the problem of estimating the emission rates of particulate matter into the atmosphere from far field measurements of deposition. Next, we present a Bayesian method for estimation of acoustic aberrations in high intensity focused ultrasound treatment of tissue in the brain using magnetic resonance images. The final contribution of this thesis is a systematic construction and convergence analysis of regularizations of the Dirac delta distribution. Point sources arise naturally in many models and we discuss smooth regularizations of these.

Document type: 
Thesis
File(s): 
Senior supervisor: 
John M. Stockie
Nilima Nigam
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Sap flow and heat transport in trees: An asymptotic and numerical study

Date created: 
2017-10-12
Abstract: 

Transport of fluid and heat inside a tree, and the interchange of water and energy between the tree and the environment, are topics that have been and continue to be areas of active research in plant physiology, agriculture and environmental studies. Many models have been proposed to describe the flow of sap inside the tree, and to connect it to the driving transpiration rate, with various levels of complexity, and with different levels of abstraction. Most existing models are 1D models and many only attempt to get numerical results, without much analysis. For our work, we adopt a porous medium model that has been verified experimentally [Chuang et al., Ecological Modelling, 191(3):447-468, 2006]. We generalize this 1D model to a 3D axisymmetric geometry, where flow is transpiration driven and has anisotropic and spatially dependent hydraulic conductivity. Through asymptotic analysis, we derive approximate solutions that produce the axial and radial trunk sap fluxes for a given transpiration function. We validate the analytical solutions using a second order finite difference scheme. Next we use our solution formulas to tackle the inverse problem of determining spatial and temporal components of transpiration given a discrete set measurements of the trunk sap flux. Finally, we compare our results to some experimental data on radial variations of sap flux. As for the heat transport problem, previous work related to trees discuss special cases of the problem, while giving detailed accounts and specific formulas of the boundary conditions, like wind and solar radiation effects. Most of this work does not include the possible effects of advection owing to sap flux, and does not discuss the effects of spatial variation in saturation on the thermal diffusivity. Assuming local thermal equilibrium for porous media, we propose a simple advection-diffusion model, with general boundary conditions, and derive Fourier-Bessel series solutions for the various possible cases suggested by dimensionless parameters.

Document type: 
Thesis
File(s): 
Senior supervisor: 
John Stockie
Weiran Sun
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

Coloring cayley tables of finite groups

Date created: 
2017-08-08
Abstract: 

The chromatic number of a latin square L, denoted χ(L), is defined as the minimum number of partial transversals needed to cover all of its cells. It has been conjectured that every latin square L satisfies χ(L) ≤ |L| + 2. If true, this would resolve a longstanding conjecture, commonly attributed to Brualdi, that every latin square has a partial transversal of length |L|−1. Restricting our attention to Cayley tables of finite groups, we prove two results. First, we constructively show that all finite Abelian groups G have Cayley tables with chromatic number |G|+2. Second, we give an upper bound for the chromatic number of Cayley tables of arbitrary finite groups. For |G| ≥ 3, this improves the best-known general upper bound from 2|G| to 3 |G|, while yielding an even stronger result in infinitely many cases.

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

Solving multivariate diophantine equations and their role in multivariate polynomial factorization

Date created: 
2017-08-14
Abstract: 

Multivariate polynomial factorization over integers via multivariate Hensel lifting (MHL) is one of the central areas of research in computer algebra. Most computer algebra platforms, such as Maple, Magma and Singular, implement Wang's incremental design of MHL which lifts the factors one variable at a time and one degree at a time. At each step MHL must solve a multivariate diophantine problem (MDP) which Wang solves using the same idea; lifting the solutions one variable and one degree at a time. Although this performs well when the evaluation points are mostly zero, it performs poorly when there are many non-zero evaluation points as the number of MDP problems to be solved can be exponential in the number of variables. In this thesis we introduce a new non-recursive solution to the MDP which explicitly exploits the sparsity of the solutions to the MDP. We use sparse interpolation techniques and exploit the fact that at each step of MHL, the solutions to MDP's are structurally related. We design a probabilistic sparse Hensel lifting algorithm (MTSHL) and give a complete average case complexity analysis for it. We describe a series of experiments based on our implementation of MTSHL, compare its efficiency with Wang's algorithm, and show that MTSHL performs better for many practical applications. We also show that previous probabilistic approaches proposed for MHL as an alternative to Wang's algorithm are not practical whereas MTSHL is practical and the running time is predictable.

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