Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3
Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3
-
Oliver Janzer, ETH Zurich
Online Talk
In 1981, Erdős and Simonovits conjectured that for any bipartite graph H we have ex(n,H)=O(n^{3/2}) if and only if H is 2-degenerate. Later, Erdős offered 250 dollars for a proof and 500 dollars for a counterexample. We disprove the conjecture by finding, for any epsilon>0, a 3-regular bipartite graph H with ex(n,H)=O(n^{4/3+epsilon}).