Inversion dans les tournois

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 n − 1 2 − log 2 n ⩽ i ( n ) ⩽ n − 3 pour n ⩾ 4 . Soit I m < ω (resp. I m ⩽ ω ), la classe des tournois finis (resp. au plus dénombrables) T tels que i ( T ) ⩽ m . La classe I m < ω est déterminée par un nombre fini d'obstructions ; nous donnons une description morphologique des éléments de I 1 < ω et décrivons ses obstructions. Nous décrivons aussi un tournoi universel de la classe I m ⩽ ω .