**NB:** A

PDF
version of this announcement (suitable for posting) is also available.

## A Tale of Two Theorems: Calibrating Mathematical Complexity

### Joseph Mileti

Dartmouth College

###
Thursday, January 22, 2009

007 Kemeny Hall, 4 pm

Tea 3:30 pm, 300 Kemeny Hall

**Abstract: **
How complicated are ideals of a ring relative to the complexity of the operations of the ring? How about the complexity of the maximum values of a continuous functions on [0,1] relative to the function? Or of matchings relative to the complexity of a graph? The area of computability theory has tools for making such questions precise and methods relevant to their answers. In particular, it provides various hierarchies by which we can measure the complexity of rings, functions, graphs, and other objects, and techniques for carrying out such measurements.\par After introducing the relevant background from computability theory, we will consider two theorems from infinite Ramsey Theory. To understand how these theorems relate to each other, we will take a detour through the concept of computable randomness (an attempt to give meaning to when an infinite sequence of 0's and 1's is random). With this notions in hand, we will be able to definitely show that one theorem is "harder" than the other.

This talk will be accessible to undergraduates.