Weak regularity and finitely forcible graph limits

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Weak regularity and finitely forcible graph limits

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Weak regularity and finitely forcible graph limits

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA14-19503S" target="_blank" >GA14-19503S: Barevnost a struktura grafů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

Kód důvěrnosti údajů

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

Název periodika

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY

ISSN

0002-9947

e-ISSN

—

Svazek periodika

370

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

32

Strana od-do

3833-3864

Kód UT WoS článku

000428311400003

EID výsledku v databázi Scopus

2-s2.0-85044404667