Penn Arts & Sciences Logo

Logic and Computation Seminar

Friday, January 14, 2011 - 2:00pm

Henry Towsner

UCLA

Location

University of Pennsylvania

DRL 4C4

Please note special day, time, and room.

Sophisticated theorems about finite structures often end up needing long strings of bounds with elaborate dependencies that can obscure the underlying elegance of the proof. Correspondence principles make it possible to prove an equivalent theorem in an infinite setting, usually a topological or measure-theoretic one, where the need for precise bounds disappears, and where powerful structure theorems can be brought to bear on the the problem. We will illustrate this method by taking a powerful but difficult method from graph theory --- the Szemeredi regularity lemma --- and outlining a short proof that avoids most of the need for exacting calculations. (No knowledge of the Szemeredi regularity lemma will be assumed!)