[On the repartition of diamonds in a tournament]
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.
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.
Accepted:
Published online:
Houcine Bouchaala 1
@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}, }
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] Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358
[2] 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] Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66
[4] La reconstruction des tournois sans diamants, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 283-291
[5] 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:
Comments - Policy