Logique
Tournois infinis et critiques
Comptes Rendus. Mathématique, Tome 336 (2003) no. 2, pp. 107-110.

Étant donné un tournoi T=(S,A), une partie X de S est un intervalle de T lorsque pour tous a,bX et xSX, (a,x)∈A si et seulement si (b,x)∈A. Par exemple, ∅, {x} (xS) 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 xS, T(S−{x}) est décomposable et lorsqu'il existe xyS 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 xyS 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,bX and xVX, (a,x)∈A if and only if (b,x)∈A. For example, ∅, {x} (xV) 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 xV, T(V−{x}) is decomposable and if there are xyV 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 xyV such that T and T(V−{x,y}) are isomorphic.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(03)00002-5
Boudabbous, Imed 1

1 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 = {Boudabbous, Imed},
     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},
     url = {http://archive.numdam.org/articles/10.1016/S1631-073X(03)00002-5/}
}
TY  - JOUR
AU  - Boudabbous, Imed
TI  - Tournois infinis et critiques
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 107
EP  - 110
VL  - 336
IS  - 2
PB  - Elsevier
UR  - http://archive.numdam.org/articles/10.1016/S1631-073X(03)00002-5/
DO  - 10.1016/S1631-073X(03)00002-5
LA  - fr
ID  - CRMATH_2003__336_2_107_0
ER  - 
%0 Journal Article
%A Boudabbous, Imed
%T Tournois infinis et critiques
%J Comptes Rendus. Mathématique
%D 2003
%P 107-110
%V 336
%N 2
%I Elsevier
%U http://archive.numdam.org/articles/10.1016/S1631-073X(03)00002-5/
%R 10.1016/S1631-073X(03)00002-5
%G fr
%F CRMATH_2003__336_2_107_0
Boudabbous, Imed. Tournois infinis et critiques. Comptes Rendus. Mathématique, Tome 336 (2003) no. 2, pp. 107-110. doi : 10.1016/S1631-073X(03)00002-5. http://archive.numdam.org/articles/10.1016/S1631-073X(03)00002-5/

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

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

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

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

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

Cité par Sources :