Elusive extremal graphs

GRZESIK, Andrzej; Daniel KRÁĽ a Laszlo Miklos LOVASZ. Elusive extremal graphs. Proceedings of the London mathematical society. Cambridge: Cambridge University Press, 2020, roč. 121, č. 6, s. 1685-1736. ISSN 0024-6115. Dostupné z: https://doi.org/10.1112/plms.12382.

Základní údaje

Originální název

Elusive extremal graphs

Autoři

GRZESIK, Andrzej; Daniel KRÁĽ a Laszlo Miklos LOVASZ

Vydání

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

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Velká Británie a Severní Irsko

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 1.303

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/20:00118499

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.1112/plms.12382

UT WoS

000594908500007

EID Scopus

2-s2.0-85097065424

Klíčová slova anglicky

extremal graph theory

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

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.