Overview

Date: Saturday, May 2, 2015
Time: 11:00am–4:30pm
Place: University of Connecticut (Visitor information), Laurel Hall 307 (View on campus map).

Schedule

10:00–10:30	Coffee
11:00–12:00	Stephen Flood (University of Connecticut)	The Logic of Graph Decompositions
12:00–1:30	Lunch
1:30–2:00	Seth Harris (Dartmouth College)	Evasion, Prediction, and On-Line Graph Problems
2:15–3:15	Karen Lange (Wellesley University)	Lengths of roots of polynomials over k((G))
3:30–4:30	Carl Jockusch (University of Illinois)	Imperfect Computability

Abstracts

Stephen Flood

The theory of simplicial graph decompositions studies the graphs that can be built by pasting irreducible graphs together at complete subgraphs. Many of the classical definitions refer to arbitrary ordinal lengths, and many classical proofs use Zorn’s lemma. We will study this theory from the perspective of mathematical logic and computability theory.

We will first classify the strength of one “existence theorem,” known as Halin’s Theorem, by eliminating the use of Zorn’s lemma from its proof. We will then compare the ordinal lengths of different classes of graphs. This will allow us to show that the index set of general decomposable graphs is \Pi^1_1 hard, and that the index set of tree-decomposable graphs \Sigma^1_1 definable.

Seth Harris

The principle Evade_k(n) is a variation of the principle DNR(n), the existence of a Diagonally Non-Recursive function with range bounded by n. Schmerl first studied the relationship between Evade_k(n) and on-line graph colorings, in which the graph and its color function are created by a two-player game. I will present joint work with François Dorais on the reverse-mathematical strength of Evade_k(n) and its variants, and I will present some applications to on-line graph coloring problems and on-line marriage (bipartite matching) problems.

Carl Jockusch

This is joint work with Andy Lewis. We compare the computational power required to produce noncomputable functions using various methods. Our main result is that every diagonally noncomputable function computes a bi-immune set, and this holds uniformly. Here a function f from \omega to \omega is called diagonally noncomputable if, for all e, f(e) \neq \phi_e (e) , where \phi_e is the e-th partial computable function in a standard enumeration. A set A \subseteq \omega is called bi-immune if neither A nor its complement contains an infinite computably enumerable subset. This result fits into a larger framework of comparing the difficulty of diagonalization and randomization which I will also discuss.

Karen Lange

Mourgues and Ressayre showed that any real closed field R can be mapped isomorphically onto a truncation-closed subfield of the Hahn field k((G)), where G is the natural value group of R and k is the residue field. If we fix a section of the residue field and a well ordering \prec of R, then the procedure of Mourgues and Ressayre yields a canonical section of G and a unique embedding d: R \to k((G)). Julia Knight and I believed we had shown that for a real closed field R with a well ordering \prec of type \omega, the series in d(R) have length less than \omega^{\omega^\omega}, but we found a mistake in our proof. We needed a better understanding of what happens to lengths under root-taking. In this talk, we give a partial answer, which allows us to prove the original statement and generalize it. We make use of unpublished notes of Starchenko on the Newton-Puiseux method for taking roots of polynomials.