2022 Projects

Project 22.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 22.02: Packing of Polyominoes

A polyomino is a plane geometric figure composed of a discrete number of squares which share edges; think tetris. Many problems related to polyominoes have been studied, particularly when it comes to counting different types of polyominoes. Polyomino types include free, one-sided, and fixed, as well as the lesser-studied convex, directed, equable, hole-free, etc. In packing polyominoes, we normally consider packing efficiently, meaning we want to find the maximum number of objects we can pack into a finite space. However, in this project, we consider the opposite which has been coined clumsy packing. In clumsy packing we are trying to fill a space with the least amount of objects so that we can not place any additional objects. Some results are known for clumsy packing of basic polyominoes, however, not much has been explored for various types of polyominoes or packing on finite boards. Clumsy packing has applications in projective geometry and number theory. Computational methods can be used to test hypotheses for small boards.

Project 22.03: Supereulerian Graphs and Maximum matching Number

Let G be a graph and let O(G) denote the set of vertices of odd degrees in G. If O(G) is the empty set, then G is called an even graph. An Eulerian graph is a connected even graph. In particular, the graph K₁ is an Eulerian graph. If a graph contains a spanning Eulerian subgraph, then it is called supereulerian. Let a'(G) be the matching number, the size of a maximum independent edge set, of the graph. Obviously every graph G has an a'(G)-matching. The circumference of G, denoted by c(G), is the length of a longest cycle of G. Previous results proved necessary and sufficient conditions for supereulerian for graphs with specific properties. Motivated by the Chinese Postman Problem, Boesch et al. proposed the problem regarding the classification of supereulerian graphs: determine when a graph has a spanning Eulerian subgraph. It turned out that this is a difficult problem, as Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. This project considers the problem: Let G be a graph with k'(G) ≤ 2 and a'(G) ≤ 4. Determine the collection of graphs such that G is supereulerian if and only if G is not contractible to a member in this collection.

Project 22.04: Properties of 2-Properly Colored Graphs

A coloring c given to a graph G is a proper vertex coloring of G if c(u) ≠ c(v) for all adjacent vertices u and v in V(G). Properly colored graphs have generated many questions and interesting results. We consider one modification of a proper vertex coloring. Define a 2-proper vertex coloring of G to be a vertex coloring c on k colors such that c(u) ≠ c(v) for all vertices u and v in V(G) with d(u,v) = 2. Not all graphs can be given a 2-proper coloring with only two colors. One goal is to determine the minimum number of colors needed to give a graph a 2-proper coloring and to compare this value to the graph's chromatic number. A related question of interest is to consider how the vertex coloring game is affected under the restriction of a 2-proper coloring. Two players take turns coloring uncolored vertices of a graph from a set of k colors. Player 1 wins if the process results in a properly colored graph and Player 2 wins if it is impossible to color at least one of the vertices in a way that yields a proper coloring. The game chromatic number is the minimum number of colors for which it is possible for player 1 to win the game. Another project goal is to determine the game chromatic number of 2-properly colored graphs and to study how this value compares to the original game chromatic number.

Project 22.05: Smith Normal Forms of Permutation Incidence Matrices

For integers t, k, and n with 0 ≤ t ≤ k ≤ n, let W_tk or W_tk(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 W_tk(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 S_m and 𝜏 in S_n, 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 S_m, the columns by S_n, 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 22.06: Properties of Assignment Graphs

A pebbling assignment (S_G) on a finite simple graph G is a distribution of a finite number of pebbles on the vertices of G. 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 assignment graph is a Hasse diagram whose nodes correspond to all assignments that can be reached from (S_G) by applying a sequence of pebbling moves. We investigate properties of this new class of graphs expanding the concept to digraphs and exploring various two-player impartial games in which players alternate (a,b) pebbling moves.

Project 22.07: 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 22.08: 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 22.09: Pilliai Number of Integer Sequences

Let A={a_n} be a sequence of integers. The Pillai number of A is defined to the smallest positive integer k for which there exists a subsequence S of consecutive terms of A with k elements such that every term of S has a common divisor greater than 1 with at least one other term of S. For example, every term of the set A={2184,2185,...,2200} shares a prime divisor with at least one other terms in the set. Notice that |A|=17. It is provable that any set of 16 or fewer consecutive integers contains at least one term that is relatively prime to the rest, establishing that the Pillai number for the integers is 17. In this project, we consider the Pillai number for various other integer sequences.

Project 22.10: Permutation of Point Sets

Consider a set S of n points in the plane. A choice of a vantage point p in the plane then defines an ordering O on S according to each point’s distance from p. For n>3, only a specific subset of the n! possible orderings are possible to achieve in this way. Given a set S, a vantage point p, and a desired ordering O, we ask what the minimal modification to a point in (or subset of) S is required to make O achievable.

Project 22.11: Cable-Trench Problem

Consider a graph G with vertex set V, edge set E, root vertex r, and an edge-weight map w : E → R. A spanning tree T is a subset of E which contains every vertex in V. A root path to a vertex v, in a spanning tree T, is the unique path from r to v through T.

A Minimal Spanning Tree (MST) is a spanning tree T with minimal sum of weights for all edges in T. Minimal Spanning Trees can be found efficiently with Prim’s Algorithm.

A Shortest-Path Tree (SPT) is a spanning tree T with minimal sum of weights for all root paths in T. Shortest-Path Trees can be found efficiently with Dijkstra’s Algorithm.

The Cable-Trench Problem looks for a spanning tree T which minimizes some linear combination of the two weight-functions from the MST and SPT problems. There is no currently known efficient algorithm for solving this problem. Are there certain classes of graphs/weights that we can efficiently analyze?