Upcoming Events

Location:KAP 245

Title: What is the minimum number of colors needed to solve our puzzle?

Abstract: A “graph” is a collection of two kinds of objects which we call “points” and “edges.”  An edge is a connection between two points, which we can represent by drawing a line segment between the two points.  For example, we could define one point for each student committee on your campus, and then decide that two committees are “connected” if there is a student who sits on both committees.  Now, suppose we are trying to schedule committee meetings using as few hour-long time slots as possible.  We could phrase this problem as requiring a coloring of the points (red, blue, green…) such that connected points receive different colors (where each color represents a time slot).

In this talk, I will bring up a few abstract graph-coloring puzzles such as this.  Tools from logic can be helpful to analyze these puzzles.  Some of the puzzles we will solve together, and some will be left to you!