ICE-TCS seminar joint with the Icelandic Mathematical Society: Páll Melsted, UI

  • 30.11.2012, 14:00 - 15:00

Speaker: Páll Melsted, UI

When: Friday, November 30th, 2012, 2pm
Where: M109, Reykjavik University, Menntavegur 1
Title: The greatest theorem you'll never use!

Abstract: In this talk I will review Szemeredi's Regularity Lemma, a surprisingly powerful theorem in graph theory with many "applications" but astronomically large hidden constants. The regularity lemma states that all "large enough" graphs can be partitioned into very regular subgraphs, such that the edges between subgraphs are almost random. The lemma was used to prove Szemeredis Theorem on arithmetic progressions. We will then look at more "practical" algorithmic variants of the Lemma and finally see a real application to clustering. This talk will be self contained and require no more than elementary knowledge of graph theory.

Endre Szemeredi is this years Abel prize winner