On the rational Turán exponents conjecture

Abstract: The extremal number

m a t h r m e x (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 i n [1, 2]

is realisable if there exists a graph

F

with

m a t h r m e x (n, F) = T h e t a (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, f r a c 75, 2

, and the numbers of the form

1 + f r a c 1 m

,

2 - f r a c 1 m

,

2 - f r a c 2 m

for integers

m g e q 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 - f r a c a b

is realisable for any integers

a, b g e q 1

with

b > a

and

b e q u i v p m 1 (m m o d : a)

. This includes all previously known ones, and gives infinitely many limit points

2 - f r a c 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.

Recommendations

Cites work

Cited in

(11)

This page was built for publication: On the rational Turán exponents conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1998761)