Midwest Computability Seminar

XIX


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, and the University of Wisconsin-Madison. It meets once or twice per semester at the University of Chicago, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.

DATE: Thursday, March 16, 2017.
PLACE: Ryerson Hall 352 (the Barn), The University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers:

Schedule:


Abstracts:

Gregory Igusa

Title: Monochromatic path decomposition

Abstract: In 1978, Rado published a theorem showing that, given any n-coloring of pairs of integers, the integers can be partitioned by a collection of n monochromatic paths through the integers, one for each color. We consider this principle from the point of view of effective combinatorics and reverse mathematics. Although the principle bears a certain superficial resemblance to Ramsey's theorem for pairs, the global requirement that the paths must partition ω gives it a very different character.

The principle has a type-change between n=2 and n>2: When restricted to a finite set, the principle remains true for n=2, but is false for n>2. This distinction does not reflect in the reverse mathematics of the infinitary principle, but it appears to produce a difference in the effective combinatorics.

For n=2, we provide an exact characterization of the effectivity of the principle, and for all values of n, we provide an exact characterization of the reverse mathematical strength of the principle.

This work is joint with Peter Cholak, Ludovic Patey, Mariya Soskova, and Dan Turetsky.


Jack H. Lutz

Title: Algorithmic dimensions and fractal geometry

Abstract: This talk will review the Σ01 notions of algorithmic information and dimension and survey very recent applications of these to classical (non-algorithmic) questions in fractal geometry. These applications include N. Lutz and D. Stull's strengthened lower bounds on the dimensions of generalized Furstenberg sets and N. Lutz's extension of the fractal intersection formulas in Euclidean space from Borel sets to arbitrary sets.


Sasha Melnikov

Title: Structures computable without delay

Abstract: Various effects related to unbounded search are usually overlooked in computable structure theory, yet there is a lot to say. Using primitive recursion we formally measure and compare unbounded delays in computable algebraic structures. The audience may find some of the results counterintuitive, and the technical depth of some proofs may seem unexpected. (The talk is based on 3 papers jointly written with Kalimullin and Ng.)


Reed Solomon

Title: Baire codes for Borel sets in reverse mathematics

Abstract: Statements involving Borel codes are difficult to handle below the level of ATR0 in reverse mathematics. One way to simplify the coding in certain settings is to replace the Borel sets by Baire codes. In this talk, I will give some motivation from the Dual Ramsey theorem for using Baire codes and I will discuss the complexity of finding Baire codes. This work is joint with Damir Dzhafarov, Stephen Flood and Linda Brown Westrick.

Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.