Les tournois partiellement critiques

Mohamed Yahia Sayar

doi:10.1016/j.crma.2008.02.002

Logique

Les tournois partiellement critiques
[Partially critical tournaments]

Jean-Yves Girard

Mohamed Yahia Sayar ¹

¹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, Volume 346 (2008) no. 5-6, pp. 249-252

Résumé (Original language)
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.

Article information
Cite this article

Received: 2008-01-17
Accepted: 2008-01-20
Published online: 2008-03-01

DOI: 10.1016/j.crma.2008.02.002

Author's affiliations:

Mohamed Yahia Sayar ¹

¹ Faculté des sciences de Sfax, département de mathématiques, route de la soukra km 4, BP 802, 3018 Sfax, Tunisie

Mohamed Yahia Sayar. Les tournois partiellement critiques. Comptes Rendus. Mathématique, Volume 346 (2008) no. 5-6, pp. 249-252. doi: 10.1016/j.crma.2008.02.002

@article{CRMATH_2008__346_5-6_249_0,
     author = {Mohamed Yahia Sayar},
     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},
}

TY  - JOUR
AU  - Mohamed Yahia Sayar
TI  - Les tournois partiellement critiques
JO  - Comptes Rendus. Mathématique
PY  - 2008
SP  - 249
EP  - 252
VL  - 346
IS  - 5-6
PB  - Elsevier
DO  - 10.1016/j.crma.2008.02.002
LA  - fr
ID  - CRMATH_2008__346_5-6_249_0
ER  -

%0 Journal Article
%A Mohamed Yahia Sayar
%T Les tournois partiellement critiques
%J Comptes Rendus. Mathématique
%D 2008
%P 249-252
%V 346
%N 5-6
%I Elsevier
%R 10.1016/j.crma.2008.02.002
%G fr
%F CRMATH_2008__346_5-6_249_0

References
Cited by

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

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

[3] J.H. Schmerl; W.T. Trotter Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205

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

Cited by Sources:

Comments - Policy