| The SMALL Undergraduate Research Project is a nine-week residential summer program in which undergraduates investigate open research problems in mathematics. One of the largest programs of its kind in the country, SMALL is supported in part by a National Science Foundation grant for Research Experiences for Undergraduates and by the Science Center of Williams College. Around 500 students have participated in the project since its inception in 1988. In the next few weeks we will have a listing of what professors are participating and what their groups will be; when you apply you will need to rank your preferences.
Students work in small groups directed by individual faculty members. Many participants have published papers and presented talks at research conferences based on work done in SMALL. Some have gone on to complete PhD’s in Mathematics. During off hours, students enjoy the many attractions of summer in the Berkshires: hiking, biking, plays, concerts, etc. Weekly lunches, teas, and casual sporting events bring SMALL students together with faculty and other students spending the summer doing research at Williams College.
THE SMALL PROGRAM WILL HAVE SEVERAL GROUPS THIS SUMMER: CONNECTIONS THROUGH DIOPHANTINE EQUATIONS, NUMBER THEORY/PROBABILITY, CHIP FIRING GAMES (THIS GROUP), AND OTHERS TO BE DETERMINED; HOWEVER, PLEASE APPLY JUST TO YOUR TOP CHOICE. DO NOT APPLY TO THE MAIN PROGRAM, DO NOT APPLY TO MULTIPLE GROUPS; IF YOU DO EITHER YOUR APPLICATION WILL NOT BE READ. WE ARE HAVING YOU APPLY TO YOUR TOP CHOICE TO FACILITATE ADMINISTRATIVE TASKS. IF YOU HAVE ANY QUESTIONS EMAIL THE DIRECTOR AT smalldirector@williams.edu. WHEN YOU FILL OUT THE ADDITIONAL FORM LISTED BELOW, YOU CAN PUT YOUR OTHER CHOICES. DEADLINE IS WEDNESDAY FEBRUARY 3rd, 5pm US EASTERN.
Title: Chip Firing Games
Professor Ralph Morrison <10rem@williams.edu>
Go to https://math.williams.edu/small/ for a version with active links.
A graph is a collection of nodes (or vertices) connected by edges. We play a chip-firing game on such a graph by placing an integer number of chips on each node of the graph, and then moving them around according to chip-firing moves, where one node donates chips to its neighbors, one along each edge. You can try it out here! This simple game leads to remarkably beautiful and complex mathematics, with applications to such disparate areas as graph theory, dynamical systems, and algebraic geometry. Our group will study chip-firing games and the mathematics they lead to, as detailed in some possible projects below.
The simplest chip-firing game, like the one linked above, has the goal of eliminating all “debt” (or negative numbers of chips) from the graph. A slightly more complicated game is the following: you place k chips on the graph, and then an opponent places -1 chips. You get to chip-fire to try to remove the debt. If you can remove it, you win; if you can’t, then your opponent wins. The gonality of a graph is the smallest k such that you have a winning strategy. This number is hard (in fact, NP-hard!) to compute, but we can hope to try to compute it for certain families of graphs. For instance, my SMALL 2018 group determined the gonality of glued grid graphs; and a SMALL alum and I studied how gonality behaves under taking Cartesian products of graphs. Another strategy is to study graphs with a small gonality, like gonality 2 or (as SMALL 2018 did) gonality 3. There are still loads of open families of graphs whose gonalities are unknown, and would be great to study!
We can also look at chip-firing games on metric graphs, which have lengths assigned to their edges, and once again ask about their gonality. This is especially exciting if those metric graphs are coming from tropical curves.
There are also generalizations of the gonality game: for instance, what if the opponent gets to place -2 chips? Or -3? Or more? We can still ask how few chips we need to be guaranteed to win; we call these numbers the second gonality, the third gonality, and so on. There are a few results known about higher gonalities of graphs, but there are still many open questions.
Our group can also study computational questions related to graph gonality. Although it is NP-hard to compute in general, we might hope for certain families of graphs it is not so daunting. For instance, checking if a graph has gonality 2 can be done in quasilinear time! We might try to find similar results for graphs of gonality 3, or for computing the gonality of planar graphs. It would also be fantastic for us to implement algorithms to compute gonality and perform other chip-firing operations, for use by researchers or in the classroom.
Applications are due Wednesday, February 5th by 5pm Eastern. Please remember to fill out and upload the additional requested information, which is available as a word file at https://math.williams.edu/files/2019/10/SMALLApplicationDocGeneral.doc and as a pdf at https://math.williams.edu/files/2019/10/SMALLApplicationDocGeneral.pdf |
finished (2020/10/20, finished 2021/07/09, listed until 2021/04/21)