Pith. sign in

On the rational Tur\'an exponents conjecture

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

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, Erd\H{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 Erd\H{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.

fields

math.CO 1

years

2019 1

verdicts

CONDITIONAL 1

representative citing papers

Many Turan exponents via subdivisions

math.CO · 2019-08-06 · conditional · novelty 8.0

Every rational number 1 + p/q with q > p^2 is shown to be the exact growth exponent of some bipartite Turan problem.

citing papers explorer

Showing 1 of 1 citing paper.

  • Many Turan exponents via subdivisions math.CO · 2019-08-06 · conditional · none · ref 22 · internal anchor

    Every rational number 1 + p/q with q > p^2 is shown to be the exact growth exponent of some bipartite Turan problem.