Mathematics – Combinatorics
Scientific paper
2010-07-13
Mathematics
Combinatorics
6 pages
Scientific paper
10.1016/j.crma.2010.06.022
We consider the transformation reversing all arcs of a subset $X$ of the vertex set of a tournament $T$. The \emph{index} of $T$, denoted by $i(T)$, is the smallest number of subsets that must be reversed to make $T$ acyclic. It turns out that critical tournaments and $(-1)$-critical tournaments can be defined in terms of inversions (at most two for the former, at most four for the latter). We interpret $i(T)$ as the minimum distance of $T$ to the transitive tournaments on the same vertex set, and we interpret the distance between two tournaments $T$ and $T'$ as the \emph{Boolean dimension} of a graph, namely the Boolean sum of $T$ and $T'$. On $n$ vertices, the maximum distance is at most $n-1$, whereas $i(n)$, the maximum of $i(T)$ over the tournaments on $n$ vertices, satisfies $\frac {n-1}{2} - \log_{2}n \leq i(n) \leq n-3$, for $n \geq 4$. Let $ \mathcal{I}_{m}^{< \omega}$ (resp. $\mathcal{I}_{m}^{\leq \omega}$) be the class of finite (resp. at most countable) tournaments $T$ such that $i(T) \leq m$. The class $\mathcal {I}_{m}^{< \omega}$ is determined by finitely many obstructions. We give a morphological description of the members of $\mathcal {I}_{1}^{< \omega}$ and a description of the critical obstructions. We give an explicit description of an universal tournament of the class $\mathcal{I}_{m}^{\leq \omega}$.
Belkhechine Houmem
Bouaziz Moncef
Boudabbous Imed
Pouzet Maurice
No associations
LandOfFree
Inversion dans les tournois does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Inversion dans les tournois, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inversion dans les tournois will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-350837