Proposed Projects

Project 24.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 24.02: Stabilized Legendrian Knot Mosaics

A mathematical knot can be thought of as a tangled loop of string with its ends attached. Knot diagrams can be represented in many ways and are often viewed in a 2-dimensional projection. One convenient (and beautiful) way to represent knots is by building them with a particular set of mosaic tiles. Through these "knot mosaics," invariants can be defined such as the "mosaic number," or the smallest mosaic size that can be used to build a given knot. In this project, we will explore knot mosaics for a special class of knots called Legendrian knots and investigate how a process called "stabilization" affects the mosaic number.

Project 24.03: Knot mosaics on interesting surfaces

A mathematical knot can be thought of as a tangled loop of string with its ends attached. Knot diagrams can be represented in many ways and are often viewed in a 2-dimensional projection. One convenient (and beautiful) way to represent knots is by building them with a particular set of mosaic tiles. Typically, knot mosaics are formed on a 2-dimensional square. In this project, we explore knot mosaics on other interesting identification spaces such as a Mobius band, torus, and Klein bottle. We will investigate how the "mosaic number," or the smallest mosaic size that can be used to build a given knot, changes based on the identification space chosen.

Project 24.04: Properties of Move Graphs and Related Algebraic Constructions

The main focus of this project will be the concept of a move graph G(M,n) where M is an integral matrix, referred to as the move matrix. The vertices of G(M,n) are the ordered n-tuples x = (x1,x2,...,xn) where xi ϵ Zn and the arcs are (x,Mx), x ϵ V(G(M,n)). The project will examine properties of move graphs under different move matrices. Furthermore, we will explore variations of move graphs when vertex coordinates are elements of symmetric groups other than Zn. Mathematical Fields: Graph Theory, Group Theory, Game Theory

Project 24.05: Generalized Toggle on Finite Simple Graphs

Toggle is a two-player impartial game played on a finite simple graph G. Each vertex v in G is assigned a weight of w(v) = 0 (off) or w(v) = 1 (on). A legal Toggle move consists of selecting a vertex v in G with weight w(v) = 1, switching its weight to w(v) = 0 and switching w(u) to w(u) + 1 (mod 2) for every neighbor u of v, subject to the requirement that the sum of weights of all vertices decreases. This project will examine for which graphs the game of Toggle is first-player winning (N-game) and second-player winning (P-game), as well as variations on the game of Toggle. Mathematical Fields: Graph Theory, Game Theory

Project 24.06: Zero Locus of Graphs and Hypergraphs

Let A be the adjacency matrix of a given graph G. A vector v is a null vector of A if Av=0, and the zero locus of a null vector is the set of coordinates of v such that the entries are 0. The zero locus of a graph G is then defined as the intersection of the zero loci over all possible null vectors of A. In this project, we will study the zero locus of various graphs (or hypergraphs) and their relations with other graph parameters.

Project 24.07: Extreme Covering Systems of the Integers

A covering system of the integers is a finite collection of congruences such that every integer satisfies at least one congruence in the system. When working with covering systems, it is common to restrict the moduli of the system in a variety of ways. For example, we might require all moduli to be distinct and greater than 2. In this project, we will investigate the existence (or non-existence) of covering systems with certain restrictions on the moduli. Our primary focus will be in the direction of the well-known odd covering problem and minimum modulus problem for covering systems.

Project 24.08: Variations of Peg Solitaire and Peg Duotaire on Graphs

Peg solitaire is a one-player puzzle played on a board containing a pattern of holes, all but one of which start containing a peg. The objective is to create a sequence of jumps that will result in a single peg left on the board. Peg duotaire is a two-player impartial version of peg solitaire, in which the objective is to be the last player to make a jump. These games can be played on graphs in which vertices represent the holes and edges indicate valid moves. Variations on these games offer an abundance of unsolved problems. For example, one problem might consider the winning strategies for a partisan version of peg duotaire.

Project 24.09: Knight Domination on Hexagonal Boards

It is an age old question of how many queens can be placed on a chess board so that every square is being attacked by at least one queen. In graph theory terminology, this is known as the domination number of the queen's graph. This has been studied on a variety of non-standard chess boards, in addition to the traditional 8x8 chess board, and for each of the five main chess pieces. To offer a fresh take on this question, consider Hex Chess, which is played on a hexagonal board made up of hexagons (a.k.a. hexagonal honeycomb board). Movement of the knights in Hex Chess can be defined in one of two ways; moving along an acute angle or moving along an obtuse angle. This project will investigate the domination number of the knight's graphs in Hex Chess.

Project 24.10: 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.