Fri Oct 8, 2010
60 Evans Hall, 4:10–6 PM
Henry Towsner (University of California, Los Angeles)
The Infinitary Approach to Finite Combinatorics
The “Correspondence Principle” makes it possible to take combinatorial problems about finite structures and translate them into questions about infinitary, measure-theoretic structures. While there are fairly elementary combinatorial approaches, it has recently become clear that the model-theoretic approach creates a particularly rich and flexible infinitary structure. We will outline the model-theoretic proof of the correspondence principle and point out some of its new applications. To illustrate the flexibility of this method, we will give a short proof of the Szemeredi regularity lemma, an important tool in the study of finite graphs.
The biweekly LOGIC TEA will be held in the Alfred Tarski Room (727 Evans Hall) immediately following the Colloquium (with support from the Graduate Assembly).