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.

The planted clique graph G(n, p, k) is the random graph on n vertices in which each edge is added independently with probability p and then a k-set of its vertices is chosen uniformly and made into a clique - the planted clique. This model was suggested independently by Jerrum (1992) and Kucera (1995) to describe the planted clique problem, which consists in recovering the planted clique of a graph drawn from G(n, p, k). A first development since the problem was proposed was provided by Alon-Krivelevich-Sudakov (1998): An efficient spectral algorithm that almost surely finds the planted clique of G(n, 1/2, k), with k >= 10 n^1/2. Since then, other algorithms were found for k = Omega(n^1/2); but the problem remains unsolved for k = o(n^1/2); a fact that has been used as a hardness assumption in several works. The algorithm presented by Alon-Krivelevich-Sudakov relies on the behavior of the largest eigenvalues of A and on properties of the eigenvector of its second largest eigenvalue. Similar phenomena was observed by Nadakuditi (2012) when considering the B = A - E matrix, where E is the expected matrix of A with k = 0. While Alon-Krivelevich-Sudakov's analysis does not provide insights that explain the behavior of the spectrum of A, Nadakuditi takes some steps towards an explanation by showing a relationship between B and a particular class of zero-mean symmetric random matrices whose spectrum is well studied - the Wigner matrices. The approach followed by Nadakuditi was described and exemplified by Nadakuditi-Newman (2012), when it was presented as a manner to study the spectrum of the so-called stochastic block model, which generalizes many random graphs with planted structures. Inspired by Nadakuditi-Newman's approach, we show how the spectral behavior of A and B can be explained by regarding those matrices as the result of rank-one perturbations over Wigner matrices. Besides studying those matrices under the G(n, p, k) distribution, we also consider analogous matrices for a variant with loops of the planted clique graph. Furthermore, we offer a more detailed and complete characterization of the spectrum of those matrices under k = O((n log n)^1/2) and kq >= c(pqn)^1/2, with c > 3; showing that besides a few of the largest and smallest eigenvalues, all the others almost surely are distributed according to a semicircular law - which is the characteristic distribution of the spectra of Wigner matrices.