The Library
Weak regularity and finitely forcible graph limits
Tools
Tools
Tools
Cooper, Jacob W., Kaiser, Tomas, Králʼ, Daniel and Noel, Jonathan (2018) Weak regularity and finitely forcible graph limits. Transactions of the American Mathematical Society . doi:10.1090/tran/7066 ISSN 0002-9947.
|
PDF
WRAP-forcible-graph-limits-Kral-2018.pdf - Accepted Version - Requires a PDF viewer. Download (778Kb) | Preview |
Official URL: https://doi.org/10.1090/tran/7066
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 $ \varepsilon $-regular partition with the number of parts bounded by a polynomial in $ \varepsilon ^{-1}$. We construct a finitely forcible graphon $ W$ such that the number of parts in any weak $ \varepsilon $-regular partition of $ W$ is at least exponential in $ \varepsilon ^{-2}/2^{5\log ^*\varepsilon ^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
| Item Type: | Journal Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
| Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Graph theory | ||||||||||||
| Journal or Publication Title: | Transactions of the American Mathematical Society | ||||||||||||
| Publisher: | American Mathematical Society | ||||||||||||
| ISSN: | 0002-9947 | ||||||||||||
| Official Date: | 28 February 2018 | ||||||||||||
| Dates: |
|
||||||||||||
| DOI: | 10.1090/tran/7066 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| Date of first compliant deposit: | 12 September 2016 | ||||||||||||
| Date of first compliant Open Access: | 9 March 2018 | ||||||||||||
| Funder: | Czech Science Foundation (CSF) | ||||||||||||
| Grant number: | GA14-19503 (CSF) | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Is Part Of: | EPSRC Standard Grant number EP/M025365/1 ERC grant agreement no. 259385 | ||||||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
