论文标题
锦标赛的分解性和共同座位
Decomposability and co-modular indices of tournaments
论文作者
论文摘要
给定锦标赛$ t $，$ t $的一个模块是$ v（t）$的子集$ x $，因此，对于$ x，y \ in x $ in x $和$ v \ in v（t）\ setminus x $，$（x，x，v）\ in（t）$ in A（y，v）$ in（y，v）\ in（y，v）\ in（y，v）\ in（t）$。 $ t $的琐碎模块是$ \ emptyset $，$ \ {u \} $ $（u \ in v（t））$和$ v（t）$。如果其所有模块都很微不足道，那么比赛$ t $都是不可分解的。否则它是可分解的。 $δ（t）$表示的$ t $的可分解性指数是$ t $的最小数量的$ t $，必须逆转以使$ t $不可兼容。第一作者指出，对于$ n \ geq 5 $，我们有$δ（n）= \ left \ lceil \ frac {n+1} {4} {4} \ right \ rceil $，其中$δ（n）$是$ t $ t $ n $ n $ vertices的$δ（n）$。 In this paper we prove this conjecture by introducing the co-modular index of a tournament $T$, denoted by $Δ(T)$, as the largest number of disjoint co-modules of $T$, where a co-module of $T$ is a subset $M$ of $V(T)$ such that $M$ or $V(T) \setminus M$ is a nontrivial module of $T$.我们证明，对于$ n \ geq 3 $，我们有$δ（n）= \ left \ lceil \ frac {n+1} {2} {2} \ right \ rceil $，其中$δ（n）$是$ t $ t $ n $ n $ vertices的$δ（n）$。我们的主要结果是以下两个指数之间的紧密关系：对于每个锦标赛$ t $，至少$ 5 $顶点，我们都有$δ（t）= \ left \ lceil \ frac \ frac {δ（t）} {2} {2} {2} \ right \ rceil $。结果，我们获得了$δ（n）= \ left \ lceil \ frac {δ（n）} {2} {2} {2} {2} \ right \ rceil = \ left \ left \ lceil \ frac {n+1} {n+1} {4} {4} {4} {4} {4} {4} \ right \ right \ rceil $ for $ n \ geq for $ n \ geq 5 $，我们回答了一些相关问题。
Given a tournament $T$, a module of $T$ is a subset $X$ of $V(T)$ such that for $x, y\in X$ and $v\in V(T)\setminus X$, $(x,v)\in A(T)$ if and only if $(y,v)\in A(T)$. The trivial modules of $T$ are $\emptyset$, $\{u\}$ $(u\in V(T))$ and $V(T)$. The tournament $T$ is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of $T$, denoted by $δ(T)$, is the smallest number of arcs of $T$ that must be reversed to make $T$ indecomposable. The first author conjectured that for $n \geq 5$, we have $δ(n) = \left\lceil \frac{n+1}{4} \right\rceil$, where $δ(n)$ is the maximum of $δ(T)$ over the tournaments $T$ with $n$ vertices. In this paper we prove this conjecture by introducing the co-modular index of a tournament $T$, denoted by $Δ(T)$, as the largest number of disjoint co-modules of $T$, where a co-module of $T$ is a subset $M$ of $V(T)$ such that $M$ or $V(T) \setminus M$ is a nontrivial module of $T$. We prove that for $n \geq 3$, we have $Δ(n) = \left\lceil \frac{n+1}{2} \right\rceil$, where $Δ(n)$ is the maximum of $Δ(T)$ over the tournaments $T$ with $n$ vertices. Our main result is the following close relationship between the above two indices: for every tournament $T$ with at least $5$ vertices, we have $δ(T) = \left\lceil \frac{Δ(T)}{2} \right\rceil$. As a consequence, we obtain $δ(n) = \left\lceil \frac{Δ(n)}{2} \right\rceil = \left\lceil \frac{n+1}{4} \right\rceil$ for $n \geq 5$, and we answer some further related questions.
