Saturday, October 17, 201510:15 amNERDS: New England Recursion & Definability SeminarCarriage House, Assumption College, Worcester, MA

A-Computable Graphs

Tyler Markkanen

Springfield College

Tyler Markkanen

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.