The Library
Finitely forcible graph limits are universal
Tools
Cooper, Jacob W., Králʼ, Daniel and Martins, Taísa L. (2018) Finitely forcible graph limits are universal. Advances in Mathematics, 340 . pp. 819-854. doi:10.1016/j.aim.2018.10.019 ISSN 0001-8708.
|
PDF
WRAP-finitely-forcible-graph-universal-Kral-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (733Kb) | Preview |
Official URL: http://doi.org/10.1016/j.aim.2018.10.019
Abstract
The theory of graph limits represents large graphs by analytic objects called graphons. Graph limits determined by finitely many graph densities, which are represented by finitely forcible graphons, arise in various scenarios, particularly within extremal combinatorics. Lovasz and Szegedy conjectured that all such graphons possess a simple structure, e.g., the space of their typical vertices is always finite dimensional; this was disproved by several ad hoc constructions of complex finitely forcible graphons. We prove that any graphon is a subgraphon of a finitely forcible graphon. This dismisses any hope for a result showing that finitely forcible graphons possess a simple structure, and is surprising when contrasted with the fact that finitely forcible graphons form a meager set in the space of all graphons. In addition, since any finitely forcible graphon represents the unique minimizer of some linear combination of densities of subgraphs, our result also shows that such minimization problems, which conceptually are among the simplest kind within extremal graph theory, may in fact have unique optimal solutions with arbitrarily complex structure.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
|||||||||||||||
Library of Congress Subject Headings (LCSH): | Graph theory | |||||||||||||||
Journal or Publication Title: | Advances in Mathematics | |||||||||||||||
Publisher: | Academic Press | |||||||||||||||
ISSN: | 0001-8708 | |||||||||||||||
Official Date: | 15 December 2018 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 340 | |||||||||||||||
Page Range: | pp. 819-854 | |||||||||||||||
DOI: | 10.1016/j.aim.2018.10.019 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Reuse Statement (publisher, data, author rights): | © 2018, Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/. | |||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||
Date of first compliant deposit: | 10 October 2018 | |||||||||||||||
Date of first compliant Open Access: | 24 October 2019 | |||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year