The search for computable domatic partitions

CUNY Logic WorkshopFriday, March 21, 20142:00 pmGC 6417

Matt Jura

The search for computable domatic partitions

Manhattan College

A domatic $k$-partition of a graph is a partition of the vertex set into $k$ many classes, in which each vertex $v$ is adjacent to some vertex in every partition class of which $v$ is not a member; the domatic number is the largest $k$ for which there is a domatic $k$-partition (compare to the chromatic number of a graph, which is the size of the smallest partition into independent sets). The authors previously showed that there is a computable, locally finite graph $G$ with a domatic $k$-partition, but no computable domatic $3$-partition. In this talk we will investigate whether the same result holds for highly computable graphs, and $A$-computable graphs (we say a graph $G$ is $A$-computable if $A$ can compute the neighborhood function of $G$). This work is joint with Oscar Levin and Tyler Markkanen.

Matt Jura received his Ph.D. from the University of Connecticut, as a student of Reed Solomon, and is currently Assistant Professor in the Mathematics Department of Manhattan College. He studies computability theory, with a focus on reverse mathematics.

Posted by on February 17th, 2014