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

## Algorithmic aspects of some vertex ordering problems

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

Combinatorial Optimization problems play central role in applied mathematics and computer science. A particular class of combinatorial optimization problems is vertex ordering problems whose goal is to find an ordering on vertices of an input graph in such way that a certain objective cost is optimized. This thesis focuses on three different vertex ordering problems. First, we consider a variant of Directed Feedback Arc Set problem with applications in computational biology. We present an efficient heuristic algorithm for this problem. Next, we concentrate on parameterized complexity of Minimum Linear Arrangement problem while the parameter is size of vertex cover. We formulate the problem as Quadratic Integer Programming and propose two new techniques to tackle the problem. Finally, we introduce a vertex ordering problem on bipartite graphs with applications in different areas. We give a general algorithmic strategy for the problem, as well as, polynomial-time algorithms for three classes of graphs.

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

## Vectorial Bent Functions in Characteristic Two

Author:
Date created:
2016-02-02
Abstract:

We study Dillon-type vectorial bent functions of the monomial and multinomial varieties. We also study Kloosterman sums, which relate to the construction of Dillon-type monomial bent functions. For Dillon-type monomial functions we give sufficient conditions for vectorial bentness, leading to the construction of several new examples. We give useful necessary conditions for functions from GF(2^(4m)) to GF(4). We give new restrictions on the maximum output dimension of Dillon-type monomial bent functions on GF(2^(4m)). We subsequently show that certain Dillon-type multinomial bent functions do not meet the Nyberg bound. We give computational results regarding Dillon-type functions from GF(2^(4m)) to GF(4), suggesting that while bent monomials of this type appear to be rare, their binomial counterparts seem to be relatively abundant. Finally, we give divisibility results on Kloosterman sums valued on cosets of certain subfields of GF(2^m), leading to explicit constructions of Kloosterman zeros and Dillon-type monomial bent functions.

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

## 4D Reconstruction of dynamic studies with the discovery NM 530c SPECT Camera

Author:
Date created:
2016-02-25
Abstract:

Single photon emission computed tomography (SPECT) is a nuclear medicine imaging technique. Functional imaging allows doctors to study the physiology and function of living organs. As physiological processes in a human body are dynamic, studying changes of their temporal characteristics and spatial distribution may provide important diagnostic information. This thesis investigates various aspects of dynamic functional SPECT imaging. The algorithms are tailored for a dedicated cardiac camera system, namely the GE Discovery NM530c, a pinhole camera that can acquire views from different angles simultaneously. A fundamental feature of dynamic reconstruction is that the problem is highly underdetermined. Hence, any given consistent dataset allows infinitely many solutions. The existing dSPECT method “regularizes” the solutions by introducing constraints based on the underlying physics; it reconstructs the dynamic activity by solving one large system, as opposed to the frame-by-frame static reconstruction approach. Therefore, dSPECT reconstruction maintains temporal correlations. In this thesis, the dSPECT method was used to reconstruct images that had been scanned with the Discovery NM530c. The time activity curves of reconstructed images obtained from dSPECT are smoother than those obtained from static reconstructions. A new method, dSPECTpv, was developed to allow for successful reconstruction of dynamic behaviour that had not been observed previously in dynamic SPECT studies. Although the time activity curves of reconstructed images are much smoother, little or no improvement is observed when those reconstructions are used to estimate kinetic parameters. In this thesis, the Discovery NM530c acquisition process was modeled with the Monte Carlo method, using the simulation software GATE. Hence, computer simulations can be used to investigate the camera geometry. Our software is a useful tool in optimizing camera setup and the acquisition protocol.

Document type:
Thesis
File(s):
Supervisor(s):
Manfred Trummer
Anna Celler
Department:
Science: Department of Mathematics
Thesis type:
(Thesis) Ph.D.

## Agent-based modelling of nest site selection by bees and ants

Author:
Date created:
2016-04-14
Abstract:

In this study we develop an agent-based time discrete model to show how honeybees and ants are able to choose the best site available under different circumstances. We focus on the agent-based model introduced by Christian List, Christian Elsholtz and Thomas Seeley in their paper: Independence and interdependence in collective decision making: an agent-based model of nest-site choice by honeybee swarms. Philosophical Transactions of the Royal Society of London B: Biological Sciences, 364(1518):755-762, 2009. In that paper, the authors model the nest site selection of honeybees using an agent model and study the affect of advertising and reliability in nest site selection of honeybees. We extend the model and run it for honeybees to show that being closed-minded reduces the accuracy of the final result. We then modify the model and apply it to two different species of ants. We study how changing different parameters such as colony size, threshold, advertising and reliability can affect the final consensus accuracy. We finally compare results from our mathematical simulations to that of lab experiments and discuss the similarities and differences between the two insect species.

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

## Mathematical Model of Thermoregulation in Honeybee Swarms

Author:
Date created:
2015-12-03
Abstract:

Honeybees are masters of regulating their temperatures collectively, even in the absence of a hive. A reproductive swarm consisting of a queen and about half a colony's workers will leave their hive to find a new home. Prior to settling on a permanent home, the honeybees form a stationary swarm, where the bees cling onto one another from a roof-type structure, completely exposed to the elements. Because bees are so sensitive to extremes of heat and cold, it is essential that the swarm has ways to control its temperature. We present a mathematical model to study how honeybees thermoregulate by adjusting their movement and metabolic heat output. We introduce a system of coupled partial differential equations and integral equations to describe the swarm temperature, density, and size, along with a corresponding numerical scheme. We then relax the assumption of spherical symmetry and extend the model by studying non-spherical swarms.

Document type:
Thesis
File(s):
Supervisor(s):
JF Williams
John Stockie
Department:
Science: Department of Mathematics
Thesis type:
(Thesis) M.Sc.

## Some Results on Structure in Graphs and Numbers

Author:
Date created:
2015-11-30
Abstract:

This thesis present three results. The first is a result in structural graph theory. It demonstrates a large family of complete graphs embedded (clique embeddings) as minors of the grid-like Chimera graph, which is an abstract graph representing the D-Wave quantum adiabatic processor where vertices of the Chimera graph represent qubits in the processor. These particular embeddings are uniform in the sense that each vertex of the complete graph is represented by an equal number of vertices in the Chimera graph, which is thought to improve performance of the D-Wave processor. We present a polynomial-time algorithm to find a largest clique in this family in arbitrary induced subgraphs. Then we use the output of our algorithm as a measure of quality of a particular induced subgraph and show that the size of a largest clique embedding grows logarithmically in the grid size when a fixed percentage of qubits have been deleted. The second is a result in design theory and combinatorial number theory; constructing a family of designs called Heffter arrays. A Heffter array is a (m x n) integer matrix whose entries' absolute values cover the interval [1,mn], where every row and column sums to zero modulo 2mn+1. Archdeacon uses Heffter arrays to construct embeddings of the complete graph K_{2mn+1} into orientable surfaces such that every edge appears in an m-cycle and an n-cycle, provided either m or n is odd. This chapter establishes that m \times n Heffter arrays exist if and only m>2 and n>2. The third is a result in combinatorial number theory and structural graph theory. For subsets A,B of a group G define the product set AB = {ab : a in A, b in B}. Presented in this chapter is a classification the sets A,B such that |AB| <= |A|+|B| when H

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

## Fast direct integral equation methods for the Laplace-Beltrami equation on the sphere

Author:
Date created:
2015-07-24
Abstract:

Integral equation methods for solving the Laplace-Beltrami equation on the unit sphere are presented and applied to the problem of point vortex motion. The Laplace-Beltrami equation is first posed on a simply connected domain on the sphere, then reformulated into an integral equation and discretized. The resulting linear system is solved by adapting current fast direct solvers from fully two and three dimensional problems to the surface of the sphere. The solution is achieved in O(N) operations, where N is the number of points lying on the contour of a single “island.” The performance of the solver is studied through several representative examples. To highlight the efficiency of the direct method for problems with multiple right hand sides, the solver is used to study point vortex motion. The relationship between the Laplace-Beltrami equation and the motion of a point vortex in the presence of coastlines is explained—both in terms of finding instantaneous streamlines of the fluid and the trajectory of a vortex over time. The solver is used to construct these instantaneous streamlines and trajectories, of which the latter requires the Laplace-Beltrami equation to be solved for each time step. In this case the performance of the direct solver is found to exceed previous iterative approaches using the fast multipole method. Lastly, the fast direct solver is adapted to the multiply connected case and several numerical examples are presented.

Document type:
Thesis
File(s):
Supervisor(s):
Mary-Catherine Kropinski
Department:
Science: Department of Mathematics
Thesis type:
(Thesis) M.Sc.

## Unfolding of Diagramming and Gesturing between Mathematics Graduate Student and Supervisor during Research Meetings

Author:
Date created:
2015-07-27
Abstract:

This study has two main purposes. The first is to confirm and advance Gilles Châtelet’s account of the role of diagramming in mathematics invention by extending his results, which were based solely on historical, mathematical manuscripts, to the context of live mathematical activity. The second purpose is to elucidate the enculturation process of a graduate student into mathematical research, which has hitherto received limited research attention. These two purposes are related through the virtual and physical gestures that the graduate student engages in during diagramming thereby providing insights into mathematical invention and the enculturation process. This study adopts a qualitative methodology based on field notes, video-recordings and digital images from nine research meetings, which were held weekly over a period of three months. Current research theorises the role of mathematical diagrams in diametrically opposed ways: diagrams are either a visual representation of already existing mathematical objects and relations, or they are the means through which mathematical objects and relations emerge. The latter is due to Châtelet, who regards the diagram as a material site of engaging with and mobilizing the mathematics. His approach is employed in this thesis to create a window into the realm of mathematical thinking and invention by examining how a graduate student (as the less-expert mathematician) and his supervisor and two research colleagues (as the expert mathematicians) interact with diagrams. An embodied lens, based on the work of de Freitas, Roth, Rotman, Sinclair and Streeck, exposes the similarities and differences in the way that each class of mathematician gestures and diagrams. The analysis in this thesis reveals that gesturing and diagramming support and advance mathematical communication throughout the graduate student’s enculturation process. Furthermore, a collective study of the abundant diagrams produced during research meetings leads to a life-cycle of diagrams, whose phases disclose a variety of distinct relationships between mathematician and diagram. Lastly, a detailed examination of the evolution of a particular diagram uncovers how mathematical invention emerges through gesturing and diagramming. These findings have implications for the teaching and learning of mathematics at all levels.

Document type:
Thesis
File(s):
Supervisor(s):
Jonathan Jedwab
Nathalie Sinclair
Department:
Science: Mathematics
Thesis type:
(Thesis) Ph.D.

## Parametric resonance in immersed elastic structures, with application to the cochlea

Author:
Date created:
2015-05-05
Abstract:

Examples of fluid motion driven by immersed flexible structures abound in nature. In many biological settings, for instance a beating heart, an active material generates a time-dependent internal forcing on the surrounding fluid. Motivated by such active biological structures, this thesis investigates parametric resonance in fluid-structure systems induced by an internal forcing via periodic modulation of the material stiffness. One particular application that we study is the cochlea which is the primary component for pitch selectivity in the mammalian hearing system. We present a 2D model of the cochlea in which a periodic internal forcing gives rise to amplification of basilar membrane (BM) oscillations. This forcing is inspired by experiments showing that outer hair cells within the cochlear partition change their lengths when stimulated, which can in turn distort the partition and modulate tension across the BM. We demonstrate the existence of resonant (unstable) solutions through a Floquet stability analysis of the linearized governing equations. Moreover, we show that an internal forcing is sufficient to produce travelling waves along the BM in the absence of any external stimulus. We next examine parametric instabilities in a 3D system by considering a closed spherical elastic membrane (or shell) immersed in a viscous, incompressible fluid. A Floquet analysis for both inviscid and viscous systems shows that parametric resonance is possible even in the presence of fluid viscosity. Numerical simulations are presented to verify the analysis and an application to cardiac fluid dynamics is discussed. Finally, we deviate from the topic of parametric instabilities to consider the natural oscillations of unforced spherical elastic membranes. We present a linear stability analysis to obtain a dispersion relation for immersed membrane oscillations for both inviscid and viscous fluids, as well as a nonlinear analysis of immersed membrane oscillations in an inviscid fluid. We then present an experiment where we measure oscillation frequencies of immersed water balloons in an attempt to corroborate the analytical results.

Document type:
Thesis
File(s):
Supervisor(s):
John Stockie
Department:
Science: Mathematics
Thesis type:
(Thesis) Ph.D.

## Die Freude an der Gestalt: Methods, Figures, and Practices in Early Nineteenth Century Geometry

Author:
Date created:
2015-04-10
Abstract:

As recounted by later historians, modern geometry began with Jean Victor Poncelet, whose contributions then spread to Germany alongside an opposition between geometric methods that came to be exemplified by the antagonism of Julius Plücker, an analytic geometer, and Jakob Steiner, a synthetic geometer. To determine the participants, arguments, and qualities of this perceived divide, we drew upon historical accounts from the late nineteenth and early twentieth centuries. Several themes emerged from the historical perspective, which we investigated within the original sources. Our questions centred on how geometers distinguished methods, when opposition arose, in what ways geometry disseminated from Poncelet to Plücker and Steiner, and whether this geometry was "modern" as claimed. Our search for methodological debates led to Poncelet's proposal that within pure geometry the figure was never lost from view, while it could be obscured by the calculations of algebra. We examined his argument through a case study that revealed visual attention within constructive problem solving, regardless of method. Further, geometers manipulated and represented figures through textual descriptions and coordinate equations. In these same texts, Poncelet and Joseph-Diez Gergonne instigated a debate on the principle of duality. Rather than dismiss their priority dispute as external to mathematics, we consider the texts involved as a medium for communicating geometry in which Poncelet and Gergonne developed strategies for introducing new geometry to a conservative audience. This conservative audience did not include Plücker and Steiner, who adapted new vocabulary, techniques and objects. Through comparing their common research, we found they differentiated methods based on personal considerations. Plücker practiced a "pure analytic geometry" that avoided calculation. Steiner admired "synthetic geometry'' because of its organic unity. These qualities contradicted descriptions of analytic geometry as computational or synthetic geometry as ad-hoc. Finally, we turned to claims for novelty in the context of contemporary French books on geometry. Most of these books point to a pedagogical orientation, where the methodological divide was grounded in student prerequisites and "modern'' implied the use of algebra in geometry. By contrast, research publications exhibited evolving forms of geometry that evaded dichotomous categorization.

Document type:
Thesis
File(s):
Supervisor(s):
Thomas Archibald
Catherine Goldstein
Department:
Science:
Thesis type:
(Thesis) Ph.D.