The Library
Extremal density for sparse minors and subdivisions
Tools
Tools
Tools
Haslegrave, John, Jaehoon, Kim and Hong, Liu (2021) Extremal density for sparse minors and subdivisions. In: EuroComb 2021, Barcelona (Online), 6-10 Sep 2021. Published in: Extended Abstracts EuroComb 2021, 14 pp. 25-31. ISBN 9783030838225. doi:10.1007/978-3-030-83823-2_5 ISSN 2509-7407.
|
PDF
WRAP-extremal-density-sparse-minors-subdivisions-Haslegrave-2021.pdf - Accepted Version - Requires a PDF viewer. Download (805Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-030-83823-2_5
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. 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, furthermore, surprisingly, the value is the same for t-vertex graphs embeddable on any fixed surface; average degree (2+o(1))t forces every t-vertex graph in any nontrivial minor-closed family as a minor. All these constants are best possible.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Bipartite graphs, Extremal problems (Mathematics) | ||||||
| Series Name: | Trends in Mathematics | ||||||
| Journal or Publication Title: | Extended Abstracts EuroComb 2021 | ||||||
| Publisher: | Springer | ||||||
| ISBN: | 9783030838225 | ||||||
| ISSN: | 2509-7407 | ||||||
| Official Date: | 24 August 2021 | ||||||
| Dates: |
|
||||||
| Volume: | 14 | ||||||
| Page Range: | pp. 25-31 | ||||||
| DOI: | 10.1007/978-3-030-83823-2_5 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Re-use Statement: | This is a post-peer-review, pre-copyedit version of an article published in Extended Abstracts EuroComb 2021. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-83823-2_5 | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 20 July 2021 | ||||||
| Date of first compliant Open Access: | 24 August 2022 | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | EuroComb 2021 | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Barcelona (Online) | ||||||
| Date(s) of Event: | 6-10 Sep 2021 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
