Competitive Graph Coloring
Mentor: Chuck Dunn
We consider variations of the following game played on a finite graph G. Two players, Alice and Bob, alternate coloring the uncolored vertices of G from a set of r colors. At each step, the players must ensure that adjacent vertices receive different colors. Alice always goes first. She wins the game if the entire graph is eventually colored; otherwise, Bob wins if there comes a time such that there is an uncolored vertex that cannot be colored. The least r such that Alice has a winning strategy for this game on G is called the game chromatic number of G. We will examine variations of this game in which the players can color vertices and/or edges, and relaxations of the game in which the subgraphs induced by the color classes have bounded clique size or bounded maximum degree. Our focus with these variations will be on the classes of trees, forests, chordal graphs, outerplanar graphs, planar graphs, and partial k-trees.
Geometric Representations of Graphs
Mentor: Josh Laison
Using techniques from both graph theory and discrete geometry, we investigate families of intersection graphs and/or visibility graphs. Specifically, given a set S of geometric objects (triangles, rectangles, line segments, cubes, etc.), we can construct their intersection graph with a vertex for each object in S, and an edge between two vertices if and only if their corresponding objects intersect. We can alternatively construct their visibility graph, with an edge if and only if their corresponding objects see each other. We can ask which graphs are representable as intersection graphs or visibility graphs of a given type of geometric shape, or whether graphs representable with one shape are representable with another. In this project, the research group will define and investigate a new variation of intersection or visibility graphs.
Mentor: Naiomi Cameron
A dessin (named for “dessin d’enfant” meaning “child’s drawing”) is a connected bicolored graph where the edges around every vertex are cyclically ordered. In the early 1980s, A. Grothendieck observed that all dessins arise from finite coverings by a Riemann surface which can be defined over the set of algebraic numbers, while a theorem due to G. Belyi shows that every algebraic curve defined over the set of algebraic numbers has an embedded dessin. The correspondence between dessins and algebraic curves over the set of algebraic numbers suggests that a simple “child’s drawing” can indeed mask a deep arithmetical structure. The theory of dessins shows that the Galois group acts faithfully on the set of dessins (by acting on the associated covers), and one of the central questions in the theory is how to tell whether two dessins belong to the same Galois orbit. There is a great deal of interest in better understanding the Galois orbits of dessins through combinatorial, topological, geometric and/or arithmetical points of view. Even in the case where the dessin is a tree (that is, a connected graph with no cycles), there is much to be explored. The objective of this project is to make a contribution to these efforts by focusing on enumerative questions for certain classes of dessins and/or points of view.
Prior coursework in Discrete Mathematics, Number Theory and/or Abstract Algebra will be helpful.
Mixing Times of Markov Chains
Mentor: Peter Otto
The fundamental result of irreducible and aperiodic Markov chains is the Convergence Theorem that states that the distribution of the chain converges to a unique stationary distribution as the time steps go to infinity. In the modern study of Markov chains, an important question is how many time steps are required to be within a prescribed distance from the stationary distribution. This minimum number of required time steps is called the mixing time of the Markov chain. During the summer of 2016, the REU research group derived upper bounds on the mixing times of the rook’s walk on an n^d size chessboard with certain restrictions. The method used was the path coupling technique that expresses the distance between the Markov chain and the stationary distribution in terms of the mean coupling distance of a coupled process of two copies of the Markov chain starting at neighboring configurations.
Bayesian Image Analysis
Mentor: Xiaoyue Luo
We considered the task of reconstructing images corrupted by Gaussian and/or Poisson noise which is important in various applications such as medical imaging, optical microscopy, or astronomical imaging. Mathematically, image reconstruction in those applications can be formulated as a linear inverse and ill-posed problem. Typically, in such problems one has to deal with Fredholm integral equations of the first kind which is a well-known ill-posed problem due to the fact that the solution does not depend on the given data continuously. In this case, regularization techniques are required to enforce stability during the inversion process to obtain useful reconstructions. We therefore developed a novel method of local regularization for deblurring with Poisson and mixed Poisson-Gaussian noise present. We used a Gaussian approximation to the Poisson noise statistic, established a correspondence between the local regularization and standard Tikhonov regularization methods, and developed a discrepancy principle for parameter selection in our method. We concluded with numnerical implementations that demonstrate the effectiveness of our method for image deblurring and denoising problems.
Final presentation slides
Multiple-Urn Ehrenfest Model
Mentor: Yung-Pin Chen
The original two-urn Ehrenfest model can be represented by a Markov chain describing many natural random processes such as the diffusion of gas molecules between two isolated bodies. We began our project with introducing a third urn and examining the eigensystem of the transition matrix of the Markov chain associated with the three-urn model. Our work provided a complete eigenanalysis, including explicit forms of the eigenvalues and eigenvectors, of the transition matrix of a generalized multiple-urn Ehrenfest model. Equipped with the eigenanalysis results, we obtained a formula for the finite-step transition probabilities of this multiple-urn Ehrenfest model. We also established expressions for numerous interesting cases of expected hitting times between states under the generalized multiple-urn Ehrenfest model.
Algebraic Voting Theory
Mentor: Erin McNicholas
Algebraic voting theory is a relatively new field of study. Inspired by the symmetry arguments used by Donald Saari in his geometric approach to voting paradoxes, Michael Orrison and several undergraduates at Harvey Mudd College have successfully applied basic ideas of representation theory to extend well-known results in the field of voting. In particular, they have shown that viewing voting profiles as elements of Q_n-modules allows for new insight on a number of well-studied voting methods. In this project we will examine voting-for-committee procedures through an algebraic lens.
Algorithms over Polynomial Rings
Mentor: Courtney Gibbons
Combinatorial commutative algebra has a history of using discrete methods, such as looking at generating functions over the integers, to describe the structure of an object. For example, the Hilbert series of a module is an integer-coefficient formal power series that describes a module's size degree by degree. An example program of study starts by fixing a ring and studying the convex combinations of Betti tables (these are related to Hilbert series). We could ask how a special type of Betti table will "break up" into component parts using a specific decomposition algorithm.
Mentor: Colin Starr
A unipancyclic graph is a graph on n vertices with exactly one cycle of each possible size 3 through n. Only seven such graphs are known, and it is also known that there are no others among graphs up to order 56. Starr and Turner generalized the idea of a unipancyclic graph to matroids (simply replacing "cycle" with "circuit" in the definition) and discovered an additional non-graphic unipancyclic matroid. In this project, participants will seek to find more such examples and to use matroid techniques to study unipancyclic graphs and matroids. Further options for exploration include pancyclic graphs (cycles need not be unique), bipancyclic graphs (bipartite graphs with all possible even cycles), and n-pancyclic graphs (exactly n distinct cycles of each possible length).