Motywacją dla tego referatu jest problem postawiony w pracy [1],
dotyczący przekazywania sygnału (albo wirusa) przez agentów
poruszających się po pewnym grafie: jak oszacować czas propagacji
sygnału dla grafów pewnych klas w zależności od liczby agentów.
Wydaje się, że istotnym narzędziem dla rozwiązania tego problemu jest
analiza wielu współbieżnych błądzeń losowych, zapoczątkowana pracą [3].
Jest to dziedzina, o której wciąż, jako ludzkość, wiemy niewiele - choć
od niedawna trochę więcej [4]. Celem wystąpienia jest zapoznanie
uczestników seminarium (a w szczególności referującego) z tą tematyką. Z
uwagi na dużą rozbieżność między poziomem zaawansowania prac [3, 4] a
wiedzą referującego w dziedzinie łańcuchów Markowa, ich prezentacja
zostanie poprzedzona wprowadzeniem w teorię błądzeń po grafach w oparciu
o świetną książkę [2].
- R. Huq, B. Kamiński, A. Mashatan, P. Prałat, P. Szufel, On Broadcasting
Time in the Model of Travelling Agents
- D.A. Levin, Y. Peres, E.L. Wilmer, Markov Chains and Mixing Times,
second edition, (AMS, 2008 - first edition)
- N. Alon, C. Avin, M. Koucky, G. Kozma, Z. Lotker, M.R. Tuttle, Many
random walks are faster than one, Combin. Probab. Comput., 20 (2011),
481-502
- N. Rivera, T. Sauerwald, J. Sylvester, Multiple Random Walks on Graphs:
Mixing Few to Cover Many