76 KAM Mathematical Colloquium
Benny Sudakov
(UCLA, USA)
EXTREMAL GRAPH THEORY AND ITS APPLICATIONS
pondeli 14. brezna 2011 v 15:40, poslucharna S5, 2. patro
KAM MFF UK
Malostranske nam. 25
118 00 Praha 1
Abstract
In typical extremal problem one wants to determine maximum cardinality of discrete structure with certain prescribed properties. Probably the earliest such result was obtain 100 years ago by Mantel who computed the maximum number of edges in a triangle free graph on n vertices. This was generalized by Turan for all complete graphs and became a starting point of Extremal Graph Theory. In this talk we survey several classical problems and results in this area and present some interesting applications of Extremal Graph Theory to other areas of mathematics. We also describe a recent surprising generalization of Turan's theorem which was motivated by question in Computational Complexity.O přednášejícím
Benny Sudakov je jednim z nejznamejsich kombinatoriku soucasnosti. Vystudoval v Tbilisi a v Tel Avivu, kde ziskal doktorat pod vedenim Nogy Alona. Pak byl zamestnan na Univerzite (a rovnez v Ustavu pokrocilych studii IAS) v Princetonu a od roku 2007 je radnym profesorem na Kalifornske univerzite v Los Angeles. Je autorem pres 110 praci hlavne v ruznych oblastech kombinatoriky: v algebraickych a pravdepodobnostnich metodach, teorii grafu, extremalni kombinatorice, Ramseyove teorii, nahodnych strukturach a v aplikacich kombinatoriky v teoreticke informatice. Je autorem rady vynikajicich vysledku---z posledni doby zminme alespon metodu tzv. dependent random choice, ktera nasla nekolik prekvapivych aplikaci. Za svou praci byl opakovane vyznamenan udelenim prestiznich grantu, napr. Rothschild Postdoctoral Fellowship, Sloan Fellowship, NSF Career Award. V roce 2010 prednesl zvanou prednasku na Mezinarodnim kongresu matematiku v indickem Hajdarabadu. Benny je znamym organizatorem vedecke prace, je editorem sedmi mezinarodnich casopisu a publikacnich rad, organizoval specialni semestr na IPAM (Institute for Pure and Applied Mathematics) a rovnez radu vynikajicich workshopu na DIMACS a v Oberwolfachu.Bennyho prednasky jsou velmi pekne, coz se odrazi i v rade jeho vynikajicich zaku. Prazske kolokvium se tyka hlavni oblasti jeho zajmu.
