Inversions in tournaments

Abstract: 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

f r a c n - 1 2 - l o g_{2} n l e q i (n) l e q n - 3

, for

n g e q 4

. Let

m a t h c a l I_{m}^{< o m e g a}

(resp.

m a t h c a l I_{m}^{l e q o m e g a}

) be the class of finite (resp. at most countable) tournaments

T

such that

i (T) l e q m

. The class

m a t h c a l I_{m}^{< o m e g a}

is determined by finitely many obstructions. We give a morphological description of the members of

m a t h c a l I_{1}^{< o m e g a}

and a description of the critical obstructions. We give an explicit description of an universal tournament of the class

m a t h c a l I_{m}^{l e q o m e g a}

.

Recommendations

Cites Work

Cited In (5)

This page was built for publication: Inversions in tournaments