Finding Dense Subgraphs in G(n,1/2)

Atish Das Sarma, Amit Deshpande, Ravi Kannan

Finding the largest clique is a notoriously hard problem, even on random graphs. It is known that the clique number of a random graph G(n,1/2) is almost surely either k or k+1, whe…