Inversion dans les tournois

Houmem Belkhechine; Moncef Bouaziz; Imed Boudabbous; Maurice Pouzet

doi:10.1016/j.crma.2010.06.022

Logique/Combinatoire

Inversion dans les tournois

Présenté par : Jean-Yves Girard

Houmem Belkhechine ¹ ; Moncef Bouaziz ² ; Imed Boudabbous ³ ; Maurice Pouzet ^4,⁵

¹ Faculté des Sciences de Gabès, Gabès, Tunisie
² Institut des technologies médicales, Tunis, Tunisie
³ Institut Préparatoire aux Études d'Ingénieurs de Sfax, Sfax, Tunisie
⁴ ICJ, mathématiques, Université Claude-Bernard Lyon 1, 69622 Villeurbanne, France
⁵ Department of Mathematics and Statistics, The University of Calgary, Calgary, Alberta, Canada

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

Résumé
Abstract

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 $\frac{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}^{⩽ ω}$ .

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 $\frac{n - 1}{2} - \log_{2} n ⩽ i (n) ⩽ n - 3$ , for $n ⩾ 4$ . Let $I_{m}^{< ω}$ (resp. $I_{m}^{⩽ ω}$ ) be the class of finite (resp. at most countable) tournaments T such that $i (T) ⩽ m$ . The class $I_{m}^{< ω}$ is determined by finitely many obstructions. We give a morphological description of the members of $I_{1}^{< ω}$ and a description of the critical obstructions. We give an explicit description of a universal tournament of the class $I_{m}^{⩽ ω}$ .

Reçu le : 2010-02-27
Accepté le : 2010-06-25
Publié le : 2010-07-01

DOI : 10.1016/j.crma.2010.06.022

Affiliations des auteurs :

Houmem Belkhechine ¹ ; Moncef Bouaziz ² ; Imed Boudabbous ³ ; Maurice Pouzet ^{4, 5}

@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/

Bibliographie
Cité par

[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 $N_{5}$ , 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