The Library
Extremal graph theory and finite forcibility
Tools
Tools
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
