Department of
Applied
Mathematics

Uniqueness of optimal configurations in extremal combinatorics

Dan Kráµ

Abstract

The theory of graph limits aims at providing tools to analyze and model large graphs. In particular, the analytic models of large dense graphs are closely related to the flag algebra method, which has found many applications in extremal combinatorics. In this talk, we will address the uniqueness of optimal configurations in extremal combinatorics using the tools of the theory of graph limits. 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 disprove 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 will be self-contained and no previous knowledge of the area is needed. The results presented in the talk are based on joint work with Andrzej Grzesik and Laszlo Miklos Lovasz.