Tournois infinis et critiques

Imed Boudabbous

doi:10.1016/S1631-073X(03)00002-5

Logique

Tournois infinis et critiques

Présenté par : Jean-Yves Girard

Imed Boudabbous ¹

¹ Département des méthodes quantitatives, Faculté des sciences économiques et de gestion de Sfax, BP 1088, Université de Sfax, 3018 Sfax, Tunisie

Comptes Rendus. Mathématique, Volume 336 (2003) no. 2, pp. 107-110.

Résumé
Abstract

Étant donné un tournoi T=(S,A), une partie X de S est un intervalle de T lorsque pour tous a,b∈X et x∈S−X, (a,x)∈A si et seulement si (b,x)∈A. Par exemple, ∅, {x} (x∈S) et S sont des intervalles de T, appelés intervalles triviaux. Un tournoi dont tous les intervalles sont triviaux est dit indécomposable ; sinon, il est décomposable. Un tournoi T=(S,A) indécomposable est alors critique lorsque pour tout x∈S, T(S−{x}) est décomposable et lorsqu'il existe x≠y∈S tels que T(S−{x,y}) est indécomposable. Nous introduisons l'opération d'expansion qui nous permet de décrire un procédé de construction des tournois infinis et critiques. Il en découle que pour tout tournoi T=(S,A) infini et critique, il existe x≠y∈S tels que T et T(S−{x,y}) sont isomorphes.

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for every a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A. For example, ∅, {x} (x∈V) and V are intervals of T, called trivial intervals. A tournament all the intervals of which are trivial is called indecomposable; otherwise, it is decomposable. An indecomposable tournament T=(V,A) is then said to be critical if for each x∈V, T(V−{x}) is decomposable and if there are x≠y∈V such that T(V−{x,y}) is indecomposable. We introduce the operation of expansion which allows us to describe a process of construction of critical and infinite tournaments. It follows that, for every critical and infinite tournament T=(V,A), there are x≠y∈V such that T and T(V−{x,y}) are isomorphic.

Reçu le : 2002-11-25
Accepté le : 2002-12-02
Publié le : 2003-01-15

DOI : 10.1016/S1631-073X(03)00002-5

Affiliations des auteurs :

Imed Boudabbous ¹

¹ Département des méthodes quantitatives, Faculté des sciences économiques et de gestion de Sfax, BP 1088, Université de Sfax, 3018 Sfax, Tunisie

@article{CRMATH_2003__336_2_107_0,
     author = {Imed Boudabbous},
     title = {Tournois infinis et critiques},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {107--110},
     publisher = {Elsevier},
     volume = {336},
     number = {2},
     year = {2003},
     doi = {10.1016/S1631-073X(03)00002-5},
     language = {fr},
}

TY  - JOUR
AU  - Imed Boudabbous
TI  - Tournois infinis et critiques
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 107
EP  - 110
VL  - 336
IS  - 2
PB  - Elsevier
DO  - 10.1016/S1631-073X(03)00002-5
LA  - fr
ID  - CRMATH_2003__336_2_107_0
ER  -

%0 Journal Article
%A Imed Boudabbous
%T Tournois infinis et critiques
%J Comptes Rendus. Mathématique
%D 2003
%P 107-110
%V 336
%N 2
%I Elsevier
%R 10.1016/S1631-073X(03)00002-5
%G fr
%F CRMATH_2003__336_2_107_0

Imed Boudabbous. Tournois infinis et critiques. Comptes Rendus. Mathématique, Volume 336 (2003) no. 2, pp. 107-110. doi : 10.1016/S1631-073X(03)00002-5. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(03)00002-5/

Bibliographie
Cité par

[1] A. Ehrenfeucht; G. Rozenberg Primitivity is here ditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358

[2] P. Ille Graphes indécomposables infinis, C. R. Acad. Sci. Paris Sér. I Math., Volume 318 (1994), pp. 499-503

[3] L. Rigollet; S. Thomassé Relations infinies indécomposables critiques, C. R. Acad. Sci. Paris Sér. I Math., Volume 324 (1997), pp. 249-252

[4] 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

[5] D.P. Sumner Graphs indecomposable with respect to the X-join, Discrete Math., Volume 6 (1973), pp. 281-298

Cité par Sources :

Commentaires - Politique