论文标题
稀疏未成年人和细分的极端密度
Extremal density for sparse minors and subdivisions
论文作者
论文摘要
我们证明了一个渐近密度的渐近密度，可确保具有轻度可分离性条件的有界两分图的细分。作为推论，我们回答了里德和木材的几个问题，上面嵌入了稀疏的未成年人。等等 $ \ bullet $ $（1+O（1））T^2 $平均度足以强迫$ t \ times t $网格作为拓扑辅助； $ \ bullet $ $（3/2+o（1））t $平均度力量每$ t $ vertex Planar gruend作为未成年人，而常数$ 3/2 $是最佳的，此外，令人惊讶的是，对于$ t $ vertex图的值是相同的，对于$ t $ vertex graphs，可在任何固定表面上嵌入可嵌入在任何固定表面上； $ \ bullet $平均$（2+o（1））T $的通用限制在任何非平凡的次要次要家庭中都会强迫每一个$ t $ vertex图作为未成年人，并且最好通过考虑具有给定的树宽的图形来实现常数2。
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, $\bullet$ $(1+o(1))t^2$ average degree is sufficient to force the $t\times t$ grid as a topological minor; $\bullet$ $(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; $\bullet$ 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.
