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].
  1. R. Huq, B. Kamiński, A. Mashatan, P. Prałat, P. Szufel, On Broadcasting Time in the Model of Travelling Agents
  2. D.A. Levin, Y. Peres, E.L. Wilmer, Markov Chains and Mixing Times, second edition, (AMS, 2008 - first edition)
  3. 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
  4. N. Rivera, T. Sauerwald, J. Sylvester, Multiple Random Walks on Graphs: Mixing Few to Cover Many