On the extremal number of subdivisions

Abstract: One of the cornerstones of extremal graph theory is a result of F"uredi, later reproved and given due prominence by Alon, Krivelevich and Sudakov, saying that if

H

is a bipartite graph with maximum degree

r

on one side, then there is a constant

C

such that every graph with

n

vertices and

C n^{2 - 1 / r}

edges contains a copy of

H

. This result is tight up to the constant when

H

contains a copy of

K_{r, s}

with

s

sufficiently large in terms of

r

. We conjecture that this is essentially the only situation in which F"uredi's result can be tight and prove this conjecture for

r = 2

. More precisely, we show that if

H

is a

C_{4}

-free bipartite graph with maximum degree

2

on one side, then there are positive constants

C

and

d e l t a

such that every graph with

n

vertices and

C n^{3 / 2 - d e l t a}

edges contains a copy of

H

. This answers a question of ErdH{o}s from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: On the extremal number of subdivisions

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