Elusive problems in extremal graph theory

Graph Theory Seminar
Thursday, May 18, 2017 - 15:05
1 hour (actually 50 minutes)
Skiles 005
University of Warwick
We study the uniqueness of optimal configurations in extremal combinatorics. An empirical experience suggests that optimal solutions to extremal graph theory problems can be made asymptotically unique by introducing additional constraints. Lovasz conjectured that this phenomenon is true in general: every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints such that the resulting set is satisfied by an asymptotically unique graph. We will present a counterexample to this conjecture and discuss related results. The talk is based on joint work with Andrzej Grzesik and Laszlo Miklos Lovasz.