CMU Mathematics Summer Undergraduate Research Fellows, 2017
Projects:
- On the Sprague-Grundy Values of Auxiliary-Nim, Matthew Bowen
Advisor: Wesley Pegden
Abstract: In 2015 Boros et. al. introduced the game $\textit{extended complimentary nim}$, a generalization of the classic game of Nim played on $n+1$ heaps as follows: on a player's turn they can reduce up to $n-1$ of the first heaps and may reduce the extra heap whenever it is non-empty. While they gave a complete characterization for the Sprague-Grundy function of this game in the case where $n\geq 3$, they noted that the $n=2$ case "behaves in a chaotic way" and provided only partial results and conjectures. In this paper we prove these conjectures and related results. In addition, we introduce and analyze a natural generalization, the game $\textit{auxiliary nim}$, a game played on $n+1$ heaps where on their turn a player can either reduce any one heap or reduce both the first 'auxiliary' heap as well as any one additional heap. Equivalently, this is the game $NIM_\mathcal{H}$ where $\mathcal{H}=\{\{1\},...,\{n\}, \{1,2\},\{1,3\},...\{1,n\}\}$. - Large equiangular sets of lines, William Cooperman
Advisor: Boris Bukh
Abstract: A set of lines through the origin in a $d$-dimensional space is equiangular if the angle between any pair of lines is the same. We study the largest known equiangular set of $\frac{2}{9} (d+1)^2$ lines and consider generalizations which yield large matrices of low rank with few distinct entries. The construction is based on the Kerdock code, an error-correcting code first published in 1972. Along the way, it proves helpful to study quadratic forms in characteristic 2. - Index fund with PCA and Factor Model, Xinhui Guo
Advisor: David Handron
Abstract: An index fund is a mutual fund or exchange-traded fund that tracks a specific set of stocks. It is a very important instrument in the finance world: lots of people invest in indices like S&P 500, but note that index itself is not traded in the exchange, so the only way to actually invest in S&P 500 is to buy all 500 stocks. But commission fees and numerous transactions give people a headache. In this research, PCA is applied to reduce the dimensional complexity of an index. First, correlation matrix of stocks is estimated using their historical price. Then, find the eigenvalues and eigenvectors of the matrix, from where the stock with the least information about the index could be figured out. Keep eliminating stocks until all remaining stocks carry decent information about the index. Thirdly, factor model is applied to find the weights of the stocks in the index fund. This research also discusses optimal rebalancing period and parameters for specific indices. - Building and Calibrating a Binomial Asset Pricing Model to Reflect Market Data, Shuailin He, Huiwen Zhang
Advisor: David Handron
Abstract: In this research, we build a binomial asset pricing model with which we obtain a relatively accurate price of a derivative security: options. We introduce two methods for parametrizing the model and assess the accuracy of the resulting predictions. We also work on optimizing the algorithm to find the best parameter values, by balancing between accuracy and efficiency, to make sure it works well given real data. Furthermore, we make choices from the market data. We make sure that the data we use to calibrate the model is representative and thus we can get a relatively accurate model. The model is coded in Python. With this model, we are able to predict the market price of an option given its strike price and then can identify those mispriced options in the real market. - The Longest Common Subsequence in Shifted Words, Raymond Hogenson
Advisor: Boris Bukh
Abstract: Given two random finite sequences from $[k]^n$ with the property that a prefix of the first sequence is the suffix of the second, we examine the length of their longest common subsequence (LCS). If $\alpha$ is the length of the overlap, we prove that the expected length of the LCS is asymptotic to $\max (\alpha, E[L_n])$, where $L_n$ is the LCS between independent random sequences. We also demonstrate tail bounds for this value. - A new planar graph with lazy cop number greater than three, Serhan Kiliccote
Advisor: David Offner
Abstract: Cops and Robber is a two-player game played on graphs where a team of cops try to catch a robber. The cops and robber take turns moving along edges of the graph, and if the cops can land on the same vertex as the robber, the cops win, otherwise the robber wins. In the variant Lazy Cops and Robber, only one cop can move per turn. The minimum number of cops required to catch a robber on a graph $G$ is called the \textit{cop number} of the graph and denoted $c(G)$. Similarly, the minimum number of lazy cops required to catch a robber on a graph $G$ is called the Lazy Cop number and is denoted $c_{L}(G)$. Aigner and Fromme proved that if $G$ is a planar graph, then $c(G) \le 3$. Recently, Gao and Yang showed show that Aigner and Fromme's result does not hold in the lazy cop variant by constructing a planar graph $G$ with $c_L(G) > 3$. In this paper, we construct a different family of graphs with lazy cop number greater than three, which are simpler than Gao and Yang's. We do this by subdividing a cylindrical grid. We also prove results on the lazy cop number of subdivided grids where each edge is subdivided the same number of times and Cartesian products of graphs. - Generalized Cycle Double Covers, Nicholas Sieger
Advisor: Mary Radcliffe
Abstract: We say a collection of cycles in a graph is a Cycle Double Cover if every edge of our graph is contained in exactly two cycles in the collection. Seymour and Szekeres each conjectured that every bridgeless graph has a cycle double cover. This conjecture can be entirely expressed as a question regarding solutions to a linear equation, through which we show the existence of a generalized form of cycle cover. To transform these generalized cycle covers into cycle double covers, we build on Baker and Norine's Discrete Riemann Roch Theorem applied to the set of cycles of a graph. - On Sufficient Conditions for a measurable Function to be Constant, Michael Spoerl
Advisor: Giovanni Leoni
Abstract: The study of partial differential equations becomes more and more important as applications in more and more areas of physics are discovered. Solutions in the classical sense, however, are not adequate. Thus weak solutions must be considered, which are not differentiable or even continuous, but are found in Sobolev spaces. Thus, in order to better understand the field of partial differential equations, it becomes important to understand Sobolev spaces. A paper by H. Brezis gave a new characterization of Sobolev spaces and used it to find suitable conditions on measurable functions such that they must be constant. However, this paper leaves several questions unresolved. In this project, our goal is to further develop understanding of these open problems. - Towards a multicolor version of Rado's theorem, Xiaorong (Sean) Zhang
Advisor: Boris Bukh
Abstract: Rado's theorem is an important result in combinatorics. It concerns colorings of the natural numbers and finding a monochromatic solution to a system of linear equations. We investigated a similar problem: we now allow multiple sets of variables, each with its own coloring. We conjectured that the multicolor case can be reduced to the one-color case via a transformation of the equations, and we proved this conjecture for the special one-equation case. - Multi-period Portofolio Utility Optimization via Withdrawal Optimization On Multi-period Binomial Model, Yisu Zhou, Guoyi Jiang
Advisor: David Handron
Abstract: We approach the problem of optimally funding a stream of payments from a portfolio by analyzing a representative Multi-Period Binomial Model and offer an optimal solution that maximizes the weighted sum of the expected utility of the payments. We consider portfolios that invest in a risk-free asset representing a bank account and a risky asset representing an investment in a market portfolio.
We focus on a scenario where the investor is able to withdraw an arbitrary portion of the portfolio at every period, and thereafter reinvest the rest of the portfolio. Therefore, finding an optimal investment scheme in this scenario is equivalent to maximizing the sum of utilities of the withdrawals. With a predetermined utility function throughout the model, the paper offers an optimal solution that maximizes the sum of utilities of all withdrawals using Lagrange Multiplier method and concave utility functions. Results in this paper offer insight to various real-world scenarios including, but not limited to, retirement pension models and mutual funds.