The largest clique problem is another example where the OGP based predictions
are consistent with the state of the art algorithms.
Recall from the earlier section, that while the largest clique in \(\mathbb {G}(N,1/2)\) 
is roughly \(2\log _2 N\) , the largest size clique achievable by known algorithm
is roughly half-optimal with size approximately \(\log _2 N\) . Fixing \(\alpha \in (1,2)\) 
consider pairs of cliques \(\sigma ,\tau \)  with sizes
roughly \(\alpha \log _2 N\) . This range of \(\alpha \)  corresponds to clique sizes known
to be present in the graph existentially with overwhelming
probability, but not achievable algorithmically. As it turns out,
see [1]},[2]}, the model
exhibits the OGP for \(\alpha \in (1+1/\sqrt{2},2)\)  and overlap
parameters \(\nu _1(\alpha )<\nu _2(\alpha )\) , both of which are at the scale \(\log _2 N\) .
Specifically, every two cliques of size \(\alpha \log _2 N\)  have intersection size either at
least \(\tilde{\nu }_1(\alpha )\)  or at most \(\tilde{\nu }_2(\alpha )\) , for some values \(\tilde{\nu }_1(\alpha )>\tilde{\nu }_2(\alpha )\) ,
both at scale \(\log _2 n\) . This easily implies OGP with \(\nu _j(\alpha )=2\alpha -\tilde{\nu }_j(\alpha ), j=1,2\) .
The calculations in [1]} and [2]} were carried out
for a similar problem of finding a largest independent set (a set with no internal edges) in sparse
random graphs \(G(N,p_N)\)  with \(p_N\)  of the order \(O(1/N)\) , but the calculation details for the dense graph \(\mathbb {G}(N,1/2)\) 
are almost identical.
The end result
is that \(\tilde{\nu }_j(\alpha )=x_j(\alpha )\log _2 N\) , where \(x_1(\alpha )\)  and \(x_2(\alpha )\) 
are the two roots of the quadratic equation \(x^2/2-x+2\alpha -\alpha ^2=0\) , namely \(1\pm \sqrt{1-2(2\alpha -\alpha ^2)}\) ,
and roots exist if and only if \(\alpha >1+1/\sqrt{2}\) . For recent algorithmic results for the related
problem on random regular
graphs with small degree see [5]}.
