Densest Subgraphs of a Dense Erdös-Rényi Graph. Asymptotics, Landscape and Universality

Houssam El Cheairi, David Gamarnik

We consider the problem of estimating the edge density of densest $K$-node subgraphs of an Erdös-Rényi graph $\mathbb{G}(n,1/2)$. The problem is well-understood in the regime $K=Θ(…