# Chip-Firing Games on Graphs

Project Description

Description: 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 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 may also study invariants related to gonality, like the recently developed scramble number of graphs, which provides a much-needed lower bound on gonality.  Check out herehere, and here for work by past SMALL groups on those fronts!  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 (including computational complexity), but there are still many open questions.
Our group can also study computational questions and work on implementations related to chip-firing and graph gonality.  Here’s a website that can accomplish lots of chip-firing tasks; can we make it more efficient?  How far can we push the computation of graph gonalities?

# Commutative Algebra: Interactions with Logic

Advisors: Jenna Zomback and Austyn Simpson

Project description:

Commutative algebra is the study of commutative rings and modules over them. This subject serves as the local language of modern algebraic geometry, but connections to other branches of math are plentiful. Recently there has been an explosion of activity linking commutative algebra to various objects native to mathematical logic and set theory. For example, ultraproducts and ultrapowers have been employed extensively to study big polynomial rings (arXiv:1801.09852) as well as to resolve some questions about singularities in equal characteristic (see e.g. arXiv:1710.05331). Other objects living in the logic-algebra intersection include modules equipped with a Polish structure (arXiv:2009.05855), as well as rings emerging from tiling theory and combinatorics.

The exact direction of research will depend on student interest. The only prerequisite is a course in abstract algebra.

# Commutative Algebra: Local Rings and Completions

Project Description

Consider the set of polynomials in one variable over the complex numbers. We can define a distance between these polynomials that turns out to be a metric. The Cauchy sequences with respect to this metric, however, do not all converge. So, we can complete this metric space to get a new metric space in which all Cauchy sequences converge. What is this new space algebraically? Surprisingly, it turns out to be the set of formal power series in one variable over the complex numbers. The idea of completing a set of polynomials generalizes to rings. Given a local ring, one can define a metric on that ring and form a new ring by completing the metric space. The relationship between a ring and its completion is important and mysterious. Algebraists often gain useful information about a ring by passing to the completion, which, by Cohen’s Structure Theorem, is easier to understand. Unfortunately, the relationship between a local ring and its completion is not well understood. It is the goal of the Commutative Algebra groups in SMALL to shed light on this relationship and to use the relationship to gain a
better understanding of the structure of Noetherian rings.

Students participating in the Commutative Algebra group will work on problems relating local rings to their completions. For example, they may attempt to characterize which complete local rings are completions of a local ring satisfying a given “nice” property. Students might also work on a variety of questions regarding the prime ideal structure of particular types of Noetherian rings. In addition, there are open questions about formal fibers on which students might work. At least one Abstract Algebra course is required.

The following references are results from previous SMALL Commutative Algebra groups.

• D. Lee, L. Leer, S. Pilch, and Y. Yasufuku, Characterizations of Completions of Reduced Local Rings, Proc. Amer. Math. Soc., 129 (2001), 3193-3200.
• M. Florenz, D. Kunvipusilkul, and J. Yang, Constructing Chains of Excellent Rings with Local Generic Formal Fibers, Communications in Algebra, 30 (2002), 3569-3587.
• J. Bryk, S. Mapes, C. Samuels and G. Wang, Constructing Almost Excellent Unique Factorization Domains, Communications in Algebra, 33 (2005), 1321-1336.
• A. Dundon, D. Jensen, S. Loepp, J. Provine, and J. Rodu, Controlling Formal Fibers of Principal Prime Ideals, Rocky Mountain Journal of Mathematics, 37 (2007), 1871-1892.
• A. Boocher, M. Daub, R. Johnson, H. Lindo, S. Loepp, and P. Woodard, Formal Fibers of Unique Factorization Domains, Canadian Journal of Mathematics, 62 (2010), 721-736.A. Boocher, M. Daub, S. Loepp, Dimensions of Formal Fibers of Height one Prime Ideals, Communications in Algebra, (2010), no.1, 233-253.
• N. Arnosti, R. Karpman, C. Leverson, J. Levinson, and S. Loepp, Semi-Local Formal Fibers of Minimal Prime Ideals of Excellent Reduced Local Rings, Journal of Commutative Algebra, (2012), no.1, 29-56.
• J. Chatlos, B. Simanek, N. Watson, and S. Wu, Semilocal Formal Fibers of Principal Prime Ideals, Journal of Commutative Algebra, 4 (2012) no. 3, 369-385.
• J. Ahn, E. Ferme, F. Jiang, S. Loepp, and G. Tran, Completions of Hypersurface Domains, Communications in Algebra, (2013), no. 12, 4491-4503.
• P. Jiang, A. Kirkpatrick, S. Loepp, S. Mack-Crane, and S. Tripp, Controlling the Generic Formal Fibers of Local Domains and Their Polynomial Rings, Journal of Commutative Algebra, 7, (2015), no. 2, 241-264.
• S. Fleming, L. Ji, S. Loepp, P. McDonald, N. Pande, and D. Schwein, Controlling the Dimensions of Formal Fibers of a Unique Factorization Domain at the Height One Prime Ideals, Journal of Commutative Algebra, 10, (2018), no.4, 475-498.
• S. Fleming, L. Ji, S. Loepp, P. McDonald, N. Pande, and D. Schwein, Completely Controlling the Dimensions of Formal Fiber Rings at Prime Ideals of Small Height, Journal of Commutative Algebra, 11, (2019), no. 3, 363-388.
• C. Avery, C. Booms, T. Kostolansky, S. Loepp, and A. Semendinger, Characterization of Completions of Noncatenary Local Domains and Noncatenary Local UFDs, Journal of Algebra, 524, (2019), 1-18.
• E. Barrett*, E. Graf*, S. Loepp, K. Strong*, and S. Zhang*, Structure of Spectra of Precompletions, Rocky Mountain Journal of Mathematics, 50, (2020), no. 6, 1965-1988.
• E. Barrett*, E. Graf*, S. Loepp, K. Strong*, and S. Zhang*, Cardinalities of Prime Spectra of Precompletions, in Commutative Algebra, Contemporary Mathematics., vol.773, Amer. Math. Soc., Providence, RI, 2021, pp. 133-152.

# Number Theory and Probability

Advisor: Steven J. Miller and possibly others

Project Description:

We’ll explore many of the interplays between number theory and probability / harmonic analysis, with projects drawn from L-functions, Random Matrix Theory, Additive Number Theory (such as the 3x+1 Problem and Zeckendorf decompositions), and Benford’s law. A common theme in many of these systems is either a probabilistic model or heuristic. For example, Random Matrix Theory was developed to study the energy levels of heavy nuclei. While it can be hard to analyze the behavior of a specific configuration it is often possible to say something about the configurations in aggregate. For instance, it is often easy to calculate an average over all configurations, and then appeal to a Central Limit Theorem type result to say that a generic systems behavior is close to this average. These techniques have been applied to many problems, ranging from the behavior of L-functions to the structure of networks to city transportation.

The choice of problems will be chosen by student interest from these and other related topics. For references for each set of problems and additional details, please go to http://www.williams.edu/Mathematics/sjmiller/public_html/ntprob19 , and you can access my papers at my homepage https://web.williams.edu/Mathematics/sjmiller/public_html/math/papers/papers.html as well as videos and slides for talks at https://web.williams.edu/Mathematics/sjmiller/public_html/math/talks/talks.hml

# Statistical Approaches to Pattern Matching in Forensic Evidence

Advisors: Xizhen Cai, Anna Plantinga and Elizabeth Upton

Project Description:

The validity of existing approaches to analyzing forensic evidence (such as bullet casings and footprints) has been called into question in recent years. We will work on statistical questions related to pattern matching, such as matching bullet casings or breech face impressions to guns or matching footprints to shoes. This work will be done in collaboration with the Center for Statistics and Applications in Forensic Evidence (CSAFE), introducing student researchers to a network of fellow students and professional statisticians working on related problems around the country. For sample topics and projects, see https://forensicstats.org/ .

Required qualifications: An introductory statistics course and a course in regression theory based on linear algebra and multivariable calculus, with at least moderate proficiency in R coding.

Preferred qualifications: Familiarity with machine learning/data mining techniques and experience working with large datasets.