Logique
Sur la répartition des diamants dans un tournoi
[On the repartition of diamonds in a tournament]
Comptes Rendus. Mathématique, Volume 338 (2004) no. 2, pp. 109-112.

A tournament T=(V,A) is a directed graph such that for every x,yV, where xy, (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.

Un tournoi T=(S,A) est un graphe orienté tel que pour tous x,yS, avec xy, (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.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2003.11.018
Bouchaala, Houcine 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 = {Bouchaala, Houcine},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2003.11.018/}
}
TY  - JOUR
AU  - Bouchaala, Houcine
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2003.11.018/
DO  - 10.1016/j.crma.2003.11.018
LA  - fr
ID  - CRMATH_2004__338_2_109_0
ER  - 
%0 Journal Article
%A Bouchaala, Houcine
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2003.11.018/
%R 10.1016/j.crma.2003.11.018
%G fr
%F CRMATH_2004__338_2_109_0
Bouchaala, Houcine. 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. http://www.numdam.org/articles/10.1016/j.crma.2003.11.018/

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

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

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

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

[5] Lopez, G.; Rauzy, C. 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

Cited by Sources: