Weak regularity and finitely forcible graph limits

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F18%3A43956061" target="_blank" >RIV/49777513:23520/18:43956061 - isvavai.cz</a>
Result on the web
<a href="https://www.ams.org/journals/tran/2018-370-06/S0002-9947-2018-07066-0/S0002-9947-2018-07066-0.pdf" target="_blank" >https://www.ams.org/journals/tran/2018-370-06/S0002-9947-2018-07066-0/S0002-9947-2018-07066-0.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1090/tran/7066" target="_blank" >10.1090/tran/7066</a>

Result language
angličtina
Original language name
Weak regularity and finitely forcible graph limits
Original language description
Graphons are analytic objects representing limits of convergent sequences of graphs. Lovász and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many subgraph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak ε-regular partition with the number of parts bounded by a polynomial in ε^{−1}. We construct a finitely forcible graphon W such that the number of parts in any weak ε-regular partition of W is at least exponential in ε^{−2}/2^{5 log* ε^{-2}}. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
Czech name
—
Czech description
—

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

Project
<a href="/en/project/GA14-19503S" target="_blank" >GA14-19503S: Graph coloring and structure</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)