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.