---

Claim. Theorem 1 of N. Alon, M. Bucić and B. Sudakov, Large cliques and independent sets all over the place, Proc. Amer. Math. Soc. 149 (2021), no. 8, 3145--3157, first posted as arXiv:2004.04718 on 2020-04-09, gives for every large $n$ an $n$-vertex graph $G$ with $m_G(\log n)\le2^{2^{(\log\log n)^{1/2+o(1)}}}$. The corpus states it on its result page. Here $m_G(k)$ is the least $m$ such that every set of at least $m$ vertices contains both a clique and an independent set of size at least $k$, and logarithms are to base $2$. Theorem 2 gives the explicit bound $\log\log m_G(k)\le6\sqrt{\log\log n\,\log\log k}$ for $n\ge4$ and $k\ge\log n$. Since $\log_2n>\ln n$, the same graph serves with natural logarithms. So the answer to Problem 805 is yes for every $g(n)<n$ with $g(n)\ge m_G(\log n)$.

Covers. The instances with $2^{2^{(\log\log n)^{1/2+\varepsilon}}}\le g(n)<n$ for a fixed $\varepsilon>0$ and all large $n$, answered yes. Not covered: every smaller $g$. The bound exceeds every fixed power of $\log n$, so $g(n)=(\log n)^3$ stays open, as the paper says.

Depends on. Nothing in this wiki; the construction is the paper's own.

Acceptance. refereed: Proc. Amer. Math. Soc. 149 (2021), no. 8, 3145--3157, published online 14 May 2021. The site's curator, T. F. Bloom, credits the construction in the problem's commentary. The site labels the problem OPEN, so that commentary is not acceptance, and no reviewed is listed. Source card: Alon, Bucić and Sudakov.