Michele Triestino

Random walks on graphs

M.Triestino планирует провести 4 занятия. 

I can hardly imagine a mathematical object that succesfully describes something related to real life as graphs can do. For istance, we can see people as vertices of a graph where edges correspond to human relations: A is connected to B if A and B know each other. Or, as a further example, railways and stations in Russia can be easily pictured by a graph. Everyone can find such examples and today it is quite usual to simplify objects by mean of graphs. Sometimes this is not a difficult task — you can easily draw the graph of the streets in Dubna — but, in general, objects are too big to be deeply understood (as the first example shows).

Random walks are a way to understand "big" graphs. We do not know the graph of Wikipedia, but if we start walking from a page to another following the links, we find that pages are usually well connected to pages dealing with related topics, but it is not so easy for example to go from the page "Random Walk" to the page "Dante Alighieri". Many natural questions can arise and perhaps most of them do not have an evident answer.

In this course I will start from the basic notions and tools in the theory of random walks and explain how graphs and random walks can be used in problems in Combinatorics or Group Theory (well, it's a Math course!) or in more concrete problems, as the Google Page Ranking algortihm shows.

A basic knolewdge of discrete probability and linear algebra will be helpful to follow the course.

Увы, я лишь чуть-чуть говорю по-русски — а мои уроки будут по-английски. I hope this will not be an obstacle to follow the course!

The planning of the course will be the following (I hope we could get till to the end of it!):

• First naive examples. Graphs. Random walks on integer lattices. Markov chains.
• Harmonic point of view: Green functions, Laplacians, networks…
• A conrete example: the Google ranking.
• Discrete to continuous: Brownian motion and the heat equation.
• Geometry of graphs. Quasi-isometries, automorphisms, ends…
• Random walks on groups (finite/infinite).

Organization Committee e-mail:
dubna@mccme.ru