A-Computable Graphs

NERDS: New England Recursion & Definability SeminarSaturday, October 17, 201510:15 amCarriage House, Assumption College, Worcester, MA

Tyler Markkanen

A-Computable Graphs

Springfield College

A locally finite computable graph G is called A-computable if A can compute the neighbors of the vertices of G. William Gasarch and Andrew Lee introduced this notion to study graphs that are “between” computable and highly computable (i.e., ∅-computable). For any noncomputable c.e. set A, they proved that the A-computable graphs behave just like computable graphs when it comes to colorings. In this talk, we will see that their result also works for Euler paths and domatic partitions. Although it does not extend to arbitrary sets A (that are not necessarily c.e.), we will classify the sets for which it does.

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 September 28th, 2015