
The Library
Extremal graph theory and finite forcibility
Tools
Grzesik, Andrzej, Králʼ, Daniel and Lovasz, Laszlo Miklos (2017) Extremal graph theory and finite forcibility. Electronic Notes in Discrete Mathematics, 61 . pp. 541-547. doi:10.1016/j.endm.2017.07.005 ISSN 1571-0653.
|
PDF
WRAP-external-graph-theory-finite-Kral-017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (498Kb) | Preview |
Official URL: http://doi.org/10.1016/j.endm.2017.07.005
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´asz, 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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Extremal problems (Mathematics), Graph theory | ||||||||
Journal or Publication Title: | Electronic Notes in Discrete Mathematics | ||||||||
Publisher: | Elsevier BV | ||||||||
ISSN: | 1571-0653 | ||||||||
Official Date: | August 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 61 | ||||||||
Number of Pages: | 22 | ||||||||
Page Range: | pp. 541-547 | ||||||||
DOI: | 10.1016/j.endm.2017.07.005 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Description: | Proceedings of Eurocomb'17 |
||||||||
Date of first compliant deposit: | 6 June 2017 | ||||||||
Date of first compliant Open Access: | 3 August 2018 | ||||||||
Funder: | European Research Council (ERC), Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | 648509 (ERC), EP/M025365/1 (EPSRC) | ||||||||
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