no. 5-6
Logique
Les tournois partiellement critiques
Présenté par : Jean-Yves Girard
Sayar, Mohamed Yahia1
1 Faculté des sciences de Sfax, département de mathématiques, route de la soukra km 4, BP 802, 3018 Sfax, Tunisie
Comptes Rendus. Mathématique, Tome 346 (2008) no. 5-6, pp. 249-252

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.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2008.02.002

Sayar, Mohamed Yahia 1

1 Faculté des sciences de Sfax, département de mathématiques, route de la soukra km 4, BP 802, 3018 Sfax, Tunisie 
@article{CRMATH_2008__346_5-6_249_0,
     author = {Sayar, Mohamed Yahia},
     title = {Les tournois partiellement critiques},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {249--252},
     year = {2008},
     publisher = {Elsevier},
     volume = {346},
     number = {5-6},
     doi = {10.1016/j.crma.2008.02.002},
     language = {fr},
     url = {https://www.numdam.org/articles/10.1016/j.crma.2008.02.002/}
}
TY  - JOUR
AU  - Sayar, Mohamed Yahia
TI  - Les tournois partiellement critiques
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 249
EP  - 252
VL  - 346
IS  - 5-6
PB  - Elsevier
UR  - https://www.numdam.org/articles/10.1016/j.crma.2008.02.002/
DO  - 10.1016/j.crma.2008.02.002
LA  - fr
ID  - CRMATH_2008__346_5-6_249_0
ER  - 
%0 Journal Article
%A Sayar, Mohamed Yahia
%T Les tournois partiellement critiques
%J Comptes Rendus. Mathématique
%D 2008
%P 249-252
%V 346
%N 5-6
%I Elsevier
%U https://www.numdam.org/articles/10.1016/j.crma.2008.02.002/
%R 10.1016/j.crma.2008.02.002
%G fr
%F CRMATH_2008__346_5-6_249_0
Sayar, Mohamed Yahia. Les tournois partiellement critiques. Comptes Rendus. Mathématique, Tome 346 (2008) no. 5-6, pp. 249-252. doi: 10.1016/j.crma.2008.02.002

[1] A. Breiner, J. Deogun, P. Ille, Partially critical indecomposable graphs, 2006, soumis à Contributions to Discrete Mathematics

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

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

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

Cité par Sources :