## About Summit

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

Receive updates for this collection## On the volume of the Birkhoff polytope

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.

## On the cogrowth series of free products of finite groups

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.

## The minimax linear fractional programming problem with binary variables

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.

## From eigenbeauty to large-deformation horror

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.

## The maximum weight stable set problem with a budget constraint

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.

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

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.

## Brauer-Severi varieties associated to twists of the Burkhardt quartic

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.

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

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.

## Cops and robbers on Cayley graphs and embedded graphs

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.

## Colouring complexes of planar triangulations and the line graphs of cubic graphs

In order to study the parity of a k-colouring, Tutte introduced the notion of a k-colouring complex in 1969. Given a k-colourable graph X, the k-colouring complex Bk(X) is the graph which has all the independent sets which are colour classes of X as its vertices and two vertices A and B in V (Bk(X)) joined by an edge if the colour classes A and B appear together in a k-colouring of X. Subsequently, Fisk proved that the graph Bk(X) is k-colourable and discovered infinite families of graphs for which Bk(Bk(X)) is isomorphic to X. In this thesis, we resolve a question Tutte posed about the 4-colouring complex at one of his final public lectures in 1999. He asked whether the 4-colouring complex of a planar triangulation could have two components in which all colourings have the same parity. In response, we construct triangulations of the plane whose 4-colouring complexes have arbitrarily many even and odd components. Furthermore, we exhibit an infinite family of 4-connected triangulations of the plane whose 4-colouring complexes have an arbitrarily large number of even components, as well as a number of 5-connected triangulations of the plane whose 4-colouring complexes have at least two components in which all colourings have the same parity. In the later chapters of this thesis, we continue our study of the k-colouring complex, discovering many new infinite families of graphs X for which Bk(Bk(X)) is isomorphic to X. We call these graphs reflexive graphs. Most notably, if G is a 3-edge-colourable, connected, cubic (possibly including half-edges) outerplanar graph, we prove that L(G) is reflexive if and only if G is triangle-free. In order to establish this result, we show how to reduce questions about the reflexivity of a connected graph to questions about the reflexivity of its 2-edge-connected components. Then we determine conditions under which subdividing an edge preserves reflexivity. These two novel theorems are of independent interest. In particular, we apply the latter theorem to prove that theta graphs have reflexive line graphs.