The Library

Extremal density for sparse minors and subdivisions

Tools

Haslegrave, John, Jaehoon, Kim and Hong, Liu (2022) Extremal density for sparse minors and subdivisions. International Mathematics Research Notices, 2022 (20). pp. 15505-15548. doi:10.1093/imrn/rnab154 ISSN 1073-7928.

Preview

PDF
WRAP-Extremal-density-sparse-minors-subdivisions-2021.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.
Download (2001Kb) | Preview

PDF
WRAP-Extremal-density-sparse-minors-subdivisions-2021.pdf - Accepted Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.
Download (1046Kb)

Official URL: http://dx.doi.org/10.1093/imrn/rnab154

Request Changes to record.

Abstract

We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood on embedding sparse minors. Among others,
∙ (1+o(1))t2 average degree is sufficient to force the t×t grid as a topological minor;
∙ (3/2+o(1))t average degree forces every t-vertex planar graph as a minor, and the constant 3/2 is optimal, furthermore, surprisingly, the value is the same for t-vertex graphs embeddable on any fixed surface;
∙ a universal bound of (2+o(1))t on average degree forcing every t-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics

Divisions:

Faculty of Science, Engineering and Medicine > Science > Mathematics

Library of Congress Subject Headings (LCSH):

Bipartite graphs , Extremal problems (Mathematics) , Graph theory

Journal or Publication Title:

International Mathematics Research Notices

Publisher:

Oxford University Press

ISSN:

1073-7928

Official Date:

October 2022

Dates:

Date	Event
October 2022	Published
30 June 2021	Available
16 May 2021	Accepted

Volume:

2022

Number:

Page Range:

pp. 15505-15548

DOI:

10.1093/imrn/rnab154

Status:

Peer Reviewed

Publication Status:

Published

Re-use Statement:

This is a pre-copyedited, author-produced version of an article accepted for publication in International Mathematics Research Notices following peer review. The version of record [insert complete citation information here] is available online at: xxxxxxx [insert URL and DOI of the article on the OUP website].

Access rights to Published version:

Open Access (Creative Commons)

Date of first compliant deposit:

19 May 2021

Date of first compliant Open Access:

31 August 2021

RIOXX Funder/Project Grant:

Project/Grant ID	RIOXX Funder Name	Funder ID
MR/S016325/1	UK Research and Innovation	http://dx.doi.org/10.13039/100014013
UNSPECIFIED	POSCO TJ Park Foundation	https://www.postf.org/en/main.do
UNSPECIFIED	KAIST Advanced Institute for Science-X	http://natsci.kaist.ac.kr/eng/0406