Erich's Undergraduate Research Problems
Erich's Undergraduate Research Problems

Every Stetson student does a Senior Research Project during their last two semesters. I have many possible projects in the fields of combinatorial game theory, combinatorial geometry, combinatorics, and graph theory. A sampling of problems is shown below.

Colonel Blotto

An attacking player has A armies to deploy to attack B bases. A defending player has D armies to deploy to defend these bases. Both players decide on their apportionment, and then reveal their choices. If a base is attacked by more armies than it is defended with, it is captured. The attacking player wants to maximize the number of bases captured, and the defender wants to minimize this number. What are their best strategies?

Graph Connectivity

Given a connected graph, we can always delete vertices one-by-one, together with any incident edges, so the remaining graphs stays connected. For a given a graph G, the number of ways this can be done is called the connectivity of G. What numbers are connectivities? Can you find reasonable bounds for the connectivity of a graph?

Idiot-Proof Tiles

Assume we have a collection of congruent polyomino tiles with which to tile the plane. Some tiles are idiot-proof: if you put two tiles down in any configuration far enough away, you can always complete the tiling. Below is a tile which is not idiot-proof. Which tiles are idiot-proof? For an idiot-proof tile, how far away is far enough?

Antipodes and Geodesics

In a graph, the unique vertex farthest from vertex u is called the antipode of u. Which graphs have the property that every vertex has an antipode? A geodesic is the shortest path between two vertices. Which graphs have the property that all geodesics are unique?

Nim Variations

Nim is a game involving several piles of matches. Two players alternate removing any number of matches from any one pile. The winner is the person who takes the last match. It turns out that Nim can be easily analyzed using base 2 arithmetic. There are many modifications of Nim that have not been solved.

3 Polyomino Tilings

There are n ways to divide a 2 x n rectangle into 2 polyominoes (connected union of unit squares) with area n. How many ways are there to divide a 3 x n rectangle into 3 polyominoes with area n?

Convex Polyiamonds

A polyiamond is a union of unit area equilateral triangles where triangles meet along two entire sides. How many polyiamonds of area n are convex? For example, there are 3 convex polyiamonds with area 8:

Philosopher's Phutball

Philosopher's Phutball is a two-player game played on a n x m rectangular playing board. There are two types of pieces: one ball (a black stone), and many men (white stones). The board starts out empty, except for one square that contains the ball.

The players alternately do one of two things on their turn. Either 1) place a man on any empty square on the board, or 2) jump the ball over any number of times. A jump may be in one of 8 directions (horizontal, vertical, or diagonal). The ball is jumped over a line of adjacent men to the first empty square beyond, and the men jumped are removed.

The object of the game is to jump the ball off a side of the field. The first player wins if he jumps the ball off the left side, and the second player wins if he jumps the ball off the right side. For example, on a 7 x 1 field with the ball starting in the center, the first player wins as shown below. To avoid losing immediately, the second player must jump man #2, but the first player replaces this man on his move and wins next move.

Given the size of the board and the initial placement of the ball, who can win this game, and how?

Semi-Partite Graphs

A bipartite graphs is a graph whose vertices can be 2-colored so that the longest monochromatic chain of vertices has length 1. Bipartite graphs have been well studied, and are exactly the graphs containing no cycles of odd length. Define a semipartite graph to be a graph whose vertices can be 2-colored so that the longest monochromatic chain of vertices has length 2. Can these graphs be easily classified?

Modeling the Strength of Sports Teams

There is much controversy in the country today over the system used to rank college football teams. There are many models for the strength of a sports team, given its record and schedule. One easy model is to assign each team a rank (a number from 0 to 1), and have the probability a team beats another be a function of the two ranks. Is this a good model, based on the percent of the outcomes it correctly predicts? How can you improve the model?

Symbiotic Tile Sets

A set of polyominoes is called n-symbiotic if any n tiles, each of which is similar to one in the set, can tile a larger copy of a polyomino in the set. For example, the straight triomino and the bent triomino form a 4-symbiotic set, as the pictures below show. Find some other symbiotic sets. For a given set of polyominoes, does there always exist an n so that the set is n-symbiotic? Is the number of n-symbiotic sets finite for each n?

Past Student Projects of Mine

 Uncrossed Knight Tours(Ciara Caltagirone, 1998) Triangulations of Squares(Stephanie Daignault, 1998) Building Minimal Block Bridges(Amanda Richardson, 1998) One Dimensional Peg Solitaire(Jennifer Scott, 1998) Mancala Ad Infinitum(Gary Preisser, 1998) A Mathematical Wayof Connecting the Dots(Heather Garten, 2000) Bumper Cars(Will Simpson, 2000) Balancing Survey Costswith Nonresponse Bias UsingCallbacks in Telephone Surveys (Jennifer Czuprynski, 2001) A Variant of Pascal's Triangle(Dennis Van Hise, 2001) A Survey of Semi-Regular Graphs(Alison Northup, 2002) A Simulation of TrafficFlow on Highways(Jessica Lees, 2003) Generalized Chess Endgames(Bruce Moser, 2003) Numerical Analysis of theDiscrete Fourier Transform(Hope Wymer, 2004) Blob, A Strategy Game(Adam Holers, 2006) Improving the Ranking Systemfor Women's Professional Tennis(Maya Miladinovic, 2008) Maximizing Angle Countsfor n Points in the Plane(Brian Heisler, 2008) Modeling Lower Bounds ofWorld Record Running Times(Kevin Heisler, 2008)

 Home | Math Magic | Packing Center | Puzzle Palace | Published Puzzles | Puzzle Collection Friedman Numbers | What's Special About This Number? | Periodic Table of Mathematicians Stetson University | Math Department | Teaching | Vita | Undergraduate Research | Ambigrams Florida Mini-Golf | Movies | Places I've Been | Places I've Been E-mailed From | E-mail Me Pictures of Me | My Math Geneology | Top Ten Lists | Mathematical Horoscope | Math Humor