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

Receive updates for this collection

Combinatorial methods for integer partitions

Author: 
Date created: 
2021-08-20
Abstract: 

Integer partitions, while simply defined, are associated with some of the most celebrated results in mathematics. Despite their simple definition, many results on integer partitions can be shockingly difficult to obtain. In this thesis, we use elementary and combinatorial methods to make progress on some fundamental problems related to linear Diophantine equations and integer partitions. We find an efficient method for finding the number of nonnegative integer solutions (x,y,z) of the equation ax+by+cz=n for given positive integers a, b, c, and n. Our formula involves summations of floor functions of fractions. To quickly evaluate these sums, we find a reciprocity relation that generalizes a well-known reciprocity relation of Gauss related to the law of quadratic reciprocity. Furthermore, we use our result for the number of solutions to a particular equation to prove that the above result of Gauss is equivalent to a well-known result of Sylvester related to the Frobenius Coin Problem. Moreover, using this equivalence and our generalization of the reciprocity relation of Gauss, we obtain a nice generalization of Sylvester's result. In a different problem, we prove four conjectures of Berkovich and Uncu regarding some inequalities about relative sizes of two closely related sets consisting of integer partitions whose parts lie in the interval {s,...,L+s}. Further restrictions are placed on the sets by specifying impermissible parts as well as a minimum part. Our methods consist of constructing injective maps between the relevant sets of partitions. We obtain a very natural combinatorial proof of Euler's recurrence for integer partitions using the principle of inclusion and exclusion. Using our approach, we are able to generalize Euler's recurrence in the sense that for sufficiently large n, we can express p(n) explicitly as an integer linear combination of p(n-k), p(n-k-1),... etc. Using such recurrences, we obtain results related to Ramanujan's congruences. For example, if p_m(n) denotes the number of partitions of n that have largest part at most m, we show that for m > 5, the numbers p_m(5n+4) are not divisible by 5 for infinitely many values of n.

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

On the volume of the Birkhoff polytope

Date created: 
2021-04-15
Abstract: 

The Birkhoff polytope was introduced in 1946 to facilitate the study of doubly stochastic matrices. The volume of the n-th Birkhoff polytope is an essential characteristic but methods to compute this are computationally complex and the volume is only known up to n = 10. In this thesis, we apply a novel automated method to calculate the relative volume using analytic combinatorics in several variables. An implementation using Maple and Sage computes this volume up to n = 6 and we compare to existing methods including interpolation, Euler’s generating function, complex analytic techniques, and Barvinok’s Algorithm (LattE). The key advantage of this method is its robustness and adaptability to variants of the initial problem.

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

On the cogrowth series of free products of finite groups

Author: 
Date created: 
2021-04-19
Abstract: 

Given a group G with a finite set of generators, S, it is natural to ask if the product of n generators from S evaluate to the identity. The enumerative version of this problem, known as the cogrowth problem, counts the number of such products and studies the associated counting sequence. Many cogrowth sequences are known. This thesis focuses on the free products of finite groups: Specifically, cyclic and dihedral groups. Such groups have the property that their cogrowth generating functions are algebraic functions, and thus, are solutions to implicit polynomial equations. Using algebraic elimination techniques and free probability theory, we establish upper bounds on the degrees of the polynomial equations that they satisfy. This has implications for asymptotic enumeration, and makes it theoretically possible to determine the functions explicitly.

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

The minimax linear fractional programming problem with binary variables

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

The single ratio linear fractional programming problem when the denominator of the objective function ratio is non-negative is solvable in polynomial time. This result extends to several classes of optimization problems with binary variables. However, when the denominator is allowed to take both positive and negative values, even the unconstrained problem with binary variables is NP-hard. Generalization of this problem where a sum of ratios is also well studied. Experimental results on this however are restricted to non-negative denominators. In this thesis we consider the minimax version of the multi-ratio problem with binary variables. The continuous version of the minimax problem is also well-studied but to the best of our knowledge not much research work has been done on the binary version. We present various mathematical programming formulations of the problem for the case of non-negative denominators as well as arbitrary denominators. We also present algorithms to overcome some of the computational difficulties. Extensive computational analysis has been carried under the scenarios of unconstrained problems, problems with a knapsack constraint, and problems with assignment constraints to assess the relative merits of the models. The analysis disclosed some interesting insights into the structure of the problems.

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

From eigenbeauty to large-deformation horror

Date created: 
2020-08-14
Abstract: 

In this thesis we investigate eigenproblems arising in spectral geometry and in the theory of linear elasticity, and numerically study the mechanics of skeletal muscles in three dimensions. We first introduce a novel framework based on a combined finite element-Bayesian optimization strategy to tackle problems in spectral optimization. This method is used to investigate the Pólya-Szegö conjecture for the Dirichlet eigenvalues of the Laplacian on polygons and a similar conjecture for the Steklov eigenvalues for the Laplacian is proposed. We next explore four different eigenproblems for the Lamé operator in linear elasticity. For each we establish the existence of a countable (finite or infinite) set of eigenpairs. The first one relates to Steklov eigenpairs for elasticity where the spectral parameter appears on a Robin type boundary condition. The second eigenproblem concerns eigenmodes whose tangential traction and normal displacement on the boundary are constrained. The third eigenproblem refers to eigenmodes whose normal traction and tangential displacement are fixed on the boundary. We finally consider the Jones eigenvalue problem: elastic modes are assumed to be traction free on the boundary with the extra condition that they must be purely tangential to the boundary. For each eigenproblem, new versions of Korn’s inequalities are proven to establish the existence of a point spectrum. Finally, we present a new numerical framework to computationally simulate the large deformations of skeletal muscles in three dimensions. A semi-implicit method in time and finite element method in space are coupled to approximate the solutions of the nonlinear dynamic system that governs the deformation of these tissues. This framework is later utilized to explore questions on the effects of density and inertia in muscle performance, to investigate the energy distribution in muscle during isometric contractions, and to study the energetics of muscles during compression tests on the surface of the tissues.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Nilima Nigam
James Wakeling
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) Ph.D.

The maximum weight stable set problem with a budget constraint

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

We consider the maximum weight stable set problem with an additional budget constraint (BSS) which is also known as the knapsack problem with conflict-pair constraints. A unifying 0-1 programming formulation is given that subsumes two well-studied formulations for the problem and we analyze the strength of the LP relaxation of this model. Also, we present an alternative view of the extended cover inequalities for the knapsack polytope and using this, along with other upper bounds on the stability number of a graph, strengthened 0-1 linear programming formulations of BSS are presented. Further, we study two binary quadratic formulations of BSS and explore the relationship between its linearizations and our 0-1 linear programming formulations. Results of extensive computational analysis carried out using our models are presented that compares various features of the models and their relative merits.

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

Global guarantees from local knowledge: Stable and robust recovery of sparse in levels vectors

Date created: 
2020-08-17
Abstract: 

The model of sparse vectors has proven invaluable for compressive imaging, allowing for signal recovery from very few linear measurements. Recently however, the structured sparsity model of sparsity in levels has inspired a new generation of effective acquisition and reconstruction modalities. Moreover this local structure arises in various areas of signal processing such as parallel acquisition, radar, and the sparse corruptions problem. Reconstruction strategies for sparse in levels signals have previously relied on a suitable convex optimization program. While iterative and greedy algorithms can outperform convex optimization and have been studied extensively in the case of standard sparsity, little is known about their generalizations to the sparse in levels setting. We bridge this gap by showing new stable and robust recovery guarantees for sparse in level variants of the iterative hard thresholding and the compressive sampling matching pursuit algorithms. Our theoretical analysis generalizes recovery guarantees currently available in the case of standard sparsity and favorably compare to sparse in levels guarantees for weighted l1 minimization, both in accuracy and computational time. In addition, we propose and numerically test an extension of the orthogonal matching pursuit algorithm for sparse in levels signals.

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

Internal wave attractors and spectra of zeroth-order pseudo-differential operators

Date created: 
2020-08-12
Abstract: 

The propagation of internal gravity waves in stratified media (such as those found in ocean basins and lakes) leads to the development of geometrical patterns called "attractors". These structures accumulate much of the wave energy and make the fluid flow highly singular. Microlocal analysts have recently related this behaviour to the spectral properties of an underlying nonlocal zeroth-order pseudo-differential operator that characterizes the dynamics of this problem. In this work, we analyze this phenomenon from a numerical analysis perspective. First, we propose a high-order pseudo-spectral method to solve the evolution problem, whose long-term behaviour is known to be non-square-integrable. Then, we use similar tools to discretize the corresponding eigenvalue problem. Since the eigenvalues are embedded in a continuous spectrum, their computation is based on viscous approximations. Finally, we explore the effect that the embedded eigenmodes have in the long-term evolution of the system.

Document type: 
Thesis
File(s): 
Supervisor(s): 
Nilima Nigam
Weiran Sun
Department: 
Science: Department of Mathematics
Thesis type: 
(Thesis) M.Sc.

Brauer-Severi varieties associated to twists of the Burkhardt quartic

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

The Burkhardt quartic is a projective threefold which, geometrically, is birational to the moduli space of abelian surfaces with full level-3 structure. We study this moduli interpretation of the Burkhardt quartic in an arithmetic setting, over a general field $k$. As it turns out, some twists of the Burkhardt quartic have a nontrivial field-of-definition versus field-of moduli obstruction. Classically, if a twist has a $k$-rational point then the obstruction can be computed as the Brauer class of an associated conic. Using representation theory, we show how to compute the obstruction without assuming the existence of a $k$-rational point, giving rise to an associated 3-dimensional Brauer-Severi variety rather than a conic. This Brauer-Severi variety itself has a related moduli interpretation.

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

Cops and robbers on Cayley graphs and embedded graphs

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

We consider the game of cops and robbers, which is a game played on a finite graph G by two players, Alice and Bob. Alice controls a team of cops, and Bob controls a robber, both of which occupy vertices of G. On Alice's turn, she may move each cop to an adjacent vertex or leave it at its current position. Similarly, on Bob's turn, he may move the robber to an adjacent vertex or leave it at its current position. Traditionally, Alice wins the game when a cop occupies the same vertex as the robber---that is, when a cop captures the robber. Conversely, Bob wins the game by letting the robber avoid capture forever. In a variation of the game, Alice wins the game when each neighbor of the robber's vertex is occupied by a cop---that is, when cops surround the robber. We will consider both of these winning conditions. The most fundamental graph invariant with regard to the game of cops and robbers is the cop number of a graph G, which denotes the minimum number of cops that Alice needs in order to have a winning strategy on G. We will introduce new techniques that may be used to calculate lower and upper bounds for the cop numbers of certain Cayley graphs. In particular, we will show that the well-known Meyniel's conjecture holds for both undirected and directed abelian Cayley graphs. We will also introduce new techniques for establishing upper bounds on the cop numbers of surface-embedded graphs bounded by the genus of the surface in the surrounding win condition.

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