The Department of Math, Physics, and Computer Science Colloquium: Graph Theory: A Colorful World of Games and Logic

Presented by Tyler Markkanen, PhD
Associate Professor of Mathematics

Schoo-Bemis Science Center, Room 110

Suppose we color a map of the United States so that no two bordering states have the same color. Once completed, we will say that this map has been properly colored. Question: What are the fewest number of colors required to complete such a task? Answer: For a map of the 48 contiguous U.S. states and the District of Columbia the answer is four. In fact, according to the Four-Color Theorem, a two-dimensional map of any land with finitely many regions, real or fictitious (e.g., Tolkien’s Middle-Earth), can always be properly colored with four or fewer colors.

In this talk, led by Tyler Markkanen, we will show how Graph Theory can help solve similar coloring conundrums. We will use the principles of mathematical logic to explore infinite spaces, revealing new information about graphs. For example, by playing the game of Cops and Robbers, we can gain a deeper understanding of how to construct or dismantle an infinite graph, based on the order in which each vertex is placed or removed. This work is in collaboration with Markkanen’s colleagues at other institutions: Stephen Flood, PhD, and Shelley Stahl, PhD, from Bridgewater State University; Matthew Jura, PhD, at Manhattan College; Oscar Levin, PhD, at the University of Northern Colorado; and Reed Solomon, PhD, at the University of Connecticut.

Tyler Markkanen is a mathematician and teacher. His research is in mathematical logic, with a special interest in computability theory and computable model theory.

This event is free and open to the Springfield College community.

For more information, contact Kellie Lavoie at klavoie2@springfield.edu.