Logique

Tournois infinis et critiques

Jean-Yves Girard

Boudabbous, Imed¹

¹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, Tome 336 (2003) no. 2, pp. 107-110

Résumé (VO)

É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.

Abstract

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.

Détail

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

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