Les tournois partiellement critiques

Sayar, Mohamed Yahia

doi:10.1016/j.crma.2008.02.002

Logique

Les tournois partiellement critiques

Présenté par : Jean-Yves Girard

Sayar, Mohamed Yahia ¹

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

Résumé
Abstract

Considérons un tournoi $T = (S, A)$ . À chaque partie non vide X de S est associé le sous-tournoi $T (X) = (X, A \cap (X \times X))$ de T induit par X. Une partie I de S est un intervalle de T si pour tous $a, b \in I$ et $x \in S ∖ I$ , $(a, x) \in A$ si et seulement si $(b, x) \in A$ . Par exemple, ∅, S et ${x}$ , où $x \in 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 \in 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 \in 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 \cap (X \times X))$ of T induced by X. A subset I of V is an interval of T provided that for every $a, b \in I$ and $x \in V ∖ I$ , $(a, x) \in A$ if and only if $(b, x) \in A$ . For instance, ∅, V and ${x}$ , where $x \in 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 \in 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 \in 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 : 2008-01-17
Accepté le : 2008-01-20
Publié le : 2008-03-01

DOI : 10.1016/j.crma.2008.02.002

Affiliations des auteurs :

Sayar, Mohamed Yahia ¹

¹ 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},
     publisher = {Elsevier},
     volume = {346},
     number = {5-6},
     year = {2008},
     doi = {10.1016/j.crma.2008.02.002},
     language = {fr},
     url = {http://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  - http://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 http://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. http://www.numdam.org/articles/10.1016/j.crma.2008.02.002/

Bibliographie
Cité par

[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 :