Monday, April 3rd, 2017 | 4pm-5pm | Burnside 1205 |

Warwick University

Elusive problems in extremal graph theory

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. We will show that this phenomenon is not true in general. In particular, we will find a counterexample to the following conjecture of Lovasz, which is often referred to as saying that "every extremal graph theory problem has a finitely forcible optimum": 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. The talk is based on joint work with Andrzej Grzesik and Laszlo Miklos Lovasz.