2023 Combinatorial Game Theory Colloquia
In January 2023, I attended the Combinatorial Game Theory Colloquia, which was held in S. Miguel, Azores. What an awesome experience! The conference is held every other year and I’ll definitely be back. On the final day of the conference, I gave a talk titled Impartial geodetic convexity achievement and avoidance games on graphs. My talk summarized some of the work that was begun during my week at ICERM with Bret Benesh, Marie Meyer, Sarah Salmon, and Nandor Sieben. Nandor was also at the conference and gave a talk. Here is the abstract for my talk:
A set $P$ of vertices of a graph $G$ is convex if it contains all vertices along shortest paths between vertices in $P$. The convex hull of $P$ is the smallest convex set containing $P$. We say that a subset of vertices $P$ generates the graph $G$ if the convex hull of $P$ is the entire vertex set. We study two impartial games Generate and Do Not Generate in which two players alternately take turns selecting previously-unselected vertices of a finite graph $G$. The first player who builds a generating set for the graph from the jointly-selected elements wins the achievement game GEN($G$). The first player who cannot select a vertex without building a generating set loses the avoidance game DNG($G$). Similar games have been considered by several authors, including Harary et al. In this talk, we determine the nim-number for several graph families, including trees, cycle graphs, complete graphs, complete bipartite graphs, and hypercube graphs.
And here are the slides:
One cool consequence of the conference is that Nandor and I are now working on a new research project with Bojan Bašić, Paul Ellis, and Danijela Popović. The project was inspired by Danijela’s talk at the conference. I’m really excited about this new project!