Program



Start January 21, 2013
End June 28, 2013.
Recess  February 17 to March 2, 2013 (in these two weeks many participants will be out of town).


The official activities consist of two weekly seminars starting in January and a graduate-level reading course starting in March.
Most of the schedule is open for individual and small-group research.

Seminar on Open Questions

coordinated by Noam Greenberg and Antonio Montalbán
Once a week, January to June 2013
Wednesdays, 11:00 to 13:00, in the Seminar Room in the first floor

Current research will be presented and discussed in this seminar. Stand-alone talks will be given mostly by short-term visitors. Speakers will present the work that they are currently doing and the most recent developments within it. Thus, the presentations may not be as polished as standard conference talks but will provide an opportunity to discuss techniques and arguments in some detail. Active audience engagement will be encouraged.

Seminar on Selected Topics

coordinated by Joe Miller
twice a week, January to June 2013
Tuesdays and Thursdays, 11:00 to 13:00, in the Seminar Room in the first floor

This seminar will be a sequence of mini-courses in which the participants take turns presenting on a specific topic, with each topic spanning several meeting times. The emphasis will be on mastering the material in depth. Possible topics include randomness extractors and expander graphs, randomness and computable analysis, and conservation results in reverse mathematics.

Course on Combinatorics, Complexity and Logic

by Ted Slaman
once a week, March to June 2013

We will explore the interplay between the specification of mathematical problems, especially in combinatorics, and the descriptive complexity of their solutions. Applied in one direction, we obtain simple combinatorial problems that can have an intrinsically complicated solutions, such as finding a Hamiltonian path in a graph or finding a homogeneous set for a computable partition. In the other direction, we combinatorially analyze semantics to exhibit limits on what can be described or what can be proven, such as in Razborov's theorems on the limits of definability by monotone circuits or as in the Paris-Harrington example of a natural incompleteness in elementary arithmetic .

Course Outline:
  1. Basic Ramsey Theory
  2. Finite combinatorics and complexity theory
    1. Introduction to circuit complexity
    2. Razborov's Theorem
  3. Infinitary combinatorics and computabilty theory
    1. Introduction to computability theory
    2. Computational analysis of Ramsey's Theorem
    3. Ramsey's Theorem for Pairs in detail
  4. Infinitary combinatorics with finitary consequences
    1. Mathematical logic and formal theories of arithmetic
    2. Incompleteness theorems
    3. Conservation theorems for infinitary principles
    4. The Paris-Harrington Theorem, a finite combinatorial principle not provable by elementary methods

Supplementary Reading Material:
  1. W. T. Gowers. Razborov's method of approximations. lecture notes, 2009.
  2. David Seetapun and Theodore A. Slaman. On the strength of Ramsey's theorem. Notre Dame J. Formal Logic, 36(4):570-582, 1995.
  3. Leo A. Harrington. A mathematical incompleteness in Peano arithmetic. In Jon Barwise, editor, Handbook of mathematical logic, volume 90 of Studies in Logic and the Foundations of Mathematics, pages 1133-1142. North-Holland Publishing Co., Amsterdam, 1977.

General References:
  1. Robert I. Soare. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.
  2. H.-D. Ebbinghaus, J. Flum, and W. Thomas. Mathematical logic. Undergraduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1994.
  3. Richard Kaye. Models of Peano arithmetic, volume 15 of Oxford Logic Guides. The Clarendon Press Oxford University Press, New York, 1991.
  4. Stephen G. Simpson. Subsystems of second order arithmetic. Perspectives in Logic. Cambridge University Press, Cambridge, second edition, 2009.