Speaker: Austin Longin, ISU
Title: The hat guessing number of graphs
Abstract: Given a graph G and a set of colors [q], a game is played between the vertices (who are on a team) and an adversary. The adversary gives a hat with a color in [q] to each vertex of the graph. Vertices cannot see the color of their own hat, but they can see the colors of the hats placed on neighboring vertices. Without communicating, the vertices each guess their own hat color, and the vertices win if any of them guess correctly. A graph is q-solvable if there exists a guessing strategy for the vertices such that they win regardless of the coloring that the adversary chooses. The hat guessing number of a graph HG(G) is the largest number q such that G is q-solvable. We compute the hat guessing number of tress as well as some other nice graphs.