Extremal density for sparse minors and subdivisions
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, <br> (1+o(1))t2 average degree...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Oxford University Press
2021
|
| _version_ | 1797108410821378048 |
|---|---|
| author | Haslegrave, J Kim, J Liu, H |
| author_facet | Haslegrave, J Kim, J Liu, H |
| author_sort | Haslegrave, J |
| collection | OXFORD |
| description | 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,
<br>
(1+o(1))t2 average degree is sufficient to force the t×t grid as a topological minor;
<br>
(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;
<br>
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. |
| first_indexed | 2024-03-07T07:28:49Z |
| format | Journal article |
| id | oxford-uuid:6921668e-8d2e-4c03-9d74-c1f31c0107a3 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:28:49Z |
| publishDate | 2021 |
| publisher | Oxford University Press |
| record_format | dspace |
| spelling | oxford-uuid:6921668e-8d2e-4c03-9d74-c1f31c0107a32022-12-14T09:04:44ZExtremal density for sparse minors and subdivisionsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6921668e-8d2e-4c03-9d74-c1f31c0107a3EnglishSymplectic ElementsOxford University Press2021Haslegrave, JKim, JLiu, HWe 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, <br> (1+o(1))t2 average degree is sufficient to force the t×t grid as a topological minor; <br> (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; <br> 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. |
| spellingShingle | Haslegrave, J Kim, J Liu, H Extremal density for sparse minors and subdivisions |
| title | Extremal density for sparse minors and subdivisions |
| title_full | Extremal density for sparse minors and subdivisions |
| title_fullStr | Extremal density for sparse minors and subdivisions |
| title_full_unstemmed | Extremal density for sparse minors and subdivisions |
| title_short | Extremal density for sparse minors and subdivisions |
| title_sort | extremal density for sparse minors and subdivisions |
| work_keys_str_mv | AT haslegravej extremaldensityforsparseminorsandsubdivisions AT kimj extremaldensityforsparseminorsandsubdivisions AT liuh extremaldensityforsparseminorsandsubdivisions |