Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777119 | Electronic Notes in Discrete Mathematics | 2017 | 7 Pages |
Abstract
We study the uniqueness of optimal solutions to extremal graph theory problems. Our main result is a counterexample to the following conjecture of Lovász, 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Andrzej Grzesik, Daniel Král', László Miklós Lovász,