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

Receive updates for this collection

An explicit correspondence between certain modular curves

Date created: 
2017-05-03
Abstract: 

In this thesis, we recall an alternative proof of Merel's conjecture, which asserts that a certain explicit correspondence gives the isogeny relation between the Jacobians associated to the normalizer of split and non-split Cartan subgroups. This alternative proof does not require extensive representation theory and can be formulated in terms of certain finite geometries modulo $\ell$. Secondly, we generalize these arguments to exhibit an explicit correspondence which gives the isogeny relation between the Jacobians associated to split and non-split Cartan subgroups. An interesting feature is that the required explicit correspondence is considerably more complicated but can be expressed as a certain linear combination of double coset operators whose coefficients we are able to make explicit.

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

Magic Eulerian Hypergraphs

Date created: 
2017-05-08
Abstract: 

Motivated by the phenomenon of contextuality in quantum physics we study a particular family of proofs of the Kochen-Specker theorem. A proof is represented by a pair consisting of a hypergraph where each vertex has even degree, called an Eulerian hypergraph, and a labeling of its vertices. If a hypergraph admits a labeling constituting a proof, we say it is magic. We are interested in determining whether a given hypergraph is magic. Working with the duals of Eulerian hypergraphs, we develop the parity minor relation, which allows us to establish a concept of minimality for the magic property. We introduce a splitting operation to show that certain hypergraphs are not magic. We combine the parity minor relation and the splitting operation in order to search for minimally magic hypergraphs whose duals are grafts, hypergraphs with one edge of size four and all other edges of size two.

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

Computing characteristic polynomials of matrices of structured polynomials

Date created: 
2017-04-13
Abstract: 

We present a parallel modular algorithm for finding characteristic polynomials of matrices with integer coefficient bivariate monomials. For each prime, evaluation and interpolation gives us the bridge between polynomial matrices and matrices over a finite field so that the Hessenberg algorithm can be used. After optimizations, we are able to save a significant amount of work by incremental Chinese remaindering and early termination.

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

Algorithms for colourful simplicial depth and median in the plane

Author: 
Date created: 
2017-04-07
Abstract: 

The colourful simplicial depth (CSD) of a point x in R^2 relative to a configuration P=(P^1, P^2, ..., P^k) of n points in k colour classes is exactly the number of closed simplices (triangles) with vertices from 3 different colour classes that contain x in their convex hull. We consider the problems of efficiently computing the colourful simplicial depth of a point x, and of finding a point in R^2, called a median, that maximizes colourful simplicial depth. For computing the colourful simplicial depth of x, our algorithm runs in time O(n log(n) + kn) in general, and O(kn) if the points are sorted around x. For finding the colourful median, we get a time of O(n^4). For comparison, the running times of the best known algorithm for the monochrome version of these problems are O(n log(n)) in general, improving to O(n) if the points are sorted around x for monochrome depth, and O(n^4) for finding a monochrome median.

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

Rooted graph minors and the reducibility of graph polynomials

Date created: 
2017-04-05
Abstract: 

In 2009, Brown gave a set of conditions which when satisfied imply that a Feynman integral evaluates to a multiple zeta value. One of these conditions is called reducibility, which loosely says there is an order of integration for the Feynman integral for which Brown's techniques will succeed. Reducibility can be abstracted away from the Feynman integral to just being a condition on two polynomials, the first and second Symanzik polynomials. The first Symanzik polynomial is defined from the spanning trees of a graph, and the second Symanzik polynomial is defined from both spanning forests of a graph and some edge and vertex weights, called external momenta and masses. Thus reducibility is a property of graphs augmented with certain weights. We prove that for a fixed number of external momenta and no masses, reducibility is graph minor closed, correcting the previously claimed proofs of this fact. A computational study of reducibility was undertaken by Bogner and L\"{u}ders who found that for graphs with $4$-on-shell momenta and no masses, $K_{4}$ with momenta on each vertex is a forbidden minor. We add to this and find that when we restrict to graphs with four on-shell external momenta the following graphs are forbidden minors: $K_{4}$ with momenta on each vertex, $W_{4}$ with external momenta on the rim vertices, $K_{2,4}$ with external momenta on the large side of the bipartition, and one other graph. We do not expect that these minors characterize reducibility, so instead we give structural characterizations of the graphs not containing subsets of these minors. We characterize graphs not containing a rooted $K_{4}$ or rooted $W_{4}$ minor, graphs not containing rooted $K_{4}$ or rooted $W_{4}$ or rooted $K_{2,4}$ minors, and also a characterization of graphs not containing all of the known forbidden minors. Some comments are made on graphs not containing $K_{3,4}$, $K_{6}$ or a graph related to Wagner's graph as a minor.

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

Numerical simulations of a multiscale model for maple sap exudation

Date created: 
2017-03-24
Abstract: 

Sap exudation refers to the process whereby trees such as sugar maple (Acer saccharum) and red maple (Acer rubrum) generate elevated stem pressure, which permits maple sap to be harvested as a viable agricultural product. There exists a vast literature on sap exudation and various hypotheses regarding the physical and biological mechanisms for in- ternal pressure generation in trees but very limited mathematical modeling work. Here, we perform a careful parametric study of a model for sap exudation recently published by Graf et al. [J R Soc Interface 12:20150665, 2015] which consists of a nonlinear system of differential equations obtained by homogenizing the equations governing phase change and sap transport at the cellular level. We focus on the influence of realistic daily temperature oscillations on the resulting stem pressure and draw comparisons with experimental mea- surements on red and sugar maple saplings taken during the sap harvest season. This study demonstrates the limitations and capabilities of our model in terms of capturing realistic exudation behaviour.

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

The combinatorial RNA design problem for binary trees

Author: 
Date created: 
2017-04-13
Abstract: 

The nucleotides adenine, uracil, guanine, and cytosine are the building blocks of ribonucleic acid (RNA). Certain nucleotides can pair, creating folds in the RNA sequence known as the secondary structure. The stability of the secondary structure increases with the number of pairings, but there are typically many foldings that achieve the maximum number of pairings. The combinatorial RNA design problem is to find a design for a target secondary structure (a sequence which can achieve its maximum number of pairings only by folding into this structure), or else to show that no design exists for this structure. A design is known for a class of secondary structures in which all nucleotides are paired, but a structure in which even one nucleotide is unpaired need not admit a design. We prove constructively that there is an infinite class of secondary structures containing unpaired nucleotides and admitting a design.

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

Graph Invariants with Connections to the Feynman Period in phi-4 Theory.

Author: 
Date created: 
2017-04-07
Abstract: 

Feynman diagrams in scalar phi-4 theory have as their underlying structure 4-regular graphs. In particular, any 4-point phi-4 graph can be uniquely derived from a 4-regular graph by deleting a single vertex. The Feynman integral is encoded by the structure of the graph and is used to determine amplitudes of particle interactions. The Feynman period is a simplified version of the Feynman integral. The period is of special interest, as it maintains much of the important number theoretic information from the Feynman integral. It is also of structural interest, as it is known to be preserved by a number of graph theoretic operations. In particular, the vertex deleted in constructing the 4-point graph does not affect the Feynman period, and it is invariant under planar duality and the Schnetz twist, an operation that redirects edges incident to a 4-vertex cut. Further, a 4-regular graph may be produced by identifying triangles in two 4-regular graphs and then deleting these edges. The Feynman period of this graph with a vertex deleted is equal to the product of the Feynman periods of the two smaller graphs with one vertex deleted each. These operations currently explain all known instances of non-isomorphic 4-point phi-4 graphs with equal periods.With this in mind, other graph invariants that are preserved by these operations for 4-point phi-4 graphs are of interest, as they may provide insight into the Feynman period and potentially the integral. In this thesis the extended graph permanent is introduced; an infinite sequence of residues from prime order finite fields. It is shown that this sequence is preserved by these three operations, and has a product property. Additionally, computational techniques will be established, and an alternate interpretation will be presented as the point count of a novel graph polynomial.Further, the previously existing c2 invariant and Hepp bound are examined, two graph invariants that are conjectured to be preserved by these graph operations. A combinatorial approach to the c2 invariant is introduced.

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

Odd disjoint trails and totally odd graph immersions

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

The odd edge-connectivity between two vertices in a graph is the maximum number λ_o(u,v) of edge-disjoint (u, v)-trails of odd length. In this thesis, we define the perimeter of a vertex- set, a natural upper bound for the odd edge-connectivity between some of its constituent pairs. Our central result is an approximate characterization of odd edge-connectivity: λ_o(u, v) is bounded above and below by constant factors of the usual edge-connectivity λ_o(u, v) and/or the minimum perimeter among vertex-sets containing u and v. The relationship between odd edge-connectivity and perimeter has many implications, most notably a loose packing–covering duality for odd trails. (In contrast, odd paths do not obey any such duality.) For Eulerian graphs, we obtain a second, independent proof of the packing–covering duality with a significantly better constant factor. Both proofs can be implemented as polynomial-time approximation algorithms for λ_o(u,v). After observing that perimeter satisfies a submodular inequality, we are able to prove an analogue of the Gomory–Hu Theorem for sets of minimum perimeter and, consequently, to construct an efficient data structure for storing approximate odd edge-connectivities for all vertex pairs in a graph. The last part of the thesis studies more complicated systems of odd trails. A totally odd immersion of a graph H in another graph G is a representation in which vertices in H correspond to vertices in G and edges in H correspond to edge-disjoint odd trails in G. Using our perimeter version of the Gomory–Hu Theorem, we describe the rough structure of graphs with no totally odd immersion of the complete graph K_t. Finally, we suggest a totally odd immersion variant of Hadwiger’s Conjecture and show that it is true for almost all graphs.

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

Three Problems Involving Permutations

Date created: 
2016-12-05
Abstract: 

We study three problems involving permutations: the n-card problem, inv-Wilf-equivalence, and suitable sets of permutations. The n-card problem is to determine the minimal intervals [u, v] such that for every n times n stochastic matrix A there is an n times n permutation matrix P (depending on A) such that tr(PA) belongs to [u, v]. The minimal intervals for the n-card problem are known only for n <= 4. We answer a question posed by Sands, by showing that [1, 2] is a solution to the n-card problem for all n >= 2. We also show that each closed interval of length n/(n−1) contained in [0, 2) is a solution to the n-card problem for all n >= 2. Wilf-equivalence is one of the central concepts of pattern-avoiding permutations. The two known infinite families of Wilf-equivalent permutation pairs both satisfy the stronger condition of shape-Wilf-equivalence. Dokos et al. studied a different strengthening of Wilf-equivalence called inv-Wilf-equivalence. They conjectured that all inv-Wilf-equivalent permutation pairs arise from trivial symmetries. We disprove this conjecture with an infinite family of counterexamples, obtained by generalizing simultaneously the concepts of shape-Wilf-equivalence and inv-Wilf-equivalence. We also prove the Baxter-Jaggard conjecture on even-shape-Wilf-equivalent permutation pairs. A set of N permutations of {1, 2, . . . , v} is (N, v, t)-suitable if each symbol precedes each subset of t − 1 others in at least one permutation. We give examples of suitable sets of permutations for new parameter triples (N, v, t). We relate certain suitable sets of permutations with parameter t to others with parameter t + 1, thereby showing that one of the two infinite families presented by Colbourn can be constructed directly from the other. We prove an exact nonexistence result for suitable sets of permutations using elementary combinatorial arguments. We then establish an asymptotic nonexistence result using Ramsey’s theorem.

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