Uma análise espectral do grafo com clique plantada

• Ano de defesa: 2022
• Autor(a) principal: Liu, Félix Yowtang
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Análise espectral; Clique escondida; Hidden clique; Lei semicircular; Matrix perturbation theory; Random matrix theory; Semicircle law; Spectral analysis; Teoria de matrizes aleatórias; Teoria de perturbação de matrizes
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-30012023-194317/

O grafo com clique plantada G(n, p, k) é o grafo aleatório com n vértices em que cada aresta é incluída independentemente com probabilidade p e então um k-conjunto de seus vértices sorteado uniformemente é feito uma clique - a sua clique plantada. Tal modelo foi sugerido independentemente por Jerrum (1992) e Kucera (1995) para propor o problema da clique plantada, que consiste em encontrar a clique plantada de um grafo de G(n, p, k). Um primeiro avanço desde a sugestão do problema foi apresentado por Alon-Krivelevich-Sudakov (1998): Um algoritmo espectral de tempo polinomial que quase certamente encontra a clique plantada do G(n, 1/2, k), com k >= 10 n^(1/2). Desde então foram encontrados outros algoritmos que resolvem o problema com k = Omega(n^1/2); mas o problema continua em aberto para k = o(n^1/2). Devido a isso, tal fato já foi usado como suposição de intratabilidade em alguns trabalhos. O algoritmo de Alon-Krivelevich-Sudakov depende de certas propriedades dos maiores autovalores de A e do autovetor associado ao seu segundo maior autovalor. Nadakuditi (2012) observou fenômenos semelhantes ao estudar a matriz B = A - E, onde E é esperança de A quando se considera k = 0. Enquanto a análise de Alon-Krivelevich-Sudakov não explicita motivos que expliquem o comportamento do espectro de A, Nadakuditi dá passos na direção de elucidar tais fenômenos ao mostrar uma relação entre B e uma classe particular de matrizes simétricas aleatórias de média zero - as chamadas matrizes de Wigner - cujo espectro é bem estudado. A abordagem adotada por Nadakuditi foi descrita e exemplificada por Nadakuditi-Newman (2012), quando foi apresentada como uma forma de se estudar o espectro do chamado modelo de blocos estocástico, o qual generaliza muitos grafos aleatórios com estruturas plantadas. Motivado pela abordagem de Nadakuditi-Newman, o presente trabalho mostra como os comportamentos dos espectros de A e de B podem ser explicados ao considerar essas matrizes como resultantes da aplicação de perturbações de posto um sobre matrizes de Wigner. Além de estudar tais matrizes da distribuição G(n, p, k), matrizes análogas para uma variante com laços do grafo com clique plantada também são consideradas. Ademais, este trabalho oferece uma caracterização mais detalhada e completa do espectro dessas matrizes para o caso k = O((n log n)^1/2) e kq >= c(pqn)^1/2, com c > 3; mostrando que com exceção de uns poucos dos maiores e menores autovalores, os demais quase certamente se distribuem seguindo uma distribuição semicircular distribuição característica dos espectros de matrizes de Wigner.