Uma análise espectral do grafo com clique plantada (2022)
- Authors:
- Autor USP: LIU, FÉLIX YOWTANG - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2022.tde-30012023-194317
- Subjects: ANÁLISE ESPECTRAL; GRAFOS ALEATÓRIOS
- Keywords: 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
- Agências de fomento:
- Language: Português
- Abstract: 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 matrizesde 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
- Imprenta:
- Data da defesa: 15.12.2022
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
LIU, Félix Yowtang. Uma análise espectral do grafo com clique plantada. 2022. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2022. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-30012023-194317/. Acesso em: 18 set. 2024. -
APA
Liu, F. Y. (2022). Uma análise espectral do grafo com clique plantada (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-30012023-194317/ -
NLM
Liu FY. Uma análise espectral do grafo com clique plantada [Internet]. 2022 ;[citado 2024 set. 18 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-30012023-194317/ -
Vancouver
Liu FY. Uma análise espectral do grafo com clique plantada [Internet]. 2022 ;[citado 2024 set. 18 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-30012023-194317/
Informações sobre o DOI: 10.11606/D.45.2022.tde-30012023-194317 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
