## About Summit

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

Receive updates for this collection## The Multiplicative Assignment Problem

The quadratic assignment problem (QAP) is an extensively studied combinatorial optimization problem. The special case of QAP where the cost matrix is of rank one is called the multiplicative assignment problem (MAP). MAP is not well studied in literature, particularly in terms of experimental analysis of algorithms. In this thesis we present some mixed integer linear programming formulations and compare their selective strength using experimental analysis. We also present exact and heuristic algorithms to solve MAP. Our heuristic algorithms include improvements in existing FPTAs, as well as local search and tabu search enhancements. Results of extensive experimental analyses are also reported.

## The realisability of γ-graphs

The γ-graph γ·G of a graph G is the graph whose vertices are labelled by the minimum dominating sets of G, in which two vertices are adjacent when their corresponding minimum dominating sets differ in exactly one element. We give an explicit construction of a graph having an arbitrary prescribed set of minimum dominating sets. We show as a corollary that "labellable implies realisable for γ-graphs": if the vertices of a graph H can be labelled by distinct sets of the same size, in a manner consistent with the adjacency condition for γ-graphs, then H = γ·G for some graph G. We use this corollary to extend the classification of γ-graphs, due to Lakshmanan and Vijayakumar, to all graphs on at most six vertices. We also use this corollary to relate γ-graphs both to induced subgraphs of Johnson graphs and to optimal dominating codes in graphs.

## Resolving Zero-Divisors of Radical Triangular Sets Using Hensel Lifting and Applications

This thesis aims to create efficient algorithms for computing in the ring R = Q[z1,...,zn]/T where T is a zero-dimensional triangular set. The presence of zero-divisors in R makes it a computational challenge to use modular algorithms. In particular, there has never been a proper modular algorithm for computing greatest common divisors of polynomials in R[x]. We present two new ways of resolving zero-divisors: Hensel lifting and fault tolerant rational reconstruction, which allows us to create a new modular gcd algorithm for R[x] as well as a new inversion algorithm for R. We have implemented our algorithms in Maple using the RECDEN library, and we show that they outperform the methods currently implemented in Maple's RegularChains package. The method of Hensel lifting for resolving zero-divisors should give rise to other new modular algorithms for computing modulo triangular sets and our applications show that this approach is fruitful.

## Stability in stochastic language change models

Exemplar models are a popular class of models used to describe language change. Exemplars are detailed memories of stimuli people are exposed to, and when modelling language change are represented as vectors where each component is a phonetic variable. Each exemplar is given a category label, representing what that sound is identified as. New sounds are categorized based on how close they are to the exemplars in each category. Newly categorized exemplars become a part of the system and affect how the future sounds are produced and perceived. It is possible in certain situations in language for a category of sound to become extinct, such as a pronunciation of a word. One of the successes of exemplar models has been to model extinction of sound categories. The focus of this dissertation will be to determine whether categories become extinct in certain exemplar models and why. The first model we look at is an exemplar model which is an altered version of a k-means clustering algorithm by MacQueen. It models how the category regions in phonetic space vary over time among a population of language users. For this particular model, we show that the categories of sound will not become extinct: all categories will be maintained in the system for all time. Furthermore, we show that the boundaries between category regions fluctuate and we quantitatively study the fluctuations in a simple instance of the model. The second model we study is a simple exemplar model which can be used to model direct competition between categories of sound. Our aim in investigating this model is to determine how limiting the memory capacity of an individual in exemplar models affects whether categories become extinct. We will prove for this model that all the sound categories but one will always become extinct, whether memory storage is limited or not. Lastly, we create a new model that implements a bias which helps align all the categories in the phonetic space, using the framework of an earlier exemplar model. We make an argument that this exemplar model does not have category extinction.

## Linking systems of difference sets

A linking system of difference sets is a collection of mutually related group difference sets, whose advantageous properties have been used to extend classical constructions of systems of linked symmetric designs. The central problems are to determine which groups contain a linking system of difference sets, and how large such a system can be. All previous results are constructive, and are restricted to 2-groups. We use an elementary projection argument to show that neither the McFarland nor the Spence construction of difference sets can give rise to a linking system of difference sets in non-2-groups. We then give a new construction for linking systems of difference sets in 2-groups, taking advantage of a previously unrecognized connection with group difference matrices. This construction simplifies and extends prior results, producing larger systems than before in certain 2-groups and new linking systems in other 2-groups for which no system was previously known.

## An explicit correspondence between certain modular curves

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.

## Magic Eulerian Hypergraphs

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.

## Computing characteristic polynomials of matrices of structured polynomials

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.

## Algorithms for colourful simplicial depth and median in the plane

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.

## Rooted graph minors and the reducibility of graph polynomials

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.