On the rational Turán exponents conjecture

Abstract The extremal number ex ( n , F ) of a graph F is the maximum number of edges in an n-vertex graph not containing F as a subgraph. A real number r ∈ [ 1 , 2 ] is realisable if there exists a graph F with ex ( n , F ) = Θ ( n r ) . Several decades ago, Erdős and Simonovits conjectured that every rational number in [ 1 , 2 ] is realisable. Despite decades of effort, the only known realisable numbers are 0 , 1 , 7 5 , 2 , and the numbers of the form 1 + 1 m , 2 − 1 m , 2 − 2 m for integers m ≥ 1 . In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than the two numbers 1 and 2. In this paper, we make progress on the conjecture of Erdős and Simonovits. First, we show that 2 − a b is realisable for any integers a , b ≥ 1 with b > a and b ≡ ± 1 ( mod a ) . This includes all previously known ones, and gives infinitely many limit points 2 − 1 m in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.