## About Summit

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

Receive updates for this collection## An infinite family of Kochen-Specker sets in four-dimensional real spaces

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.

## Graph immersions

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.

## HIV epidemic control among sex workers and their clients

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.

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

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.

## Game theoretic models of clear versus plain speech

Clear speech is a speaking style intended to improve the comprehension of the hearer, which is usually due to the external noise, less ideal listening conditions, or the speaker is intended to be more intelligible. Clear speech, which exhibits increased duration, pitch, amplitude, and more exaggerated articulation, consumes more energy in order to improve the likelihood of accurate communication. To strike a balance between the cost of clear speech and the improvement it brings, we use game theory to model the phenomenon of clear speech. The conventions that speakers and hearers use to communicate are considered as equilibria in the communication game, and we need to make predictions of how the equilibria changes under the different circumstances. How our models correspond to what is experimentally observed, and what predictions are made for experimental results are discussed in the thesis. In the basic model, we study the case where the speaker has to send one of two messages equally likely in one-dimensional acoustic space. Next, we make a further discussion of the basic model in a priori probability of the sent message, the number of messages, and the conflicts between clearness and comprehensibility. The third contribution of this thesis is to extend the one-dimensional acoustic space to two dimensions, by introducing uncontrastive and contrastive features.

## Meso-swimmer suspensions: immersed boundary simulations of hydrodynamic interactions between worm-like swimmers

Hydrodynamic interaction between swimming organisms has long been a topic of interest in fluid-structure interaction. Especially, collective motion of swimming organisms such as bacteria, spermatozoa, and worms has recently received a great deal of attention from researchers in many disciplines, including biology, mathematics, engineering, food science, etc. To fully understand the collective behaviour of swimmers in dilute suspensions, near-field hydrodynamics need to be investigated. In an inertial regime, where Reynolds numbers range roughly from 0.1 to 100, and both advection and diffusion effects are present, the flow dynamics are described by the Navier-Stokes equations. We employed the immersed boundary method to couple the fluid and swimming worms (which we will refer to as meso-swimmers) in a system of integro-differential equations. We numerically examined individual, pairwise, and collective interactions of worms where phenomena such as synchronization, attraction as well as aggregation in dilute suspensions of swimmers are observed.

## Minkowski theory and rational points on hyperelliptic curves

A remarkable recent result of M.\ Bhargava shows in a certain precise sense that `most' hyperelliptic curves over $\q$ have no rational points. An object central to his proof is a certain representation $\Z^2 \otimes \Sym_2 \Z^2$ of $\GL_n(\Z)$. Elements in the set $\Z^2 \otimes \Sym_2 \Z^2$ can be viewed as a pair of $n \times n$ symmetric matrices with entires in $\z$ up to a $\GL_n(\Z)$ equivalence. Alternatively, $\Z^2 \otimes \Sym_2 \Z^2$ has an algebraic number theoretic description. By taking advantage of this property, in this thesis, we investigate $\Z^2 \otimes \Sym_2 \Z^2$ from the point of view of Minkowski theory. In particular, by assuming the hyperelliptic curve $C$ is given by $z^2 = f(x,y)$, where $f(x,y)$ is irreducible over $\q$, we gave a direct `Minkowski' style proof that a certain part of the set $\Z^2 \otimes \Sym_2 \Z^2$, which contains the elements arising from the rational points on $C$, is finite. Although, our main principle of proof mirrors the classical proof of finiteness for the class number of a number field, we develop new arguments when there exist some notable differences, and we strive to give self-contained proofs of some of the components of Bhargava's paper which we utilize.

## Computing polynomial greatest common divisors using sparse interpolation

Computing polynomial greatest common divisors (GCD) plays an important role in Computer Algebra systems because the GCD operation is the bottleneck of many basic applications. For example, to simplify a rational function one divides the numerator and denominator by their GCD. In 1988 Ben-Or and Tiwari introduced the first deterministic polynomial interpolation algorithm which accounts for sparsity. The number of evaluation points needed by the Ben-Or/Tiwari algorithm is linear in the number of non-zero terms in the target polynomial, and moreover, all variables can be interpolated simultaneously hence parallelizing the algorithm is easier. In this thesis, we present modular multivariate polynomial GCD algorithms based on Ben-Or/Tiwari sparse interpolation. They compute the GCD modulo one or more primes. We apply a Kronecker substitution to reduce the number of variables and we modify the Ben-Or/Tiwari evaluation point sequence so that we can use primes of acceptable size (machine primes) as well as gain randomness on the choice of evaluation points to avoid several known issues in polynomial GCD algorithms. Based on several assumptions, we first present a simplified algorithm for GCD computation in Z[x1, . . . , xn] from which we derive some theoretical bounds and convince the reader why it works. Then we present a practical version of the algorithm where those assumptions are dropped. This leads to a more complicated algorithm but it can be shown that it always terminates and it computes the GCD efficiently. In the 1980s, subsequent research in polynomial GCD algorithm mainly focused on polynomials over number fields. In this thesis, we also present a GCD algorithm for multivariate polynomials in Q(_)[x1, . . . , xn] where _ is an algebraic number. With a prime modulus p, all operations are performed in the finite ring Zp(_) where inversions may fail due to zero divisors. We manage to get all necessary bounds to support the correctness of our algorithm.

## Swarm equilibria in domains with boundaries

This thesis involves the study of a well-known swarming model with interaction and external potentials in one and two dimensions. We refer to this model as the plain aggregation model and later study the model with nonlinear diffusion, so-called the diffusive model here. Typically set in free space, one of the novelties of this thesis is the study of such swarming models in the presence of a boundary. We consider a no-flux boundary condition enforced in a particle context via a ``slip'' condition. Of particular relevance to the context of this thesis, the swarming model used here can be formulated as an energy gradient flow and thusly, one might expect equilibrium states to be minima of the energy. In this work we demonstrate, through both analytical and numerical investigations, a continuum of equilibria of the plain aggregation model that are not minima of the energy. Furthermore, we show that these non-minimizing equilibria are achieved dynamically from a non-trivial set of initial conditions with a variety of interaction potentials and boundary geometries. Thus we show conclusively a deficiency with the plain aggregation model in domains with boundaries, namely that it appears to evolve into equilibria that are not minima of the energy. Following this we then propose a rectification to this deficiency in way of nonlinear diffusion. This choice of nonlinear diffusion is especially attractive because it preserves compact states of the plain aggregation model. We showcase how the diffusive model approaches, but does not equilibrate at, the non-minimizing equilibria of the plain aggregation model. Furthermore we demonstrate how minimizers of the diffusive model do approach minimizers of the plain aggregation model in the zero diffusion limit.

## Genome rearrangement problems accounting for duplicate genes

We investigate certain genome rearrangement problems studied in relation to genome evolution. We introduce the SCJ-TD-FD rearrangement model to explain the directed evolution from an ancestor A to a descendant D, where D may contain multiple copies of genes from A. We study the pairwise genome distance problem that aims at finding the most parsimonious sequence of cuts, joins and single-gene duplications that transforms A to D, under this model. Next, we study the rooted median problem under the SCJ-TD-FD model, for which the problem is shown to be NP-hard. We provide an Integer Linear Program that, on simulated data, predicts an optimal median with high accuracy. Finally, we study the Small Parsimony Problem under the SCJ-TD-FD model that aims at finding the gene orders at the internal nodes of a given species tree. We define an ILP-based approach to reconstruct the ancestral gene orders and present our experiments on a data-set of Anopheles mosquito genomes.