Lovász László Miklós: Graph limits and finite forcibility

Előadó: Lovász László Miklós

Cím: Graph limits, measures, and flows

Absztrakt: We study the uniqueness of optimal solutions to extremal graph theory problems. Our main result is a counterexample to a conjecture of Lovász. The conjecture 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 a unique graphon. Joint work with Andrzej Grzesik and Daniel Král.