Comptes Rendus
Logique/Combinatoire
Inversion dans les tournois
Comptes Rendus. Mathématique, Volume 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 n1 tandis que i(n), le maximum des indices des tournois à n sommets, satisfait les inégalités n12log2ni(n)n3 pour n4. 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 n1, whereas i(n), the maximum of i(T) over the tournaments on n vertices, satisfies n12log2ni(n)n3, for n4. 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ω.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2010.06.022

Houmem Belkhechine 1 ; Moncef Bouaziz 2 ; Imed Boudabbous 3 ; Maurice Pouzet 4, 5

1 Faculté des Sciences de Gabès, Gabès, Tunisie
2 Institut des technologies médicales, Tunis, Tunisie
3 Institut Préparatoire aux Études d'Ingénieurs de Sfax, Sfax, Tunisie
4 ICJ, mathématiques, Université Claude-Bernard Lyon 1, 69622 Villeurbanne, France
5 Department of Mathematics and Statistics, The University of Calgary, Calgary, Alberta, Canada
@article{CRMATH_2010__348_13-14_703_0,
     author = {Houmem Belkhechine and Moncef Bouaziz and Imed Boudabbous and Maurice Pouzet},
     title = {Inversion dans les tournois},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {703--707},
     publisher = {Elsevier},
     volume = {348},
     number = {13-14},
     year = {2010},
     doi = {10.1016/j.crma.2010.06.022},
     language = {fr},
}
TY  - JOUR
AU  - Houmem Belkhechine
AU  - Moncef Bouaziz
AU  - Imed Boudabbous
AU  - Maurice Pouzet
TI  - Inversion dans les tournois
JO  - Comptes Rendus. Mathématique
PY  - 2010
SP  - 703
EP  - 707
VL  - 348
IS  - 13-14
PB  - Elsevier
DO  - 10.1016/j.crma.2010.06.022
LA  - fr
ID  - CRMATH_2010__348_13-14_703_0
ER  - 
%0 Journal Article
%A Houmem Belkhechine
%A Moncef Bouaziz
%A Imed Boudabbous
%A Maurice Pouzet
%T Inversion dans les tournois
%J Comptes Rendus. Mathématique
%D 2010
%P 703-707
%V 348
%N 13-14
%I Elsevier
%R 10.1016/j.crma.2010.06.022
%G fr
%F CRMATH_2010__348_13-14_703_0
Houmem Belkhechine; Moncef Bouaziz; Imed Boudabbous; Maurice Pouzet. Inversion dans les tournois. Comptes Rendus. Mathématique, Volume 348 (2010) no. 13-14, pp. 703-707. doi : 10.1016/j.crma.2010.06.022. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2010.06.022/

[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] H. Belkhechine; I. Boudabbous; J. Dammak Morphologie des tournois (1)-critiques, C. R. Acad. Sci. Paris Ser. I, Volume 345 (2007), pp. 663-666

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

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

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

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

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

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

[9] M. Pouzet 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] J.H. Schmerl; W.T. Trotter Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205

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

Cité par Sources :

Commentaires - Politique