Maker Breaker Games on Graphs and Matroids
Jenny McNulty
The University of Montana
A Maker-Breaker game, often called a tic-tac-toe game, is a 2 person game in which Maker tries to “make” something and Breaker who goes second wants to prevent Breaker from doing this. In Tic-Tac-Toe, the first person (let’s say X) is trying to “make” a line, that is get three X’s on a horizontal, vertical and diagonal line. The second player (O) has played enough times to know she can never “make” a line, the best she can do is to prevent X from making a line, her strategy is to “break” the lines and prevent X from winning. Unlike traditional tic-tac-toe, we’ll say X wins if he makes a line and O wins if she breaks all the lines. We’ll consider games of the sort on graphs and matroids. In these games we’ll change goal for Maker that is he will not be always trying to make a line, but instead some other object (like a forest, cycle, fixing set, proper coloring etc.) This is an introductory talk which will involve hands-on game playing. All terminology mentioned above will be explained. This is joint work with my undergraduate and graduate students.
Jenny McNulty is a graduate of Providence College. After receiving her BA in Chemistry and Mathematics at PC, she went on to SUNY Stony Brook where she obtained an MA in Mathematics and then to the University of North Carolina. At UNC, she completed her Ph.D. in matroid theory. In 1993, Dr. McNulty started her career at The University of Montana, currently holding the position of Associate Dean. At UM, Dr. McNulty has taught numerous courses, supervised many students, and organized numerous seminars and outreach programs; her favorite activity among all of these is sharing her love of mathematics. Her research area is Combinatorics, with an emphasis on Matroid Theory; she is currently writing a book, designed especially for undergraduates, on this subject. While Montana is far away from her native Long Island home, she has learned to love her new home and is an avid kayaker and ice hockey player.
