= Solution
Fix $k\geq1$ and sample $G$ from the <Erdős-Rényi model> with $p=\tfrac12n^{-2/3}$. Let $X$ count copies of the <complete bipartite graph> $K_{3,3}$. By the <expected subgraph count in the Erdős-Rényi model>,
$$
\mathbb EX
=\frac12\binom n3\binom{n-3}3p^9
\longrightarrow \frac{1}{72\,2^9}<1.
$$
Put $m=\lceil n/k\rceil$ and let $Z$ count <independent sets>[independent set] of size $m$. If the <chromatic number> satisfies $\chi(G)\leq k$, some colour class has at least $m$ vertices, so $Z\geq1$. Moreover,
$$
\begin{aligned}
\mathbb EZ
&=\binom nm(1-p)^{\binom m2}\\
&\leq\left(\frac{en}{m}\right)^m
\exp\left(-p\binom m2\right)
\longrightarrow0,
\end{aligned}
$$
because the positive part of the exponent is $O(n)$ whereas $p\binom m2$ has order $n^{4/3}$. The <first moment method> therefore gives $\mathbb P(\chi(G)\leq k)\leq\mathbb EZ=o(1)$.
Using <Markov inequality> for $X$ and the <union bound>,
$$
\begin{aligned}
\mathbb P(X=0\text{ and }\chi(G)>k)
&\geq1-\mathbb P(X\geq1)-\mathbb P(\chi(G)\leq k)\\
&\geq1-\mathbb EX-o(1)>0
\end{aligned}
$$
for all sufficiently large $n$. Hence at least one such $G$ contains no $K_{3,3}$ and has $\chi(G)>k$.
Back to article page
