Elusive extremal graphs

GRZESIK, Andrzej, Daniel KRÁĽ and Laszlo Miklos LOVASZ. Elusive extremal graphs. Proceedings of the London mathematical society. Cambridge: Cambridge University Press, 2020, vol. 121, No 6, p. 1685-1736. ISSN 0024-6115. Available from: https://dx.doi.org/10.1112/plms.12382.

Basic information

Original name

Elusive extremal graphs

Authors

GRZESIK, Andrzej (616 Poland), Daniel KRÁĽ (203 Czech Republic, guarantor, belonging to the institution) and Laszlo Miklos LOVASZ (840 United States of America)

Edition

Proceedings of the London mathematical society, Cambridge, Cambridge University Press, 2020, 0024-6115

---

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United Kingdom of Great Britain and Northern Ireland

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

URL

Impact factor

Impact factor: 1.303

RIV identification code

RIV/00216224:14330/20:00118499

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1112/plms.12382

UT WoS

000594908500007

Keywords in English

extremal graph theory

Tags

International impact, Reviewed

---

Abstract

V originále

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.