2024 Iowa State REU Projects

Recreational mathematics

Project mentor: Steve Butler

The goal of this project is to do some problems that are tied to recreational mathematics. The primary goal is not to produce a paper (though we might mess up and end up publishing a paper by mistake), but to explore some math problems, make some progress in understanding, get practice in some programming, come out of the summer with a better understanding of what math can be, and importantly have a fun experience. (The alternative description for this project is "Have fun, prove s**t".)

The initial two problems we will be considering are as follows:

We might also look at some LEGO constructions involving "tubes" and in particular try to build a large cube which is "optimal" in some measurable way. Even if we fail, our spaghetti-fication of the cube will hopefully lead to some beautiful construction(s).

Prerequisites: Proof-based math course; basic linear algebra course; mathematical curiosity; good communication skills and ability to work well in a group.

Two graphs, one spectrum: variations of the distance matrix

Project mentor: Kate Lorenzen

A graph is a mathematical object with vertices and edges that are used to model networks. The distance between two vertices is the smallest number of edges between the two. The distance matrix is the matrix where the ij-th entry stores the distance between vertices i and j. We are interested in the exponential distance matrix where the ij-th entry is q raised to the distance between vertices i and j. This has been an intriguing matrix since it is well defined for |q|<1 for disconnected graphs. We are particularly interested in when two graphs exponential distance matrices have the same spectrum, or same set of eigenvalues. These types of graphs are make a cospectral pair. We will be investigating graph, combinatorial, and linear algebra patterns that lead to cospectral pair. 

Prerequisites: Interested students should have taken a linear algebra course and preferably have familiarity with graph theory or combinatorics.

Counting independent sets in grid-like graphs

Project mentor: Anna Halfpap

A graph is a mathematical object made up of points (called vertices) and lines (called edges) which connect some pairs of points. As well as being interesting in their own right, graphs are often useful tools for modelling networks and other objects whose structure is based on the relationships between people or things. For example, a set of vertices which spans no edges might correspond to a set of objects which are somehow unrelated or "far away" from each other. We call such a set an independent set. Many important questions in graph theory involve finding, counting, or otherwise understanding independent sets. This project will focus on counting maximal independent sets (often called MIS's for short) -- that is, independent sets which cannot be made larger by the addition of extra vertices. In general, the number of maximal independent sets in a graph will depend a lot on the graph's structure; for this project, we will focus on MIS's in nicely-structured graphs which arise from grids. 

The m x n integer lattice can be thought of as a graph, whose vertices are the points (i, j) where i and j are positive integers with i at most m and j at most n, and where two vertices are connected by an edge if and only if they are at unit distance in the plane. We call a graph which arises from the m x n integer lattice a grid graph; predictably, grid graphs look like flat grids when we "naturally" draw them in the plane. This project will focus on the "grid-like" graphs which arise from embedding integer lattices on non-flat surfaces, such as a Mobius strip or a torus. You can visualize such an embedding by starting with a flat grid, picking it up, and ​"gluing together" two or more of its sides to make a non-flat object. This gluing procedure identifies some vertices and edges of our grid, changing its structure in cool ways while maintaining grid-like properties. 

Ordinary grid graphs have very regular structure, which can give rise to some beautiful results. Several authors have recently used this structure to give different descriptions of the number of MIS's in grids. For instance, the number of MIS's in the 2 x n grid can be determined by a recurrence relation which is closely related to the Fibonacci numbers. Using more complicated recurrence relations, we can find the number of MIS's in m x n grids generally. Are there similar recurrence relations (possibly relating to other beautiful sequences) for the number of MIS's in the m x n "grid Mobius strip", "grid cylinder", or "grid torus"? We will begin by trying to find such recurrence relations for 2 x n grid-like graphs; depending on our progress and participants' interests, this exploration may lead in a variety of more general directions. Some natural questions would include: Once we understand MIS's in 2 x n grid-like graphs, can we understand 3 x n grid-like graphs, or even m x n grid-like graphs? Can we somehow describe the "typical structure" of a maximal independent set in a grid graph -- and does this typical structure change when we embed our grid on a non-flat surface? Are there interesting correspondences between the number of MIS's in different "shapes" of grid-like graphs? 

Prerequisites: Students should have experience writing proofs (i.e., at least one proof-based math course), curiosity about the topic, and the ability to work well in a group. Familiarity with graph theory and/or combinatorics is desirable.