The Library
Elusive extremal graphs
Tools
Tools
Tools
Grzesik, Andrzej, Králʼ, Daniel and Lovász, Miklós (2020) Elusive extremal graphs. Proceedings of the London Mathematical Society, 121 (6). pp. 1685-1736. doi:10.1112/plms.12382 ISSN 0024-6115.
|
PDF
WRAP-Elusive-extremal-graphs-Kral-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1275Kb) | Preview |
Official URL: https://doi.org/10.1112/plms.12382
Abstract
We study the uniqueness of optimal solutions to extremal graph theory problems. Lovász 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.
| Item Type: | Journal Article | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory , Extremal problems (Mathematics) | |||||||||||||||
| Journal or Publication Title: | Proceedings of the London Mathematical Society | |||||||||||||||
| Publisher: | London Mathematical Society | |||||||||||||||
| ISSN: | 0024-6115 | |||||||||||||||
| Official Date: | December 2020 | |||||||||||||||
| Dates: |
|
|||||||||||||||
| Volume: | 121 | |||||||||||||||
| Number: | 6 | |||||||||||||||
| Page Range: | pp. 1685-1736 | |||||||||||||||
| DOI: | 10.1112/plms.12382 | |||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||
| Publication Status: | Published | |||||||||||||||
| Reuse Statement (publisher, data, author rights): | This is the accepted version of the following article: Grzesik, A., Král, D. and Lovász, L.M. (2020), Elusive extremal graphs. Proc. London Math. Soc., 121: 1685-1736. doi:10.1112/plms.12382 which has been published in final form at https://doi.org/10.1112/plms.12382. | |||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
| Copyright Holders: | The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. | |||||||||||||||
| Date of first compliant deposit: | 14 August 2020 | |||||||||||||||
| Date of first compliant Open Access: | 22 January 2021 | |||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
