论文标题
比赛中有许多捷径的路径
Paths with many shortcuts in tournaments
论文作者
论文摘要
定向路径的快捷方式$ v_1 v_2 \ cdots v_n $是边缘$ v_iv_j $，带有$ j> i+1 $。如果$ j = i+2 $，快捷方式称为跳跃。如果存在所有啤酒花，则该路径称为“跃点”，因此路径及其啤酒花形成路径的正方形。我们证明，每场比赛的$ n \ ge 4 $顶点都有一条至少$（4n-10）/7 $ hops的哈密顿路径，并且具有至少$ n^{0.295} $的啤酒花完整路径。 跨越比赛的二进制树是一棵跨越的快捷树，如果对树的每个顶点，其所有左后代都是邻居的，其所有右后代都是超过邻居的。众所周知，每次比赛都包含一棵跨越的快捷树。快捷树的快捷方式的数量是其独特的诱发哈密顿路径的捷径数量。令$ t（n）$表示最大的整数，以便每次拥有$ n $顶点的比赛都有一棵跨越至少$ t（n）$快捷方式的快捷树。我们几乎确定$ t（n）$的渐近生长，因为证明$θ（n \ log^2n）\ ge t（n） - \ frac {1} {2} {2} \ binom {n} {2} {2} {2} \geθ（n \ log n \ log n）$。
A shortcut of a directed path $v_1 v_2 \cdots v_n$ is an edge $v_iv_j$ with $j > i+1$. If $j = i+2$ the shortcut is called a hop. If all hops are present, the path is called hop complete, so the path and its hops form a square of a path. We prove that every tournament with $n \ge 4$ vertices has a Hamiltonian path with at least $(4n-10)/7$ hops, and has a hop complete path of order at least $n^{0.295}$. A spanning binary tree of a tournament is a spanning shortcut tree if for every vertex of the tree, all its left descendants are in-neighbors and all its right descendants are out-neighbors. It is well-known that every tournament contains a spanning shortcut tree. The number of shortcuts of a shortcut tree is the number of shortcuts of its unique induced Hamiltonian path. Let $t(n)$ denote the largest integer such that every tournament with $n$ vertices has a spanning shortcut tree with at least $t(n)$ shortcuts. We almost determine the asymptotic growth of $t(n)$ as it is proved that $Θ(n\log^2n) \ge t(n)-\frac{1}{2}\binom{n}{2} \ge Θ(n \log n)$.
