Conjecture on the landscape of planted dense subgraphs and overlap gaps

Let $G$ be the planted-clique model with planted clique $\mathcal{PC}$, let $k$ satisfy

$$(\log n)^5\leq k=o(n),$$

and let $\epsilon\in(0,1)$. Write $\bar{k}$ for the subgraph size, $\mathcal{D}_{\bar{k},k}(G)$ for the dense-subgraph optimization problem, $d_{\bar{k},k}(G)(z)$ for its value at overlap $z$ with $\mathcal{PC}$, and $\mathcal{I}$ for the relevant set of admissible overlaps. The notation $\bar{k}$-Overlap Gap Property means the overlap-gap property at subgraph size $\bar{k}$; $o(\cdot)$ and $\omega(\cdot)$ have their usual asymptotic meanings, and “w.h.p.” means with high probability as $n\to+\infty$. There are constants $C_0,D_1,D_2,E$ as in the statement, with $0<D_1<D_2$.

Landscape conjecture. Suppose

$$(\log n)^5\leq k=o(n).$$

If $k=o(\sqrt n)$, then:

• for every $\bar{k}=o\left(k^2\log\left(\frac{n}{k^2}\right)\right)$, the $\bar{k}$-Overlap Gap Property holds w.h.p.;
• for every $\bar{k}=\omega\left(k^2\log\left(\frac{n}{k^2}\right)\right)$, the $\bar{k}$-Overlap Gap Property does not hold, $d_{\bar{k},k}(G)(z)$ is decreasing in $z$ w.h.p., and near-optimal solutions of $\mathcal{D}_{\bar{k},k}(G)$ are uninformative for recovering $\mathcal{PC}$.

If $k=\omega(\sqrt n)$, then:

• for every $\bar{k}=o\left(\frac{n^2}{k^2\log\left(\frac{k^2}{n}\right)}\right)$, the $\bar{k}$-Overlap Gap Property holds w.h.p.;
• for every

$$\omega\left(\frac{n^2}{k^2\log\left(\frac{k^2}{n}\right)}\right)=\bar{k}=o(n),$$

the $\bar{k}$-Overlap Gap Property does not hold, $d_{\bar{k},k}(G)(z)$ is increasing in $z$ w.h.p., and near-optimal solutions are informative for recovering $\mathcal{PC}$.

Furthermore, whenever the $\bar{k}$-Overlap Gap Property holds, there are constants $0<D_1<D_2$ and $E>0$ such that, with

$$u_1=D_1\left\lceil\sqrt{\frac{\bar{k}}{\log(n/\bar{k})}}\right\rceil,\qquad u_2=D_2\left\lceil\sqrt{\frac{\bar{k}}{\log(n/\bar{k})}}\right\rceil,$$

for sufficiently large $n$,

$$\left\lfloor C_0\frac{\bar{k}k}{n}\right\rfloor<u_1<u_2<(1-\epsilon)k,$$ $$\max_{z\in\mathcal{I}\cap[u_1,u_2]}d_{\bar{k},k}(G)(z)+\Omega\left(\frac{\bar{k}}{\log(n/\bar{k})}\right)\leq d_{\bar{k},k}(G)\left(\left\lfloor C_0\frac{\bar{k}k}{n}\right\rfloor\right)\leq d_{\bar{k},k}(G)((1-\epsilon)k),$$

and $d_{\bar{k},k}(G)(z)$ is increasing for

$$z\in\left[E\sqrt{\bar{k}\log\frac{n}{\bar{k}}},(1-\epsilon)k\right],$$

all w.h.p. as $n\to+\infty$.

This conjecture predicts when the dense-subgraph landscape is informative about the planted clique and when it exhibits an overlap gap. The stated thresholds distinguish the regimes $k=o(\sqrt n)$ and $k=\omega(\sqrt n)$; the final inequalities describe the separation and monotonicity expected in the OGP regime.