Limits of dense graph sequences
| dc.creator | Lovasz, Laszlo | |
| dc.creator | Szegedy, Balazs | |
| dc.date | 2004-08-12 | |
| dc.date | 2004-09-22 | |
| dc.date.accessioned | 2026-07-07T05:11:15Z | |
| dc.date.available | 2026-07-07T05:11:15Z | |
| dc.description | We show that if a sequence of dense graphs has the property that for every fixed graph F, the density of copies of F in these graphs tends to a limit, then there is a natural ``limit object'', namely a symmetric measurable 2-variable function on [0,1]. This limit object determines all the limits of subgraph densities. We also show that the graph parameters obtained as limits of subgraph densities can be characterized by ``reflection positivity'', semidefiniteness of an associated matrix. Conversely, every such function arises as a limit object. Along the lines we introduce a rather general model of random graphs, which seems to be interesting on its own right. | |
| dc.description | 27 pages; added extension of result (Sept 22, 2004) | |
| dc.identifier | https://arxiv.org/abs/math/0408173 | |
| dc.identifier | http://arxiv.org/abs/math/0408173 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/72177 | |
| dc.subject | Combinatorics | |
| dc.subject | 05CXX | |
| dc.title | Limits of dense graph sequences | |
| dc.type | text |