Tempos de recobrimento de passeios aleatórios em grafos

• Processo: 14/25389-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de março de 2015
• Data de Término da vigência: 29 de fevereiro de 2016
• Área de conhecimento: Ciências Exatas e da Terra - Probabilidade e Estatística - Probabilidade
• Pesquisador responsável: Serguei Popov
• Beneficiário: Victor Seixas Souza
• Instituição Sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Passeios aleatórios Grafos Cadeias de Markov Vértices Hipercubo
• Palavra(s)-Chave do Pesquisador: cadeias de Markov | grafos | Passeios Aleatórios | Tempo de recobrimento | Cadeias de Markov

Resumo

Um passeio aleatório simples em um grafo é uma sequência de movimentos de um vértice a outro adjacente tal que cada passo é escolhido de forma aleatória e uniformemente na vizinhança do vértice atual. O tempo de recobrimento de um passeio aleatório é o primeiro momento tal que todo vértice do grafo foi visitado. Estamos interessados no valor esperado do tempo de recobrimento em famílias específicas de grafos. O hipercubo é um grafo de suma importância em diversos contextos e passeios aleatórios no hipercubo são uma fonte rica de problemas. A partir de múltiplas visões sobre passeio aleatório num hipercubo, pretende-se estudar o tempo de recobrimento do mesmo e toda a literatura que acompanha o problema.