2020 REU Program Projects
20.01 - Network Reliability Measures Based on Size and Order
Participants: Ashley Rose Armbruster, Nicholas Hanson, Jieqi Di, Jose Arbelo
Mentors: Nate Shank
Summary of project:
Assume a network can be represented by a graph G with vertex set V and edge set E. The network is operational as long as the graph maintains some property P. The network reliability measures how quickly a network loses property P. Often vertices fail, or edges fail, or both. Often we use this information backwards; meaning we want to construct a network with maximum reliability relative to property P, however we are restricted by the number of vertices and edges in the graph. Given n vertices, m edges, and property P, what graphs will produce the most (and least) reliable networks? The aid of computers allows us to experiment with small values of n and m in order to make conjectures.
Results:
Network reliability models generally have two items which can vary from model to model. The first is the conditions which determine if a network is in a failure state and the second is what items in the network are prone to failure (vertices, edges, both). The group of Ashley Armbruster (Frostburg State University), Nicholas Hanson (University of Minnesota), Jieqi Di (Boston College) and Jose Arbelo (Northampton County Community College) chose to define a network to be in a failure state if all components had order less than some proportion of the original order. They also considered two cases of failures; vertices and edges. Results for several graph classes include paths, cycles, trees, complete, and complete binary were found as well as some bounds for graphs with a fixed size and order.
20.02 - Diameters Restricted Polyominoes
Participants: Mitchel L O'Connor, Emma Miller, Peter Kanjorski
Mentors: Nate Shank
Summary of project:
A polyomino is a plane geometric figure which is made up of square cells which are joined along an edge. Polyominoes are classified by the number of cells (n) present in the polyomino. For example, the classic game of tetris uses polyominoes where n=4. There are many different types of polyominoes including free (OEIS A000105), free with holes (OEIS A001419), one-sided (OEIS A000988), and fixed (OEIS A001168). In this project we will consider the diameter restricted polyominoes where the diameter, as in graph theory, is the maximum shortest distance between two cells. We will try to count the number of polyominoes with a fixed number of cells (n) and a fixed diameter (d) as well as investigate other properties of diameter restricted polyominoes.
Results:
Polyominoes are plane geometric figures made from squares joined along their edges. An example of a size 4 would include the pieces in a game of tetris. The group consisting of Mitchel O’Connor (Whitman College), Emma Miller (91pornÔ´´) and Peter Kanjorski (Kutztown University) considered the clumsy packing problem in a finite space. Clumsy packing involves placing polyominoes into a board so that you use the least amount of pieces so that no additional piece can fit into the board without overlapping the other pieces. Partial results were obtained for straight pieces, L pieces, T pieces, and + pieces where the pieces were placed onto a finite size board.
20.03 - Covering Systems
Participants: Ashley Rose Armbruster, Emily M Eckard, Tyler J Dvorachek, Grace Barger, Yewen Sun, Sofya Bykova, Kyree Generett
Mentors: Josh Harrington, Tony Wong
Summary of project:
A covering system of the integers is a collection of congruences such that every integer satisfies at least one congruence in the collection. In this project we will investigate the existence of certain types of covering systems and their relationship to Sierpinski numbers.
Results:
A covering system of the integers is a collection of congruences so that every integer satisfies at least one congruence in the system. Covering systems have been used to show the existence of integers with certain properties. In this project, team members Ashley Armbruster (Frostburg State University), Grace Barger (Salem College), Sofya Bykova (Cornell University), Tyler Dvorachek (University of Wisconsin-Green Bay), Emily Eckard Mount St. Mary’s University, and Yewen Sun (University of California, Santa Barbara) worked with mentors Joshua Harrington (Cedar Crest College) and Tony Wong (Kutztown University of Pennsylvania) to prove the existence of infinitely many Sierpinski numbers and Riesel numbers as binomial coefficients through applications of covering systems. In particular, they showed that the set of values of r for which there exist infinitely many Sierpinski numbers of the form k=xCr has asymptotic density 1. A similar study was also performed on Riesel numbers.
20.04 - Fibonacci Polynomials
Participants: Lindsey M Wise, Emily M Eckard, Cameron Lee Byer, Tyler J Dvorachek
Mentors: Josh Harrington, Tony Wong
Summary of project:
Let F_1(x)=1 and let F_2(x)=x. The n-th Fibonacci polynomial is defined by F_n(x)=xF_{n-1}(x)+F_{n-2}(x).
Results:
Fibonacci polynomials are defined recursively in the following manner:U0(x)=0and U1(x)=1, and for all n2, Un(x)=Un-2(x)+xUn-1(x). The n-th fibotomic polynomial is defined as the primitive factor of the n-th Fibonacci polynomial. In this project, team members Cameron Byer (Eastern Mennonite University), Tyler Dvorachek (University of Wisconsin-Green Bay), Emily Eckard (Mount St. Mary’s University), and Linsdey Wise (Appalachian State University) worked with mentores Joshua Harrington (Cedar Crest College) and Tony Wong (Kutztown University of Pennsylvania) to study various properties of the fibotomic polynomials. Their investigation includes a formula for the discriminant of the n-th fibotomic polynomial, as well as the factorization of fibonomic polynomials modulo a prime. Properties analogous to the well-known cyclotomic polynomials were also investigated.
20.05 - Maximum Distance for Latin Square
Participants: Mitchel L O'Connor, Paige Genevieve Beidelman, Omar Aceval, Jieqi Di, Yewen Sun
Mentors: James Hammer
Summary of project:
For an integer n, an n x n array is a latin square if every row and every column has symbols 1 through n exactly once. Two cells are said to be adjacent if they share an edge (that is to say, two cells are adjacent if they are next to each other either vertically or horizontally). Let u and v be symbols in two adjacent cells. We say that the distance between these two cells is |u-v|. In the same vein, a distance function can be defined on the latin square as the minimum distance between any two cells. What is the maximum distance that a latin square of order n can be?
Results:
The inner distance of a Latin square is defined as the minimum difference between symbols in adjacent cells. In this project, team members Omar Aceval (University of Texas), Paige Beidelman (University of Mary Washington), Jieqi Di (Boston College), Mitchel O’connor (Whitman College), and Yewen Sun (University of California, Santa Barbara) worked with mentors James Hammer (Cedar Crest College) and Caitlin Owns (DeSales University) to study the inner distance of a general nXn Latin square. In particular, they found that the inner distance of an nXn Latin square is given by the floor of (n-1)/2. They also extended their study to investigate (a,b)-Sudoku Lain squares.
20.07 - Strong Proper Connection Number
Participants: Paige Genevieve Beidelman, Jonathan Tyler Moore, Johnna Ann Farnham, Jelena Mojsilovic, Emma Miller
Mentors: Caitlin Owens
Summary of project:
An edge coloring of a graph is a proper edge coloring if incident edges are colored with distinct colors. A properly colored path in a graph is a path such that the edges of the path are properly edge colored. A graph, with an edge coloring, is said to be properly connected if there is a properly colored path between every pair of vertices. The proper connection number of a graph is the minimum number of colors required for an edge coloring to have so that the graph is properly connected. In this project, we will investigate the strong proper connection number of a graph, the minimum number of colors required to color the edges such that there exists a shortest path between every pair of vertices which is properly colored.
Results:
The strong proper connection number of a graph is the minimum number of colors it takes so that between every two vertices, there exists a properly colored path.. In this project, team members Paige Beidelman (University of Mary Washington), Johnna Farnham (Western New England University), Rob Lorch (Grinnell College), Emma Miller (91pornÔ´´), Jelena Mojsilovic (Illinois Institute of Technology), and Jonathan Moore (Rowan University) worked with mentors James Hammer (Cedar Crest College) and Caitlin Owens (DeSales University) to determine the strong proper connection number of cycles, free graphs,, paths, and multigraphs.
20.08 - Structural Results for 1HP on Cographs
Participants: Jonathan Tyler Moore, Johnna Ann Farnham, Xiangyi Tao, Arthur Bernardo
Mentors: Caitlin Owens
Summary of project:
The Hamiltonian path problem is a well-known NP-complete graph theory problem which is to determine whether or not it is possible to find a path through all the vertices of a graph, visiting each vertex exactly once. A variation on this problem is the 1HP problem which is to determine, given a graph and a vertex in the graph, whether or not it is possible to find a Hamiltonian path in the graph which has the specified vertex as an end of the path. The problem is also NP-complete for graphs in general, though like the Hamiltonian path problem, 1HP can be polynomially solvable on certain types of graphs. Cographs is a class of graphs for which the problem is known to be polynomially solvable. In this project, we will investigate whether there are structural properties of cographs which can determine whether or not there is a Hamiltonian path which has an end at a given vertex.
Results:
20.09: Addressing Graphs & Pebbling
Participants: Jelena Mojsilovic, Sofya Bykova, Xinyi Fan, Rey Anaya
Mentors: Eugene Fiorini
Summary of project:
A t-address is a t-tuple with entries in {0,a,b}. An addressing of length t for a graph G is an assignment of t-addresses to the vertices of G so that the distance between two vertices is equal to the number of locations in the addresses at which one of the addresses equals a and the other address equals b. Bell Lab mathematicians Graham and Pollak introduced such addressings in the context of loop switching networks. Let N(G) be the minimum t for which G has an addressing of length t. Determining N(G) in general is believed to be NP-hard. This project will examine N(G) for certain families of graphs, such as generalized Petersen graphs, Kneser graphs, and bipartite graphs.
Results:
The team presented at the Ohio State University Young Mathematicians Conference.
Title: Optimal Addressing Schemes for Subfamilies of Block Graphs and Related Graphs
Presenters: Sofya Bykova and Xinyi (Cynthia) Fan
Date: 14 - 16 August 2020
Location: Ohio State University Young Mathematicians Conference (online)
Abstract: Graham and Pollak introduced the concept of a $t$-addressing of a graph as it applied to message routing in communication networks. A length $t$ addressing of a graph $G$ is a labelling of the vertices of $G$ by $t$-tuples consisting of the symbols $a,b,0$ such that the number of positions at which corresponding entries of their labels are distinct and nonzero equals the distance between the two labeled vertices. For a simple graph $G$, an optimal addressing $N(G)$ is the minimum $t$ for which there exists a $t$-addressing of $G$. It has been shown that $h(D)\leq N(G) \leq |V(G)| - 1$, where $h(D)$ is the maximum of the number of positive and negative eigenvalues for the distance matrix $D$ of $G.$ An addressing is said to be eigensharp if $N(G)=h(D)$. In this talk, we identify several families of eigensharp graphs including various subfamilies of block graphs, prism graphs, and torus graphs. We also show the optimal addressing scheme for additional graph families such as flower graphs, spider graphs, wheel graphs, and stacked prism graphs.
We are preparing a paper (same title as above) for submission. It will be submitted this fall in the next couple of months, probably around October or November.
20.11: Host-Parasitoid Population Dynamic Modeling
Participants: Grace Barger, Xiangyi Tao, Xinyi Fan, Denavio Cortez Leeks
Mentors: Brooks Emerick
Summary of project:
A parasitoid is an organism that spends most of its life cycle attached to or inside the host. Unlike an actual parasite, the parasitoid eventually kills the host. During a particular season of the year, known as the vulnerable period, the parasitoid injects eggs into the host larvae. Parasitoid larvae, then, emerge from the host, effectively killing it. Early models of this phenomenon include the discrete-time Nicholson-Bailey model, which is known to be unstable i.e. coexistence is impossible. In this project, we'll implement relevant changes during the vulnerable period using a semi-discrete framework that includes migration dynamics on a patch network. What characteristics about the network will yield coexistence of the two species? Does density dependent migration make a difference? Can we construct a similar model for hyper-parasitoids i.e. parasitoids that prey on parasitized host larvae? The project will employ model simulation in Matlab, numerical and qualitative analysis of ODE systems, and stability analysis of a discrete dynamical system.
Results:
The group consisting of Grace Berger (Salem College), Xiangyi Tao (Lehigh University), Xinyi Fan (Davidson College), and Denavio Cortez-Leeks (Harrisburg Area Community College) were presented three potential problems which included a model for parasitoids ovipositing in infected host larvae, a model for migration of multiple parasitoid populations on a network of patches, and a model to describe a hyper-parasitoid dynamic. The group focused on the hyper-parasitoid model. They created two models: synchronous and asynchronous attack by parasitoids and hyper-parasitoids. In the synchronous model, they showed that a constant attack rate in both parasitoid species yields unstable results. The same holds for the asynchronous model. The group then proved that a stable equilibrium exists if at least one parasitoid species has a functional response in the attack rate for the synchronous model. For the asynchronous model, a more relaxed condition holds for the functional response attack rates, which means coexistence of all three populations is possible for a wider range of parameter values.
20.12: Projective planes/Latin square
Participants: Lindsey M Wise, Omar Aceval, Cameron Lee, Nicholas Hanson
Mentors: Eugene Fiorini
Summary of project:
An algebraically defined graph $\Gamma_{\mathcal{R}}(f(x,y))$ is constructed using a specific ring $\mathcal{R}$ and function $f(x,y)$. These graphs are bipartite with each partition set consisting of all coordinate pairs in $\mathcal{R}^2$. The vertices of the partition classes are represented by $(a_1,a_2)$ and $[x_1,x_2]$, respectively. Two vertices are joined $(a_1,a_2)$ and $[x_1,x_2]$ are adjacent if and only if their coordinates satisfy the equation $a_2 + x_2 = f(a_1,x_2)$. Recent research has focused on the classification of functions $f(x,y)$ that identify the properties, such as girth, of the associated bipartite graph. This project studied the relationship between Latin squares and algebraically defined graphs over finit fields. For instance, if $p$ is prime, what can be said about the matrix of values $[f(x_i,x_j)]$, where $x_i,x_j \in \mathbb{F}_p$, and the associated algebraically defined graph?
Results:
The group has also submitted a sequence to the Online Encyclopedia of Integer Sequences. It is currently under review. The sequence is:
The maximum number of 3 by 3 Latin subsquares in an n by n Latin square.
20.13: Incidence Geometry
Participants: Jose Arbelo, Arthur Bernardo, Denavio Cortez Leeks, Kyree Generett, Peter Kanjorski
Mentors: Tony Wong, Brian Kronenthal
Summary of project:
This project studies algebraically defined graphs and their properties. Algebraically defined graphs are motivated by finite incidence geometries. Common finite incidence geometries include projective planes, affine planes, and generalized quadrangles. Algebraically defined graphs and finite incidence geometries are related to many different areas of mathematics, such as graph theory, combinatorics, design theory, abstract algebra, linear algebra, and mathematical games.
An algebraically defined graph contains two partite sets, and the vertices in each partite set are indexed by $\mathbb{F}^n$. A vertex from one partite set is connected to another vertex in the opposite partite set if the corresponding two coordinates satisfy some predefined equations. One of the major questions in this area of mathematics is to classify algebraically defined graphs up to isomorphism.
There are a number of different strategies for determining whether two graphs are isomorphic. One of them is to compare their intrinsic properties, such as the girth of the graphs, i.e., the length of the shortest cycle in the graphs. Other techniques include counting the number of certain subgraphs. This summer, we determined a formula to enumerate the number of complete bipartite graphs $K_{s,t}$ that are embedded in three-dimensional monomial graphs over finite fields, thus providing a necessary condition for these algebraically defined graphs to be isomorphic. This project is within the realm of proof-based theoretical mathematics, but we also utilized computer programs as a major aid to formulate conjectures and verify answers.
Results: