The extremal number $mathrm{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 in [1,2]$ is realisable if there exists a graph $F$ with $mathrm{ex}(n , F) = Theta(n^r)$. Several decades ago, ErdH{o}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, frac{7}{5}, 2$, and the numbers of the form $1+frac{1}{m}$, $2-frac{1}{m}$, $2-frac{2}{m}$ for integers $m geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$. In this paper, we make progress on the conjecture of ErdH{o}s and Simonovits. First, we show that $2 - frac{a}{b}$ is realisable for any integers $a,b geq 1$ with $b>a$ and $b equiv pm 1 ~({rm mod}:a)$. This includes all previously known ones, and gives infinitely many limit points $2-frac{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.
تحميل البحث