论文标题
锦标赛中有许多叶子的树木
Trees with many leaves in tournaments
论文作者
论文摘要
萨姆纳（Sumner）的通用锦标赛猜想指出，每$（2n-2）$ - 顶点锦标赛应包含每$ n $ vertex的副本。如果我们知道面向树或最高学位的叶子数量，我们可以保证在比赛中具有更少顶点的树的副本吗？由于Häggkvist和Thomason（用于叶子的数量）和Kühn，Mycroft和Osthus（最高程度）发起的工作，众所周知，在某些情况下，可以对Sumner的猜想进行改进，实际上有时是$（N+O（N+O（N））$ - Vertex锦标赛可能足够。 在本文中，我们就这些问题给出了新的结果。具体来说，我们显示 i）对于每一个$α> 0 $，都存在$ n_0 \ in \ mathbb {n} $中，以便每当$ n \ geqslant n_0 $，每个$（（（1+α）n+k）$ - vertex $ - dertex termentai ii）对于每$α> 0 $，都存在$ c> 0 $和$ n_0 \ in \ mathbb {n} $，这样，每当$ n \ geqslant n_0 $，每个$（1+α）n $ vertex tournament都包含每个$ n $ n $ n $ n $ n $ vertex ofdex tree的副本，并带有最大$ $ $ $ $ ulet $ uequd。 我们的第一个结果给出了Havet和Thomassé猜想的渐近形式，而第二个结果则改善了Mycroft和Naia的结果，Mycroft和Naia适用于具有最大程度的树木。
Sumner's universal tournament conjecture states that every $(2n-2)$-vertex tournament should contain a copy of every $n$-vertex oriented tree. If we know the number of leaves of an oriented tree, or its maximum degree, can we guarantee a copy of the tree with fewer vertices in the tournament? Due to work initiated by Häggkvist and Thomason (for number of leaves) and Kühn, Mycroft and Osthus (for maximum degree), it is known that improvements can be made over Sumner's conjecture in some cases, and indeed sometimes an $(n+o(n))$-vertex tournament may be sufficient. In this paper, we give new results on these problems. Specifically, we show i) for every $α>0$, there exists $n_0\in\mathbb{N}$ such that, whenever $n\geqslant n_0$, every $((1+α)n+k)$-vertex tournament contains a copy of every $n$-vertex oriented tree with $k$ leaves, and ii) for every $α>0$, there exists $c>0$ and $n_0\in\mathbb{N}$ such that, whenever $n\geqslant n_0$, every $(1+α)n$-vertex tournament contains a copy of every $n$-vertex oriented tree with maximum degree $Δ(T)\leqslant cn$. Our first result gives an asymptotic form of a conjecture by Havet and Thomassé, while the second improves a result of Mycroft and Naia which applies to trees with polylogarithmic maximum degree.
