[Critical and infinite tournaments]
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.
É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.
Accepted:
Published online:
Imed Boudabbous 1
@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}, }
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/
[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
Cited by Sources:
Comments - Policy