Inversion dans les tournois

Belkhechine, Houmem; Bouaziz, Moncef; Boudabbous, Imed; Pouzet, Maurice

Comptes Rendus. Mathématique, Tome 348 (2010) no. 13-14, pp. 703-707.

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

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 n−12−log2n⩽i(n)⩽n−3, for n⩾4. Let Im<ω (resp. Im⩽ω) be the class of finite (resp. at most countable) tournaments T such that i(T)⩽m. The class Im<ω is determined by finitely many obstructions. We give a morphological description of the members of I1<ω and a description of the critical obstructions. We give an explicit description of a universal tournament of the class Im⩽ω.

[1] H. Belkhechine, Indécomposabilité des graphes et des tournois, thèse de doctorat, Université Claude-Bernard et Université de Sfax, 15 juillet 2009

[2] Belkhechine, H.; Boudabbous, I.; Dammak, J. Morphologie des tournois (−1)-critiques, C. R. Acad. Sci. Paris Ser. I, Volume 345 (2007), pp. 663-666

[3] Bondy, J.A.; Murty, U.S.R. Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, 2008 (651 pp)

[4] Boudabbous, Y.; Pouzet, M. The morphology of infinite tournaments; applications to the growth of their profile, Europ. J. Combin., Volume 31 (2010), pp. 461-481

[5] Culus, J.-F.; Jouve, B. Convex circuit-free coloration of an oriented graph, Europ. J. Combin., Volume 30 (2009), pp. 43-52

[6] Fraïssé, R. Theory of Relations, Studies in Logic and the Foundations of Mathematics, vol. 145, Elsevier, 2000

[7] Gallai, T. Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[8] Latka, B.J. Structure theorem for tournaments omitting N5, J. Graph Theory, Volume 42 (2003), pp. 165-192

[9] Pouzet, M. Un bel ordre d'abritement et ses rapports avec les bornes d'une multirelation, C. R. Acad. Sci. Paris Sér. A-B, Volume 274 (1972), p. A1677-A1680

[10] Schmerl, J.H.; Trotter, W.T. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205

[11] Slater, P. Inconsistencies in a schedule of paired comparaison, Biometrika, Volume 48 (1961), pp. 303-312