É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.
Accepté le :
Publié le :
@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 -
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] Primitivity is here ditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358
[2] Graphes indécomposables infinis, C. R. Acad. Sci. Paris Sér. I Math., Volume 318 (1994), pp. 499-503
[3] Relations infinies indécomposables critiques, C. R. Acad. Sci. Paris Sér. I Math., Volume 324 (1997), pp. 249-252
[4] Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205
[5] Graphs indecomposable with respect to the X-join, Discrete Math., Volume 6 (1973), pp. 281-298
Cité par Sources :
