COOPER, Jacob, Tomáš KAISER, Daniel KRÁĽ and Jonathan NOEL. Weak regularity and finitely forcible graph limits. Transactions of the American Mathematical Society. American Mathematical Society, 2018, vol. 370, No 6, p. 3833-3864. ISSN 0002-9947. Available from: https://dx.doi.org/10.1090/tran/7066.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Weak regularity and finitely forcible graph limits
Authors COOPER, Jacob, Tomáš KAISER, Daniel KRÁĽ and Jonathan NOEL.
Edition Transactions of the American Mathematical Society, American Mathematical Society, 2018, 0002-9947.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10101 Pure mathematics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 1.318
Doi http://dx.doi.org/10.1090/tran/7066
UT WoS 000428311400003
Keywords in English weak regularity; finitely forcible graph limits
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 13/1/2021 11:55.
Abstract
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 graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak epsilon-regular partition with the number of parts bounded by a polynomial in epsilon^-1. We construct a finitely forcible graphon W such that the number of parts in any weak epsilon-regular partition of W is at least exponential in epsilon ^-2/2^(5*logstar epsilon^-2). This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
PrintDisplayed: 19/7/2024 01:42