This paper by László Lovász and Balázs Szegedy explores the limits of dense graph sequences. They show that if a sequence of dense graphs $ G_n $ has the property that the density of copies of every fixed graph $ F $ tends to a limit, then there exists a natural "limit object," a symmetric measurable function $ W : [0,1]^2 \to [0,1] $, which determines all the limits of subgraph densities. Conversely, every such function arises as a limit object. They also characterize graph parameters that are obtained as limits of subgraph densities by the "reflection positivity" property.
The paper introduces a general model of random graphs, called W-random graphs, which are defined by a symmetric measurable function $ W $. These graphs provide a way to represent the limit of a convergent graph sequence. The authors show that every random graph model satisfying certain natural criteria can be obtained as a W-random graph for an appropriate $ W $.
The main result is a characterization of graph parameters in the set $ T $, which consists of graph parameters that are limits of subgraph densities. The characterization is given in terms of three equivalent conditions: (a) the parameter is in $ T $; (b) it can be represented as a limit of subgraph densities; (c) it is normalized, multiplicative, and reflection positive. The paper also provides a detailed analysis of the properties of these graph parameters and their relationship to the concept of convergence in graph sequences.
The authors also discuss the convergence of graph sequences and the role of Szemerédi partitions in this context. They show that every graph sequence has a subsequence with well-behaved Szemerédi partitions, and that these partitions can be used to approximate the limit object of the sequence. The paper concludes with a discussion of the implications of these results for extremal graph theory and the characterization of graph parameters.This paper by László Lovász and Balázs Szegedy explores the limits of dense graph sequences. They show that if a sequence of dense graphs $ G_n $ has the property that the density of copies of every fixed graph $ F $ tends to a limit, then there exists a natural "limit object," a symmetric measurable function $ W : [0,1]^2 \to [0,1] $, which determines all the limits of subgraph densities. Conversely, every such function arises as a limit object. They also characterize graph parameters that are obtained as limits of subgraph densities by the "reflection positivity" property.
The paper introduces a general model of random graphs, called W-random graphs, which are defined by a symmetric measurable function $ W $. These graphs provide a way to represent the limit of a convergent graph sequence. The authors show that every random graph model satisfying certain natural criteria can be obtained as a W-random graph for an appropriate $ W $.
The main result is a characterization of graph parameters in the set $ T $, which consists of graph parameters that are limits of subgraph densities. The characterization is given in terms of three equivalent conditions: (a) the parameter is in $ T $; (b) it can be represented as a limit of subgraph densities; (c) it is normalized, multiplicative, and reflection positive. The paper also provides a detailed analysis of the properties of these graph parameters and their relationship to the concept of convergence in graph sequences.
The authors also discuss the convergence of graph sequences and the role of Szemerédi partitions in this context. They show that every graph sequence has a subsequence with well-behaved Szemerédi partitions, and that these partitions can be used to approximate the limit object of the sequence. The paper concludes with a discussion of the implications of these results for extremal graph theory and the characterization of graph parameters.