On the Turán number for the hexagon

A long-standing conjecture of Erdős and Simonovits is that ex(n,C2k)ex(n,C2k), the maximum number of edges in an n  -vertex graph without a 2k2k-gon is asymptotically 12n1+1/k as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove thatex(n,C6)>3(5-2)(5-1)4/3n4/3+O(n)>0.5338n4/3.We also show that ex(n,C6)⩽λn4/3+O(n)<0.6272n4/3ex(n,C6)⩽λn4/3+O(n)<0.6272n4/3 if n   is sufficiently large, where λλ is the real root of 16λ3-4λ2+λ-3=016λ3-4λ2+λ-3=0. This yields the best-known upper bound for the number of edges in a hexagon-free graph. The same methods are applied to find a tight bound for the maximum size of a hexagon-free 2n×n2n×n bipartite graph.