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

Receive updates for this collection

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.

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.