密度有向图中的生成细分

Spanning subdivisions in dense digraphs

摘要 Abstract

我们证明了对于一个具有至少 $\left(\frac{1}{2} + \varepsilon \right)n$ 最小半度数的 $n$ 阶有向图 $D$,当 $n \geq C m$ 时,它包含所有不含孤立点的 $m$ 弧有向图的细分结构。这里的 $C$ 是仅依赖于 $\varepsilon$ 的常数。这是可能的最佳结果,并以更强的形式解决了 Pavez-Sign\'{e} 提出的一个猜想。

We prove that an $n$-vertex digraph $D$ with minimum semi-degree at least $\left(\frac{1}{2} + \varepsilon \right)n$ and $n \geq C m$ contains a subdivision of all $m$-arc digraphs without isolated vertices. Here, $C$ is a constant only depending on $\varepsilon.$ This is the best possible and settles a conjecture raised by Pavez-Sign\'{e} in a stronger form.

密度有向图中的生成细分 - arXiv