118. Mathematical Colloquium

aula (refektar), 1st floor MFF UK, Malostranské nám. 25, Praha 1

By a well-known result of Lipton and Tarjan, a planar graph with n vertices can be split into two parts of approximately the same size by removing roughly square root of n vertices. Such sublinear separators in planar graphs and other hereditary graph classes play an important role both in theory and in algorithmic design.

Does the presence of sublinear separators in a hereditary graph class by itself enforce some kind of structural constraints? Somewhat surprisingly, this seems to be the case. I will present recent results and conjectures on this topic.

Zdeněk Dvořák se narodil v roce 1981 a studoval na MFF UK, kde je dnes docentem (a v brzké době má být jmenován profesorem). Po dokončení PhD (2013) byl zaměstnán na Georgia Institute of Technology a pak na Simon Fraser University. Je mezinárodně známým odborníkem v oblasti kombinatoriky a zvláště pak strukturální teorie grafů, kde publikoval přes 100 prací v časopisech a sbornících konferencí. V současnosti je výkonným redaktorem JCTB a vedoucím redaktorem časopisu Electronic Journal of Combinatorics. Za svou práci získal několik ocenění, např. Evropskou cenu za kombinatoriku (2015). Zdeněk je také aktivní vedoucí týmu v mezinárodních informatických soutěžích (např. ACM ICPC).