Erdős–Hajnal: smallest $g(n)$ so every $g(n)$-subset has a $\log n$ clique and $\log n$ independent set (Erdős #805)

For a function $g(n)$ with $n>g(n)\geq (\log n)^2$, call an $n$-vertex graph $g$-good if every induced subgraph on $g(n)$ vertices contains both a clique of size $\geq \log n$ and an independent set of size $\geq \log n$. For which functions $g(n)$ does a $g$-good graph on $n$ vertices exist? In particular, does one exist for $g(n)=(\log n)^3$? (Erdős and Hajnal believed no such graph exists at $g(n)=(\log n)^3$.) Determine the threshold order of $g(n)$ that separates existence from non-existence.

Acceptance. FULLY RESOLVES: determine the threshold — settle whether an $n$-vertex $g$-good graph exists for $g(n)=(\log n)^3$ (the specific Erdős–Hajnal question), and more generally identify the order of magnitude of the smallest $g(n)$ admitting a good graph, with a complete proof of both a construction (an explicit or randomized graph family that is $g$-good for the claimed $g$, together with a proof that every $g(n)$-vertex subset contains the required clique and independent set) and a matching non-existence bound. ADVANCES: improve either frontier stated in the background — a construction of $g$-good graphs for some $g(n)$ smaller than $2^{2^{(\log\log n)^{1/2+o(1)}}}$ (delivered as an explicit graph family with a proof that every $g(n)$-vertex subset has a $\log n$ clique and a $\log n$ independent set), or a non-existence proof ruling out good graphs for some $g(n)$ larger than $\frac{c}{\log\log n}(\log n)^3$ — with a full proof. Deliver the proof, and for constructions the explicit graph family.