On the extremal number of subdivisions

DOI10.1093/IMRN/RNZ088zbMATH Open1486.05155arXiv1807.05008OpenAlexW2963671725MaRDI QIDQ5068166FDOQ5068166

Publication date: 5 April 2022

Published in: IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1807.05008

Recommendations

zbMATH Keywords

bipartite graph extremal numbers dependent random choice technique

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

Cited In (23)

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)