The domatic numbers of computable graphs

CUNY Logic WorkshopFriday, May 9, 20142:00 pmGC 6417

Tyler Markkanen

The domatic numbers of computable graphs

Springfield College

A dominating set $D$ of a graph is a set of vertices “near” all other vertices, in that every vertex outside of $D$ is adjacent to a vertex in $D$. In this talk, we will compare two values associated with a graph $G$: the domatic number $d(G)$ and computable domatic number $d^c(G)$, which give the size of the largest partition and computable partition (respectively) of $G$ into dominating sets. Our goal is to maximize the value of $d(G)-d^c(G)$ for highly computable graphs (in which we can computably count each vertex’s neighbors). Specifically, is it even possible for this difference to be greater than 1? To find an answer, we will work with total dominating sets (where $D$ must now be near all vertices, instead of only the ones outside of $D$) and regular graphs (where each vertex has exactly the same number of neighbors). In our proofs and constructions, we will play the “game” of computable graph theory, as we set up gadgets and spring traps against adversaries who are determined to thwart our every move.

The slides for the talk are available here.

Tyler Markkanen received his Ph.D. in 2009 from the University of Connecticut, as a student of Reed Solomon. After teaching at St. Mary-of-the-Woods College and Manhattan College, he has now joined the faculty of Springfield College. He studies computability theory, with a focus on computable model theory.

Posted by on February 17th, 2014