BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:Applications of convex optimization in extremal gr
aph theory - Will Perkins (School of Mathematics)
DTSTART:20180201T120000Z
DTEND:20180201T130000Z
UID:TALK3011AT
URL:/talk/index/3011
DESCRIPTION:Extremal graph theory deals with problems of maxim
izing and minimizing graph parameters over given c
lasses of finite graphs. For instance\, what d-re
gular graph on n vertices has the most matchings?
Or what cubic graph on n vertices has the most pro
per 5-colorings? I will describe how such extrema
l problems can be solved using techniques from con
vex optimization. In particular\, I will describe
a new method for solving extremal problems on bou
nded degree graphs using probabilistic models from
statistical physics and linear programming relaxa
tions. The talk will be aimed at an audience fami
liar with linear programming but with little or no
background in graph theory and statistical physic
s. \n\n
LOCATION:Lecture Theatre 2\, Strathcona Building
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR