Extremal density for sparse minors and subdivisions

Cited 8 time in webofscience Cited 0 time in scopus
  • Hit : 115
  • Download : 0
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))t(2) average degree is sufficient to force the t x t grid as a topological minor;,(3/2+o(1))t average degree forces 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 t-vertex graph in nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth.,
Publisher
OXFORD UNIV PRESS
Issue Date
2022-10
Language
English
Article Type
Article
Citation

INTERNATIONAL MATHEMATICS RESEARCH NOTICES, v.2022, no.20, pp.15505 - 15548

ISSN
1073-7928
DOI
10.1093/imrn/rnab154
URI
http://hdl.handle.net/10203/301644
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 8 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0