On the Turán number for the hexagon

A long-standing conjecture of Erdo{combining double acute accent}s and Simonovits is that ex ( n, C_{2 k} ), the maximum number of edges in an n-vertex graph without a 2 k-gon is asymptotically frac(1, 2) n^{1 + 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 that{A formula is presented}We also show that ex ( n, C₆ ) {less-than or slanted equal to} λ n^{4 / 3} + O ( n ) < 0.6272 n^{4 / 3} if n is sufficiently large, where λ is the real root of 16 λ³ - 4 λ² + λ - 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 2 n × n bipartite graph.