Les tournois partiellement critiques

RésuméConsidérons un tournoi T=(S,A). À chaque partie non vide X de S est associé le sous-tournoi T(X)=(X,A∩(X×X)) de T induit par X. Une partie I de S est un intervalle de T si pour tous a,b∈I et x∈S∖I, (a,x)∈A si et seulement si (b,x)∈A. Par exemple, ∅, S et {x}, où x∈S, sont des intervalles de T appelés triviaux. Un tournoi est indécomposable si tous ses intervalles sont triviaux ; sinon il est décomposable. Soit T=(S,A) un tournoi indécomposable. Le tournoi T est critique si T(S∖{x}) est décomposable pour tout x∈S. Il est partiellement critique s'il existe une partie stricte X de S telle que |X|⩾3, T(X) est indécomposable et pour tout x∈S∖X, T(S∖{x}) est décomposable. Les tournois critiques ont été caractérisés par Schmerl et Trotter (1993). Nous caractérisons les tournois partiellement critiques. Pour citer cet article : M.Y. Sayar, C. R. Acad. Sci. Paris, Ser. I 346 (2008).

Given a tournament T=(V,A), with each subset X of V is associated the subtournament T(X)=(X,A∩(X×X)) of T induced by X. A subset I of V is an interval of T provided that for every a,b∈I and x∈V∖I, (a,x)∈A if and only if (b,x)∈A. For instance, ∅, V and {x}, where x∈S, are intervals of T called trivial. A tournament is indecomposable if all its intervals are trivial; otherwise it is decomposable. Let T=(V,A) be an indecomposable tournament. The tournament T is critical if T(S∖{x}) is decomposable for every x∈S. It is partially critical if there exists a proper subset X of V such that |X|⩾3, T(X) is indecomposable and for every x∈V∖X, T(V∖{x}) is decomposable. The critical tournaments were characterized by Schmerl and Trotter (1993). We characterize the partially critical tournaments. To cite this article: M.Y. Sayar, C. R. Acad. Sci. Paris, Ser. I 346 (2008).