Ipari és társadalomtudományi alkalmazott matematika
Matematika
Számítás- és információtudomány
We show that if a sequence of dense graphs G, has the property that for every fixed
graph F, the density of copies of F in G, tends to a limit, then there is a natural
"limit object," namely a symmetric measurable function W: [0, 1](2) ->. [0, 1]. This
limit object determines all the limits of subgraph densities. Conversely, every such
function arises as a limit object. We also characterize graph parameters that are
obtained as limits of subgraph densities by the "reflection positivity" property.
Along the way we introduce a rather general model of random graphs, which seems to
be interesting on its own right. (c) 2006 Elsevier Inc. All rights reserved.
