Connectedness in graph limits - Mathematics > CombinatoricsReportar como inadecuado

Connectedness in graph limits - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We define direct sums and a corresponding notion of connectedness for graphlimits. Every graph limit has a unique decomposition as a direct sum ofconnected components. As is well-known, graph limits may be represented bysymmetric functions on a probability space; there are natural definitions ofdirect sums and connectedness for such functions, and there is a perfectcorrespondence with the corresponding properties of the graph limit. Similarly,every graph limit determines an infinite random graph, which is a.s. connectedif and only if the graph limit is connected. There are also characterizationsin terms of the asymptotic size of the largest component in the correspondingfinite random graphs, and of minimal cuts in sequences of graphs converging toa given limit.

Autor: Svante Janson



Documentos relacionados