Project 17.01: Theoretical Network Reliability Measures

Consider a network or graph $G = (V,E)$ and some property $P(G)$ which must occur in order for the network to be operational. If the property $P$ is not present in $G$, then $G$ is said to be in a failure state. Different pieces of networks can fail; vertices, edges, or both. An interesting and valuable question is to try to find the most and least reliable graphs based on different properties $P$ under different failure models.

For example, if $P$ represents ``is connected,'' and edges can fail, then a network would be operational if the network is connect. However if the network is disconnected, then it is in a failure state. So we would be interested in finding the minimum number of edges to delete in order to disconnect the graph (this is also called the edge connectivity parameter).

In this project we will work with different network structures, different properties $P$ and different failure models to generate sequence based on graphs of increasing size and/or order. We will also try to find the most extreme cases for particular properties by finding the most and least reliable network structures. (See for example: A263296)

 

Project 17.02: Game Theory

Consider the following well known modification of a popular two-player game of nim:  Assume there are two piles of pebbles with $n$ pebbles and $m$ pebbles where $0 \leq n \leq m$.  We will denote this phase of the game as $(n,m)$.  On a players turn, they may remove any positive number of pebbles from one pile, OR remove an equal positive number of pebbles form both piles.  Thus we may be left with phase $(n-x,m), (n, m-y),$ or $(n-z,m-z)$ with $0 < x \leq n, 0< y \leq m$ and $0<z\leq n$.  The person that removes the last pebble wins the game.  What values of $m$ and $n$ will guarantee a winning strategy for each player? 

An additional game:   Consider a complete graph on $n$ vertices.  On a players turn, they may remove an edge as long as the resulting graph still contains a cycle.  What values of $n$ are first player win games?  What if we change the removal object or the end condition?  Can we develop results for partizan games? 

During this project, we will look at variants of these games and develop some of our own games.

 

Project 17.03: Golden Ratio and generalized continued fractions

A001622 is the decimal expansion of golden ratio $\phi$, which can be characterized as the irrational number having the simplest continued fraction expansion $\phi = [1, 1, 1, \dots]$. We will study properties of $N$-th generalized continued fraction of real numbers, which are continued fractions of denominator $N$, instead of 1 in the case of classical continued fraction expansions. After reviewing the basic set up and properties of generalized continued fractions from previous work, we will investigate some open questions in this area. In particular, we will try to answer the following question: what irrational number will have the "simplest" $N$-th generalized continued fraction?

 

Project 17.04: Pillai Labeling

A Pillai labeling of order $m$ of a simple graph $G$ is a labeling in which every vertex in every path of length $m$ has a label that is pair-wise relatively prime to the label of every other vertex in that path.  The Pillai number of $G$ is the maximum order of all Pillai labelings of $G$.  In this project we will try to find the Pillai numbers for certain families of graph.  These Pillai numbers will form integer sequences.

 

Project 17.05: Quasi Factor Pair Latin Squares

Let n be a positive integer. We define an ordered factor pair $(a,b)$ of n to be two integers $a$ and $b$ such that $a\times b = n$. An $(a,b)$-Sudoku latin square is an $n\times n$ array where every row, column, and $a\times b$ rectangle contains every symbol $1$ through $n$ exactly once if the $n\times  n$ grid is tiled by $a\times b$ rectangles in the natural way. A factor pair latin square of order $n$ is an $(a, b)$-Sudoku latin square for every factor pair $(a,b)$ of $n$. There are in nitely many values known for when there does not exist a factor pair latin square. When a factor pair latin square does not exist, define a set $P$ of factor pairs. A quasi-factor pair latin square is an $n\times n$ array where very row, column, and $a\times b$ rectangle contains every symbol $1$ through $n$ exactly once for every ordered factor pair $(a,b)\in P$. Let $F$ be the maximum $P$ for which there exists a quasi-factor pair latin square.

For a given integer $n$, what is the largest $F$ such that there exists a quasi-factor pair latin square? This gives a natural integer sequence.


Project 17.06: Exceptional Units

Let $n\geq 2$ be an integer. An element $u$ in the ring $\mathbb{Z}_{n}$ is called an exceptional unit if $gcd(n,u) = gcd(1-u,n) = 1$. The concept of exceptional units has been generalized to elements that satisfy $gcd(n,u) = gcd(k-u,n) = 1$ for a fixed integer $k$. In this project we study these elements and their properties, as well as sequences that arise naturally from counting the number of such elements in $\mathbb{Z}_{n}$.

 

Project 17.07: $Q \times Q$

$Q \times Q$ is a 2-player game played on a $Q$ by $Q$ grid, where $Q \in \mathbb{N}$. For some natural number $n$, player 1 selects a square and places a number $k_1 \in \mathbb{N}$, $0<k_2 \leq n$ in the square. Player 2 then moves a total of $k_1$ squares horizontally and vertically by their choice of path, without crossing a previously used square, and chooses a number $k_2 \in \mathbb{N}$, $0<k_2 \leq n$ to place in the resulting square. Players repeat this process alternating turns until it is impossible to move. The last player to move wins the game. We will analyze winning strategies for various values of $Q$ and $n$, and determine for which values of $Q$ and $n$ the game is $N$-position, $P$-position, or $O$-position.

 

Project 17.08: Variations on Ultimate Tic-Tac-Toe

Ultimate tic-tac-toe consists of a $3 \times 3$ grid contained within each of the 9 spaces of a larger $3 \times 3$ grid. Two players take turns places X’s and O’s with the following rules: 1) the first move for each player is a free move; 2) successive moves must be in a previous marked grid; 3) when a player wins a grid they mark that grid with a large X or O for that player; 4) players then choose another open square and repeat the process until the larger grid is filled. This project will mathematically examine winning strategies for ultimate tic-tac-toe and analyze generalizations to the game such as $n \times n$ grids and alternative rules.