Problem Statement
Let $f(m)$ be maximal such that every graph with $m$ edges must contain a bipartite graph with\[\geq \frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}+f(m)\]edges. Is there an infinite sequence of $m_i$ such that $f(m_i)\to \infty$?
Categories:
Graph Theory
Progress
Conjectured by Erdős, Kohayakava, and Gyárfás. Edwards [Ed73] proved that $f(m)\geq 0$ always. Note that $f(\binom{n}{2})= 0$, taking $K_n$. Solved by Alon [Al96], who showed $f(n^2/2)\gg n^{1/2}$, and also showed that $f(m)\ll m^{1/4}$ for all $m$. The best possible constant in $f(m)\leq Cm^{1/4}$ is unknown.Source: erdosproblems.com/127 | Last verified: January 13, 2026