Back to Search Start Over

Elusive extremal graphs

Authors :
Grzesik, Andrzej
Král', Daniel
Lovász, László Miklós
Publication Year :
2018

Abstract

We study the uniqueness of optimal solutions to extremal graph theory problems. Lovasz conjectured that every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints so that the resulting set is satisfied by an asymptotically unique graph. This statement is often referred to as saying that `every extremal graph theory problem has a finitely forcible optimum'. We present a counterexample to the conjecture. Our techniques also extend to a more general setting involving other types of constraints.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1807.01141
Document Type :
Working Paper
Full Text :
https://doi.org/10.1112/plms.12382