2021 REU Program Projects

21.01 Network Reliability Measures Based on Size and Order

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.

21.02 Random Race

Alice and Bob take turns to collect chips in the following manner. In each turn, Alice tosses a fair coin, which decides whether she collects a or b chips, where a and b are positive integers. If Alice collects a chips, then Bob collects b chips, and vice versa. Alice wins if her total number of chips is divisible by n and Bob wins if his total number of chips is divisible by m. In this project, we study the winning probability of each player.

21.03 Harshad Numbers

A harshad number is a number that is divisible by its digit sum. For example, 2412 is a harshad number since 2 + 4 + 1 + 2 = 9 and 9 divides 2412. In this project we study the existence of hashad numbers in various interesting sequences of positive integers

21.04 Induced H-Saturated Graphs

An induced H-saturated graph G is a non-complete graph that does not contain H as an induced subgraph, but when any missing edge e is added to G, the resulting graph G ∪ e does indeed contain H as an induced subgraph. It has been shown that there exists an induced K1,3-saturated graph on n vertices for n ≥ 12. The proof of this result involves finding a “nice” construction on 12 vertices and then creatively inserting edges/vertices into the construction so that n can grow arbitrarily large. The goal of this project would be to study this construction and to determine if it can be extended to general star graphs, K1,s
where s ≥ 4. Another goal would be to ask similar questions for other graph 1 families. For example, is it possible to find a “nice” construction that proves the existence of induced kite-saturated graphs of arbitrary size or perhaps of induced wheel-saturated graphs of arbitrary size?

21.05 Assignment Graphs

Graph pebbling is a mathematical game played on a simple graph (i.e., an undirected graph with no loops or multiple edges). A pebbling move consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex.

A pebble assignment (SG) on a finite, simple graph G is a distribution of a finite number of pebbles on the vertices of G. An assignment graph [SG] is a Hasse diagram whose nodes correspond to all assignments that can be reached from (SG) by applying a sequence of pebbling moves. Edges of [SG] adjoin any two
assignment nodes where one can be reached from the other via a single pebbling move. Assignment graphs are a relatively new concept introduced into the literature within the last two years. This project will explore some of the properties of assignment graphs as well as investigate what assignment graphs arise when the pebbling move is generalized. That is, removing a pebbles from a vertex and placing b pebbles on an adjacent vertex.

21.06 Impartial Two-Player Graph Pebbling Games

Graph pebbling is a mathematical game played on a simple graph (i.e., an undirected graph with no loops or multiple edges). A pebbling move consists of removing two pebbles from a vertex and adding one pebble to an adjacent vertex. A pebble assignment (SG) on a finite, simple graph G is a distribution of a finite number of pebbles on the vertices of G. This project will explore  the question: Under what conditions will graph pebbling be an next-player game when it is played as an impartial two-person game on a given family of graphs.

21.07 Impartial Two-Player Games on an n by n Lattice 

Let L be an n by n lattice and k < n be a positive integer. Player 1 selects a node and labels it with an integer value 1 ≤ m1 ≤ k. Player 2 must select a node within m1 of the previous node and label it with a value 1 ≤ m2 ≤ k. Player 1 must now select a node within m2 of the previous node, avoiding all previously
labeled nodes. Play continues in this fashion until no move is possible. The winner is the player who makes the last possible move. This project will explore for what values of n and k the game is a next-player game.

21.08 Algebraically Defined Graphs

An algebraically defined graph can be constructed as a bipartite graph in which each vertex is assigned an (x, y)-coordinate pair, and two vertices are adjacent when their coordinate pairs satisfy a given equation. For example, one could study a graph in which (a, b) is adjacent to [x, y] whenever b + y = a2x5 + ax3. In this project, we will be interested in the distances between vertices in these graphs, which are related to the existence of solutions to special equations (or systems of equations). We will explore how the graphs’ properties change when the coordinates are subject to different restrictions, as well as when we generalize the graphs in various ways. This project is related to areas of math such as algebra, graph theory, and incidence geometry (although no special prior knowledge is assumed or required).

21.09 Double Coco Puzzles

Double Choco Puzzles are relatively new. The goal of the puzzle is to draw borders around cells in a grid, thus creating regions that enclose a single contiguous grey shape and a single contiguous white shape of the same size. Additionally, if a region encloses a cell with the integer n, then the size of the grey shape and the white shape within the region must both be n. Finally, within any region, the enclosed grey shape and white shape must be symmetric, meaning, we can obtain one shape from the other by translation, reflection, or rotation.

The goal of this project is to study the solvability of Double Choco Puzzles. The team will start by asking this question: If we color half the cells in an n × n grid grey and the other half white and we do not include any integers, then how do we know that a solution exists? For example, there is no solution to the puzzle
shown at right above, which we refer to as “The Impossible Staircase.” This is because there is no way to draw borders so that the cell labeled X is in a region enclosing symmetric grey and white shapes. What other examples of unsolvable puzzles are there? Can we classify which puzzles are/are not solvable? Using the discoveries we make, can we define a greedy algorithm to solve these puzzles?
These questions and more await participants of “Team Double Choco”!