Spanning trees in dense directed graphs
Spanning trees in dense directed graphs
复制标题
密集有向图中的生成树
DOI：
10.1016/j.jctb.2022.04.007
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
R. Montgomery
中科院分区：
文献类型：
--
作者：
Amarja Kathapurkar;R. Montgomery
2001年，Komlós，Sárközy和Szemerédi证明了，对于每个α> 0，存在一些c> 0和n 0使得，如果n≥ n 0，则每个最小度至少为（1/2+ α）n的n-顶点图包含每个最大度至多为cn/log n的n-顶点树的副本。我们证明了有向图的相应结果。也就是说，对于每个α> 0，存在某个c> 0和n 0，使得如果n≥ n 0，则每个最小半度至少为（1/2+ α）n的n-顶点有向图包含每个最大度至多为cn/log n的n-顶点定向树的副本。与Komlós，Sárközy和Szemerédi定理一样，这是紧到c的值。我们的结果改进了Mycroft和Naia的最近结果，该结果要求定向树的最大度不超过Δ，对于任意常数Δ∈ N和足够大的n.与这些结果相反，我们的方法不使用Szemerédi的正则性引理。
In 2001, Komlós, Sárközy and Szemerédi proved that, for each α> 0, there is some c> 0 and n 0 such that, if n≥ n 0, then every n-vertex graph with minimum degree at least (1/2+ α) n contains a copy of every n-vertex tree with maximum degree at most c n/log n. We prove the corresponding result for directed graphs. That is, for each α> 0, there is some c> 0 and n 0 such that, if n≥ n 0, then every n-vertex directed graph with minimum semi-degree at least (1/2+ α) n contains a copy of every n-vertex oriented tree whose underlying maximum degree is at most c n/log n. As with Komlós, Sárközy and Szemerédi's theorem, this is tight up to the value of c. Our result improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most Δ, for any constant Δ∈ N and sufficiently large n. In contrast to these results, our methods do not use Szemerédi's regularity lemma.
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus