Connectedness in graph limits - Mathematics > CombinatoricsReport as inadecuate

Connectedness in graph limits - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

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.

Author: Svante Janson



Related documents