Cover times of random walks on graphs

• Grant number: 14/25389-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: March 01, 2015
• End date: February 29, 2016
• Field of knowledge: Physical Sciences and Mathematics - Probability and Statistics - Probability
• Principal Investigator: Serguei Popov
• Grantee: Victor Seixas Souza
• Host Institution: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

A simple random walk on a graph is a sequence of movements from a vertex to an adjacent vertex in such that each step is chosen uniformly randomly distributed across the neighborhood of the current vertex. The cover time of a random walk is the first moment where each vertex of the graph was visited. We are interested on the expected time for the cover time of specific families of graphs. Hypercubes are graphs of utmost importance in several contexts and random walks on hypercubes are a rich source of problems. From multiple standpoints over random walks on hypercubes, we'll study their cover times and all the companion literature to this problem.