Conlon, D;
Lee, J;
(2019)
On the Extremal Number of Subdivisions.
International Mathematics Research Notices
, Article rnz088. 10.1093/imrn/rnz088.
Preview |
Text
exH.pdf - Published Version Download (226kB) | Preview |
Abstract
One of the cornerstones of extremal graph theory is a result of Füredi, 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 Cn2−1/r edges contains a copy of H. This result is tight up to the constant when H contains a copy of Kr,s with s sufficiently large in terms of r. We conjecture that this is essentially the only situation in which Füredi’s result can be tight and prove this conjecture for r=2. More precisely, we show that if H is a C4-free bipartite graph with maximum degree 2 on one side, then there are positive constants C and δ such that every graph with n vertices and Cn3/2−δ edges contains a copy of H. This answers a question of Erd̋s from 1988. The proof relies on a novel variant of the dependent random choice technique which may be of independent interest.
| Type: | Article |
|---|---|
| Title: | On the Extremal Number of Subdivisions |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1093/imrn/rnz088 |
| Publisher version: | http://dx.doi.org/10.1093/imrn/rnz088 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10120251 |
Archive Staff Only
 |
View Item |
