 |
|
Session 27. Probabilistic and Extremal Combinatorics |
Graph limits via discrete potential theory |
| Rudolf Grübel, Leibniz Universität Hannover, Germany |
|
We present a probabilistic approach to the currently very active area of
graph limits; see [3] for background and references. Many
of the models considered in this area can be regarded as combinatorial
Markov chains \(X=(X_n)_{n\in\mathbf{N}}\) that are adapted to the family \(\mathcal{G}\)
of finite simple graphs in the sense that \(X_n\) takes its values in the
subset \(\mathcal{G}_n\) of graphs with \(n\) nodes. For stochastic
processes of this kind discrete potential theory, as initiated by Doob
in [1], provides a state space compactification with the
properties that \(X_n\) converges to some \(X_\infty\) with values in the
boundary \(\partial\mathcal{G}\), and that fully captures the persisting
randomness of the process in the sense that the limit \(X_\infty\)
generates the tail \(\sigma\)-field associated with \(X\). We review
these concepts and then apply them to several popular graph models. |
References
|
| Print version |