Finitely forcible graph limits are universal
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00106842" target="_blank" >RIV/00216224:14330/18:00106842 - isvavai.cz</a>
Result on the web
<a href="https://arxiv.org/abs/1701.03846" target="_blank" >https://arxiv.org/abs/1701.03846</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.aim.2018.10.019" target="_blank" >10.1016/j.aim.2018.10.019</a>
Alternative languages
Result language
angličtina
Original language name
Finitely forcible graph limits are universal
Original language description
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. (C) 2018 Elsevier Inc. All rights reserved.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
V - Vyzkumna aktivita podporovana z jinych verejnych zdroju
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Advances in Mathematics
ISSN
0001-8708
e-ISSN
—
Volume of the periodical
340
Issue of the periodical within the volume
December
Country of publishing house
US - UNITED STATES
Number of pages
36
Pages from-to
819-854
UT code for WoS article
000451363700020
EID of the result in the Scopus database
2-s2.0-85055086923