The Northfield Undergraduate Mathematics Symposium (NUMS) is an annual event sponsored jointly by Carleton and St. Olaf. In 2016, eight students spoke at the symposium on research they did around the country over the summer.
m-gapped Progressions and van der Waerden Numbers
Daniel Lewitz (Carleton)
An m-gapped progression is a generalization of an arithmetic progression in which the gaps in the progression only need to belong to a set of $m$ elements, rather than all be the same. In the same way that arithmetic progressions pertain to the van der Waerden numbers, W(k; r), m-gapped progressions pertain to a function we call Bm(k; r). We will examine some results about the nature of the function Bm(k; r), both in general and for special case when r = 2. In particular, we will show how there are exact results for Bm(k; r) when k is relatively small. This work was done with Catherine Cooper, Trinity College; Alex Stoll, Clemson University; and Bruce Landman, University of West Georgia.
An Involution Proof of a Borwein Theorem for Overpartitions
Conrad Parker and Melanie Stevenson (St. Olaf)
In 1990, P. Borwein conjectured a + − − sign pattern for polynomials counting certain signed integer partitions. We conjecture a + − 0 pattern for the generating function for overpartitions into parts not divisible by 3 and give an involution-based proof of the 0 case of this conjecture using pentagonal numbers and the Jacobi triple product. We also share a proof of a generalization of this case involving quadratic nonresidues modulo a prime.
A Combinatorial Model of Quantum Skew Symmetric Matrices
Eleanor Campbell (Carleton)
The quantized coordinate ring of m × n Quantum matrices, or simply quantum matrices, holds deep connections to the theory of totally nonnegative matrices, wave interactions and knot theory. We examine the less understood theory of quantum skew-symmetric matrices Oq(Skn) over a field k. This algebra is known to be generated by a set of generators yi,j, 1 ≤ i < j ≤ n, which satisfy certain commutativity relations dependent on some element q k. We view Oq(Skn) from a combinatorial perspective. We prove Oq(Skn) is isomorphic to an algebra called An over k, defined graphically. An is generated by elements xij, where each xij is the sum of the weights of paths from i to j in a particular directed graph. The weights are obtained from elements of a space with simpler commutativity relations dependent on q. Using inductive methods on the graph, we prove that the generators of An satisfy the same commutativity relations of Oq(Skn), allowing for a new combinatorial perspective that may be used to study this algebra.
Partial Differential Modeling in the Kidney
Quinton Neville (St. Olaf)
The kidney, a diverse and complicated biological system, is most simply charged with the production of urine. At a deeper level, the functional unit that facilitates this process is the nephron. The nephron utilizes the Tubuloglomerular Feedback (TGF) System to monitor chloride levels during the production of urine, making sure the body is not retaining or losing too much. In mammals, there are two types of nephrons: short-looped and long-looped. The key difference between the short-loop and the long-loop is the existence of the Thin Ascending Limb (THAL) in the long-loop, which has differing properties for spatially varying permeability and maximum transport rate of chloride. Additionally, there is biological evidence of an association between desert mammals’ ability to produce more highly concentrated urine and a higher percentage of long-looped nephrons in their kidneys. The long-looped nephron, however, is not well characterized biologically, which provides motivation to attempt to explain this association mathematically. Thus, we developed a partial differential model of a long-looped nephron, derived a characteristic ordinary differential equation, varied the length of the model THAL, and performed a bifurcation analysis of the long-looped TGF system. Our analysis indicates that there is a higher tendency towards oscillatory solutions in the long-looped TGF system than in the short-looped, and increasing the length of the THAL may create a more stable TGF system.
Finding Minimal Spanning Forests in a Graph
Abdel-Rahman Madkour and Philip Nadolny (St. Olaf)
In the computation of multidimensional persistent homology, a popular tool in topological data analysis, a family of planar graphs arises. We have studied the problem of partitioning these graphs in a way that will be useful for parallelizing the persistent homology calculation. Specifically, we desire to partition an edge-weighted, undirected graph G into k connected components, G1, . . . , Gk. Let wi be the weight of a minimum spanning tree in component Gi. For our purposes, an ideal partition is one that minimizes max{w1,…,wk}. This problem is known to be NP-hard in the case of general graphs and we are unable to find this specific problem in the graph partitioning literature. We propose two approximation algorithms, one that uses a dynamic programming strategy and one that uses a spectral clustering approach, that produce near-optimal partitions in practice on a family of test graphs. We present detailed descriptions of these algorithms and the analysis of empirical performance data.
The Metric s-t path Travelling Salesperson Problem and the Randomized Christofides Algorithm
Shatian Wang (Carleton)
In the well-known metric Traveling Salesman Problem (metric TSP), a complete graph G= (V, E) is given with nonnegative metric edge costs. The goal is to find a Hamiltonian circuit in G with minimum cost. The Christofides heuristic (1976) gives a nice purely combinatorial 1.5-approximation algorithm for the metric TSP. An important variant of the metric TSP is the metric s-t path TSP, in which two fixed vertices, s and t are given, and the goal is to find a min-cost Hamiltonian path from s to t.
The Christofides heuristic can be easily extended to this s-t path variant, but only with an approximation ratio of 5/3. An, Kleinberg and Shmoys (2012) made the first improvement to 5/3 with an LP based algorithm, the randomized Christofides algorithm, and achieved an approximation ratio of 1.618. This LP based analysis has inspired a sequence of later breakthroughs, including an 1.6 bound by Sebo (2013) and an 1.566 bound by Gottschalk and Vygen (2016). If time permits, a more general problem, the connected T-join problem, will be discussed at the end of the talk.