Problem 625 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph. Let $\chi(G)$ denote the chromatic number.

If $G$ is a random graph with $n$ vertices and each edge included independently with probability $1/2$ then is it true that almost surely\[\chi(G) - \zeta(G) \to \infty\]as $n\to \infty$?

Picture
-------
Graph picture:

o---o
|\  |
| \ |
o---o    K4 is the complete graph on 4 vertices (all connections)

Question: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: infinite graph theory / Ramsey-type decompositions.

Benchmarks / known results (from comments)
----------------------------------------
- At a conference on random graphs in Poznan, Poland (most likely in 1989)
  Erd\H{o}s offered \$100 for a proof that this is true, and \$1000 for a
  proof that this is false (although later told Gimbel that \$1000 was perhaps
  too much).
- It is known that almost surely\[\frac{n}{2\log_2n}\leq \zeta(G)\leq
  \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.\](The final upper bound is due to
  Bollob\'{a}s.
- The first inequality follows from the fact that almost surely $G$ has clique
  number and independence number $< 2\log_2n$.) Heckel and, independently,
  Steiner have shown that it is not the case that $\chi(G)-\zeta(G)$ is
  bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$
  with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite
  sequence of $n$.
- Heckel conjectures that, with high probability,\[\chi(G)-\zeta(G) \asymp
  \frac{n}{(\log n)^3}.\]Heckel further proved that, for any $\epsilon>0$, we
  have\[\chi(G) -\zeta(G) \geq n^{1-\epsilon}\]for roughly $95\%$ of all $n$.