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

Problem statement
---------------
Let $f(n)\to \infty$ (possibly very slowly). Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

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)
----------------------------------------
- Conjectured by Erd\H{o}s, Hajnal, and Szemer\'{e}di.
- R\"{o}dl has proved this for hypergraphs, and also proved there is such a
  graph (with chromatic number $\aleph_0$) if $f(n)=\epsilon n$ for any fixed
  constant $\epsilon>0$.
- It is open even for $f(n)=\sqrt{n}$.
- Erd\H{o}s offered \$500 for a proof but only \$250 for a counterexample.