Comptes Rendus
no. 2
Logique
Sur la répartition des diamants dans un tournoi

Présenté par : Jean-Yves Girard

Houcine Bouchaala1
1 Université de Sfax, Institut préparatoire aux études d'ingénieurs de Sfax, département de la préparation mathématiques-physique, BP 805, 3000 Sfax, Tunisie
Comptes Rendus. Mathématique, Volume 338 (2004) no. 2, pp. 109-112.

Un tournoi T=(S,A) est un graphe orienté tel que pour tous x,y∈S, avec x≠y, (x,y)∈A si et seulement si (y,x)∉A. Par exemple, le 3-cycle est le tournoi ({1,2,3}, {(1,2),(2,3),(3,1)}). À l'isomorphisme près, il existe deux tournois à 4 sommets et contenant un seul 3-cycle, que nous appelons diamants. Nous montrons que pour tout tournoi T défini sur n⩾9 sommets, ou bien T contient au moins 2n−6 diamants ou bien le nombre de diamants contenus dans T est égal à 0, n−3 ou 2n−8. Suite à la caractérisation des tournois sans diamants due à Gnanvo et Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) et à Lopez et Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), nous étudions la morphologie des tournois définis sur n⩾5 sommets et qui contiennent exactement n−3 ou 2n−8 diamants.

A tournament T=(V,A) is a directed graph such that for every x,y∈V, where x≠y, (x,y)∈A if and only if (y,x)∉A. For example, the 3-cycle is the tournament ({1,2,3}, {(1,2),(2,3),(3,1)}). Up to an isomorphism, there are two tournaments with 4 vertices and containing an unique 3-cycle which we call diamonds. We prove that for any tournament T defined on n⩾9 vertices, either T contains at least 2n−6 diamonds or the number of diamonds contained in T is equal to 0, n−3 or 2n−8. Following the characterization of the tournaments without diamonds due to Gnanvo and Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) and to Lopez and Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), we study the morphology of the tournaments defined on n⩾5 vertices and which contain exactly n−3 or 2n−8 diamonds.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2003.11.018
Houcine Bouchaala 1

1 Université de Sfax, Institut préparatoire aux études d'ingénieurs de Sfax, département de la préparation mathématiques-physique, BP 805, 3000 Sfax, Tunisie 
@article{CRMATH_2004__338_2_109_0,
     author = {Houcine Bouchaala},
     title = {Sur la r\'epartition des diamants dans un tournoi},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {109--112},
     publisher = {Elsevier},
     volume = {338},
     number = {2},
     year = {2004},
     doi = {10.1016/j.crma.2003.11.018},
     language = {fr},
}
TY  - JOUR
AU  - Houcine Bouchaala
TI  - Sur la répartition des diamants dans un tournoi
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 109
EP  - 112
VL  - 338
IS  - 2
PB  - Elsevier
DO  - 10.1016/j.crma.2003.11.018
LA  - fr
ID  - CRMATH_2004__338_2_109_0
ER  - 
%0 Journal Article
%A Houcine Bouchaala
%T Sur la répartition des diamants dans un tournoi
%J Comptes Rendus. Mathématique
%D 2004
%P 109-112
%V 338
%N 2
%I Elsevier
%R 10.1016/j.crma.2003.11.018
%G fr
%F CRMATH_2004__338_2_109_0
Houcine Bouchaala. Sur la répartition des diamants dans un tournoi. Comptes Rendus. Mathématique, Volume 338 (2004) no. 2, pp. 109-112. doi : 10.1016/j.crma.2003.11.018. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2003.11.018/

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

[2] R. Fraı̈ssé L'intervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture d'une relation (M. Pouzet; D. Richard, eds.), Orders, Description and Roles, North-Holland, 1984, pp. 313-342

[3] T. Gallai Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[4] C. Gnanvo; P. Ille La reconstruction des tournois sans diamants, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 283-291

[5] G. Lopez; C. Rauzy Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Sous-tournois isomorphes à W5 dans un tournoi indécomposable

Houmem Belkhechine; Imed Boudabbous; Kaouthar Hzami

C. R. Math (2012)

Demi-isomorphie, autodualité et tournois non fortement connexes finis

Moncef Bouaziz; Youssef Boudabbous

C. R. Math (2002)

Les tournois (⩽k)-demi-reconstructibles pour k⩽6

Youssef Boudabbous; Abderrahim Boussaïri; Abdelhak Chaïchaâ; ...

C. R. Math (2008)