2023 REU Projects
Project 23.01: Network Reliability Parameters
We often model networks using graphs and the ability for a network to remain operational is extremely important. Assume a network remains operational as long as it has some property P. An important measure of network reliability is finding the minimum number of vertex failures, edge failures, or both, which render the network inoperable. In this project we will consider different properties P as well as different graph classes and find the network reliability measure associated with the property P. Different properties already of interest include connectivity, component order, and diameter. This work has applications in communication networks, computational networks, social networks, electrical networks, and of recent importance, epidemiology. Computational methods can be used to approximate solutions for large networks, generate sequences to help develop conjectures, and visualize failure states to better understand the problem.
Project 23.02: Smith Normal Forms of Permutation Incidence Matrices
For integers t, k, and n with 0 ≤ t ≤ k ≤ n, let Wtk or Wtk(n) denote the matrix whose rows are indexed by the t-subsets of an n-set X, whose columns are indexed by the k-subsets of X, and where the entry in row A and column B is Wtk(A,B) = 1 if A is a subset of B. The Smith normal form of these incidence matrices are well-studied with numerous applications. There have also been plenty of investigations on the q-analogue. In this project, we consider the symmetric group analogue. For m ≤ n positive integers, any permutation σ in the symmetric group Sm and 𝜏 in Sn, we say σ is embedded in 𝜏 if the sequence (σ(1),σ(2),...,σ(m)) is a subsequence of (𝜏(1),𝜏(2),...,𝜏(n)). Let A be an m! x n! matrix such that the rows are indexed by Sm, the columns by Sn, and the entry is given by A(σ,𝜏) = 1 if σ is embedded in 𝜏. This project will compute the Smith normal form of A. This may also give rise to zero-sum Ramsey results on permutations graphs, as seen in some work in the literature utilizing computational methods in discrete mathematics.
-->
Project 23.03: Impartial Two-Player Graph Pebbling Games
Graph pebbling is a mathematical game played on a finite, simple graph G in which zero or more “pebbles” are assigned to each of the graph’s vertices. For integers a > b > 0, an (a,b) pebbling move consists of removing a pebbles from a vertex v of G while adding b pebbles to a vertex adjacent to v. An impartial two-player game is a mathematical game in which allowable moves depend only on the position and not on which of the two players is currently moving. Several problems offered this summer will concentrate on variations to impartial two-player graph pebbling games. For example, one problem might consider strategies associated with altering the rules of a pebbling move, perhaps for integers a, b, c > 0, a > b + c, pebbling move (a,b,c) is where a pebbles are removed from one vertex v, b pebbles are placed on an adjacent vertex u, and c pebbles are placed on a second distinct vertex w.
Project 23.04: Generalized Toggle on Finite Simple Graphs
The game of Toggle is the umbrella game for two variants, Batel and BaoWei. Played on a standard chessboard (i.e., an 8 by 8 lattice), each piece has two distinct sides. Batel is a race to be the first to occupy your opponent’s home row. BaoWei has a capture mechanic. This project will study generalizations on the game of Toggle by playing the game on a finite simple graph and exploring variations on toggle moves.
Project 23.05: Questions Involving Digital Sums
Let b>2 be an integer. For a positive integer n, let sb(n) be the sum of the digits of the base b expansion of n. In this proposed project, we will investigate the sequence of integers satisfying gcd(n,sb(n))=1. Directions of investigation may include determining the maximum length of an arithmetic progression of these numbers and the intersection of these numbers with other sequences and integers.
Project 23.07: Peg Duotaire
Peg solitaire is a game played on a board containing a pattern of holes, all but one of which start containing a peg. The triangular pattern board is well-known to patrons of Cracker Barrel. One peg can be moved to an open hole, jumping a single peg. The peg that is jumped is then removed. The object of the game is to make some sequence of jumps so that there is a single peg remaining. The pattern of holes can be modeled using a graph and admissible jumps can be thought of as moving a peg from one vertex to another so long as the vertices share a neighbor.
Peg duotaire is a two-player, impartial variation of peg solitaire. In duotaire, two players alternate making jumps. The last person to make a valid jump wins. The conditions in which the first player has a winning strategy are known for several classes of graphs. This project will consider several variations of peg duotaire including misere play (last person to make a valid move loses), winning strategies for the first player when a turn consists of a sequence of jumps instead of a single jump, and a partisan variation of the game.
Project 23.08: Zero-Sum-Free Tuples
A zero-sum-free d-tuple is a vector (v1, v2, ... ,vd) in ℤnd such that the sum of any non-empty subset of its components is never 0 in ℤn. In this project, we restrict the entries of the d-tuples to certain families of residues modulo n. For example, we might restrict the entries to the squares or the Fibonacci residues modulo n. Under these restrictions, we try to classify all zero-sum-free d-tuples for a fixed d < n.
Project 23.09: Disjoint Path Cover
Given a graph G and 2k vertices {s1, s2, ... , sk, t1, t2, ... , tk} in V(G), a paired k-to-k disjoint path cover of G is a collection of k path subgraphs P1, P2, ... , Pk such that
- for each 1 ≤ i ≤ k, the endpoints of Pi are si and ti, and
- V(P1), V(P2), ... , V(Pk) form a partition of V(G).
If there is a paired k-to-k disjoint path cover for every 2k-subset of V(G), then G is said to be paired k-to-k disjoint path coverable. It is known that certain families of graphs such as hypertori exhibit such property. In this project, we will try to investigate this property for other families of graphs.
Project 23.10: A Combinatorial Approach to Pop-It and Graph Coloring
The focus of this project is the combinatorial game behind the popular Pop-It toy. A Pop-It is a silicone grid consisting of six rows of six bubbles. Now, Pop-Its come in different grid configurations and various shapes. It was initially invented as a fidget, or self-soothing toy. However, mathematicians have discovered that it was possible to play an impartial two-player, perfect information game. In the Pop-It game, two players take turns pressing consecutive bubbles. The player that presses the last bubble is the winner. The goal of this project is to determine which player has a winning strategy for the 6x6 Pop-It board and to determine the winning player for NxN Pop-It boards, MxN Pop-It boards, and/or Pop-It boards of other geometric shapes. The Pop-it game can be abstracted into a graph coloring game. We can merge the games of Pop-It and vertex coloring into a new game on the graph, called the 2-color game. Two players, Blue player (B) and Red player (R), take turns coloring the vertices of a graph using their respective color. On each turn, a player can only color vertices that are connected by an edge. Blue goes first, followed by Red. The player that colors the last vertex wins. We would like to determine the winning player for the 2-color game on different families of graphs.