Lovász, László (ELTE)
Graph limits meet Markov chains
To define the limit of a sequence of graphs which are neither dense nor very
sparse is perhaps the most important question in graph limit theory. Several
convergence notions have been proposed (Frenkl, Kunszenti-Kovács – Lovász –
Szegedy, Backhausz – Szegedy), which interestingly lead to limit objects that
can be viewed as (continuous space) Markov chains with some added features. In
other words, the random walk ont he graph seems to be the key structure that
carries over to the limit.
This observation motivates a goal to see how various results in graph theory carry over to these limit objects. We show that flow theory has a very natural and simple generalization. Counting subgraphs (for example, triangles) is another basic method in graph theory. A generalization of this to the Markov chain setting is not straightforward, but with Kunszenti-Kovács and Szegedy we could develop a theory that covers a good part of graph sequences with intermediate density.
The talk is
held in English!
Az előadás
nyelve angol!
Date: Nov 2, Tuesday 4:15pm
Place: BME, Building „Q”, Room
QBF13