Inversion dans les tournois

RésuméNous considérons la transformation qui inverse tous les arcs d'une partie X de l'ensemble des sommets d'un tournoi T. L'indice de T, noté i(T), est le plus petit nombre de parties dont il faut inverser les arcs pour ramener T à un tournoi acyclique. Il apparaît que les tournois critiques et les tournois (−1)-critiques peuvent être définis au moyen d'inversions, les premiers étant d'indice un ou deux, les seconds d'indice au plus quatre. On peut voir i(T) comme le minimum de la distance de T aux tournois acycliques définis sur le même ensemble de sommets ; la distance entre deux tournois T et T′ peut être également interprétée comme la dimension booléenne d'un graphe, celui-ci étant la somme booléenne de T et T′. Sur n sommets, la distance maximale vaut n−1 tandis que i(n), le maximum des indices des tournois à n sommets, satisfait les inégalités pour n⩾4. Soit (resp. ), la classe des tournois finis (resp. au plus dénombrables) T tels que i(T)⩽m. La classe est déterminée par un nombre fini d'obstructions ; nous donnons une description morphologique des éléments de et décrivons ses obstructions. Nous décrivons aussi un tournoi universel de la classe .

We consider the transformation reversing all arcs of a subset X of the vertex set of a tournament T. The 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 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 , for n⩾4. Let (resp. ) be the class of finite (resp. at most countable) tournaments T such that i(T)⩽m. The class is determined by finitely many obstructions. We give a morphological description of the members of and a description of the critical obstructions. We give an explicit description of a universal tournament of the class .