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

Receive updates for this collection

Cops and robbers on geometric graphs and graphs with a set of forbidden subgraphs

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

In this thesis we study the game of cops and robbers on some special class of graphs, including planar graphs and geometric graphs. Moreover, under some conditions on graph diameter, we characterize all sets H of graphs with bounded diameter for which H-free graphs are cop-bounded. Furthermore, we extend our characterization to the case of cop-bounded classes of graphs defined by a set H of forbidden graphs such that the components of members of H have bounded diameter.

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

On the density of parameterizations of generalized Fermat equations of signature (2,3,3) that produce locally primitive solutions

Date created: 
2019-05-15
Abstract: 

We consider the equations Ax^2+By^3=Cz^3, where A,B,C are square-free and pairwise co-prime integers. A solution (x,y,z) is called primitive if it consists of co-prime integers. Adapting earlier work for the equations x^2+y^3=Cz^3, we show that primitive solutions give rise to integer Klein forms of degree four, with discriminant A^3B^2C . Whether Klein forms come from primitive solutions is determined by local conditions. We show that for primes p dividing B, there are exactly four GL_2(Q_p)-equivalence classes of Klein forms that are relevant, and that exactly half of those classes come from Z_p-primitive solutions. We also show that if we set A=1, then further restricting B,C to square-free and co-prime integers leaves us with an asymptotically positive proportion of triples.

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

Sparse and low rank approximation via partial regularization: Models, theory and algorithms

Author: 
Date created: 
2019-02-28
Abstract: 

Sparse representation and low-rank approximation are fundamental tools in fields of signal processing and pattern analysis. In this thesis, we consider introducing some partial regularizers to these problems in order to neutralize the bias incurred by some large entries (in magnitude) of the associated vector or some large singular values of the associated matrix. In particular, we first consider a class of constrained optimization problems whose constraints involve a cardinality or rank constraint. Under some suitable assumptions, we show that the penalty formulation based on a partial regularization is an exact reformulation of the original problem in the sense that they both share the same global minimizers. We also show that a local minimizer of the original problem is that of the penalty reformulation. Specifically, we propose a class of models with partial regularization for recovering a sparse solution of a linear system. We then study some theoretical properties of these models including existence of optimal solutions, sparsity inducing, local or global recovery and stable recovery. In addition, numerical algorithms are proposed for solving those models, in which each subproblem is solved by a nonmonotone proximal gradient (NPG) method. Despite the complication of the partial regularizers, we show that each proximal subproblem in NPG can be solved as a certain number of one-dimensional optimization problems, which usually have a closed-form solution. The global convergence of these methods are also established. Finally, we compare the performance of our approach with some existing approaches on both randomly generated and real-life instances, and report some promising computational results.

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

Topics in quadratic binary optimization problems

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

In this dissertation, we consider the quadratic combinatorial optimization problem (QCOP) and its variations: the generalized vertex cover problem (GVC), the quadratic unconstrained binary optimization problem (QUBO), and the quadratic set covering problem (QSCP). We study these problems as discussed below. For QCOP, we analyze equivalent representations of the pair (Q, c), where Q is a quadratic cost matrix and c is a linear cost vector. We present various procedures to obtain equivalent representations, and study the effect of equivalent representations on the computation time to obtain an optimal solution, on the quality of the lower bound values obtained by various lower bounding schemes, and on the quality of the heuristic solution. The first variation of QCOP is GVC, and we show that GVC is equivalent to QUBO and also equivalent to some other variations of GVC. Some solvable cases are identified and approximation algorithms are suggested for special cases. We also study GVC on bipartite graphs. QUBO is the second variation of QCOP. For QUBO, we analyze several heuristic algorithms using domination analysis. We show that for QUBO, if any algorithm that guarantees a solution no worse than the average, has a domination ratio of at least 1/40. We extend this result to the maximum and minimum cut problems; maximum and minimum uncut problems; and GVC. We also study the QUBO when Q is: 1) (2d + 1)-diagonal matrix, 2) (2d + 1)-reverse-diagonal matrix, and 3) (2d+1)-cross diagonal matrix, and show that these cases are solvable in polynomial time when d is fixed or is of O(log n). The last variation of QCOP is QSCP. For QSCP, we identify various inaccuracies in the paper by R. R. Saxena and S. R. Arora, A linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm does not guarantee optimality, contrary to what is claimed. We also present the mixed integer linear programming formulations (MILP) for QSCP. We compare the lower bounds obtained by the linear programming relaxations of MILPs, and study the effect of equivalent representations of QSCP on these MILPs.

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

The quadratic travelling salesman problem: complexity and approximation

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

In this thesis we study the Quadratic Travelling Salesman Problem (QTSP) which generalizes the well-studied Traveling Salesman Problem and several of its variations. QTSP is to find a least cost Hamiltonian cycle in an edge-weighted graph, where costs are defined for all pairs of edges contained in the Hamilton cycle. This is a more general version than the one that appears in the literature as the QTSP, denoted here as the adjacent quadratic TSP, which only considers costs for pairs of adjacent edges. We give a complete characterization of the QTSP linearization problem and give a polynomial time algorithm to find a linearization whenever one exists. The fixed-rank QTSP is introduced as a restricted version of the QTSP where the cost matrix has fixed rank p. We study QTSP by examining the complexity of searching exponential neighbourhoods for QTSP, the fixed-rank QTSP and the adjacent quadratic TSP. We develop pseudopolynomial time algorithms for many of these special cases, and give FPTAS whenever possible. Polynomial algorithms are given for each special case which is not NP-hard.

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

Well-posedness of a Gas-disk Interaction System

Author: 
Peer reviewed: 
No, item is not peer reviewed.
Date created: 
2019-08
Abstract: 

This thesis concerns a gas-disk interaction system: the disk is immersed in a gas and acted on by a drag force and an external force. The evolution of the system is described by a coupled system of integro-differential equations. More specifically, we use a pure kinetic transport equation to model the gas and a Newton’s Second Law ODE to model the disk. The two are coupled via the drag force exerted on the disk by the gas and the boundary condition for the gas colliding with the disk.

Systems of this type have been extensively studied in the literature, both analytically and numerically. To the best of our knowledge, existing works focus on existence of nearequilibrium solutions and their long-time behaviour. However, uniqueness of solutions has not been investigated previously. In the first part of the thesis we will give the first rigorous proof of existence and uniqueness of solutions for general initial data and external forcing.

The most important physical feature of this system is its inherent recursivity: particles can collide with the disk time and time again. Recognizing this structure and introducing recursivity into the equations by the means of gas decomposition is the key to obtaining the well-posedness result.

In the second part of the thesis we will present a simple numerical method for computing the trajectory of the disk using the aforementioned gas decomposition. We will contrast it with methods used previously, and also use it to show that considering only one or two precollisions for the gas particles is sufficient to accurately compute the density distribution of the gas and the velocity of the disk.

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

An infinite family of Kochen-Specker sets in four-dimensional real spaces

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

Contextuality is a feature differentiating between classical and quantum physics. It is anticipated that it may become an important resource for quantum computing and quantum information processing. Contextuality was asserted by the Kochen-Specker (KS) theorem. We study parity proofs of the KS theorem. Although many parity proofs exist, only finitely many of them have been discovered in any real or complex space of fixed dimension. We study a special family of chordal ring graphs. We construct orthonormal representations of their line graphs in four-dimensional real spaces. Our construction takes advantage of the high degree of symmetry present in the special class of chordal rings that we use. In this way we find, for the first time, an infinite family of KS sets in a fixed dimension.

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

Graph immersions

Author: 
Date created: 
2018-11-27
Abstract: 

One of the first prominent theorems in structural graph theory is the Kuratowski-Wagner theorem which characterizes planar graphs as those with no K_{3,3} or K_5 minor. Numerous other classical theorems give precise descriptions of the class of graphs with no H-minor for numerous small graphs H. In particular, such classifications exist when H is W_4, W_5, Prism, K_{3,3}, K_5, Octahedron, and Cube. One of the most useful tools in establishing such results are splitter theorems which reduce a graph while preserving both connectivity and containment of a given minor. In this thesis we consider analogous problems for a different containment relation: immersion. Although immersion is a standard containment relation, prior to this thesis there were almost no precise structure theorems for forbidden immersions. The most prominent theorems in this direction give a rough description of graphs with no W_4 immersion and those with no K_{3,3} or K_5 immersion. Our main contributions include precise structure theorems for the class of graphs with no H-immersion when H is one of K_4, W_4, Prism, and K_{3,3}. To assist in this exploration, we have also established two splitter theorems for graph immersions, one for 2k-edge-connected graphs, and another for 3-edge-connected and internally 4-edge-connected graphs.

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

HIV epidemic control among sex workers and their clients

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

Controlling the spread of HIV among hidden, high-risk populations such as sex workers and their clients is becoming increasingly important in the fight to end AIDS. In this thesis, we identify a number of sociological and structural factors which render general control strategies ineffective among these key populations, and instead call for focused testing and interventions. A bipartite network model of sexual contacts between female sex workers and male clients is motivated using historical data from a South African mining community. HIV transmission and progression is modelled as a stochastic process on the network, and the effect of various intervention strategies on HIV prevalence in the population is determined through numerical simulations. We find that preventative interventions are highly cost effective when targeted at female sex workers. For aggressive reduction in HIV prevalence, however, the client population cannot be ignored and treatment of both populations is necessary.

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

A combinatorial description of the cup product for smooth complete toric varieties

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

For any smooth variety X, there exists an associated vector space of first-order deformations. This vector space can be interpreted using sheaf cohomology; it is the first cohomology group H^1(X,T_X), where T_X is the tangent sheaf. One can ask when it is possible to "combine" two first-order deformations. The cup product takes elements of H^1(X,T_X) x H^1(X,T_X) and maps to the obstruction space H^2(X, T_X), and the vanishing of the cup product tells us precisely when this is possible. In this thesis we give a combinatorial description of the cup product (on the level of Čech cohomology) when X is a smooth, complete, toric variety with an associated fan Σ. We also give an example of a smooth, complete, toric 3-fold for which the cup product is nonvanishing.

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