A Tale of Two Theorems: Calibrating Mathematical Complexity
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.