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

RésuméSoit T=(S,A) un tournoi. Pour toute partie non vide X de S, on note T[X] le sous-tournoi de T induit par X. Par ailleurs, le dual de T est le tournoi T⋆ obtenu à partir de T en inversant tous ses arcs. Un tournoi T′ est demi-isomorphe à T s'il est isomorphe à T ou à T⋆. Étant donné un entier k⩾1, deux tournois T et T′, ayant le même ensemble de sommets S, sont (⩽k)-demi-isomorphes lorsque pour toute partie non vide X de S ayant au plus k éléments, les sous-tournois T[X] et T′[X] sont demi-isomorphes. Un tournoi T est (⩽k)-demi-reconstructible lorsque tout tournoi (⩽k)-demi-isomorphe à T lui est demi-isomorphe. En 1995, Y. Boudabbous et G. Lopez ont montré que les tournois sont (⩽7)-demi-reconstructibles. Dans cette Note, nous caractérisons les tournois (⩽k)-demi-reconstructibles pour 3⩽k⩽6. Pour citer cet article : Y. Boudabbous et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).

Let T=(V,A) be a tournament. For a non-empty subset X of V, we denote by T[X] the sub-tournament of T induced by X. The dual of T is the tournament T⋆ obtained from T by reversing all its arcs. A tournament T′ is half-isomorphic to T if it is isomorphic to T or T⋆. Given an integer k⩾1, two tournaments T, T′ defined on the same set V are (⩽k)-half-isomorphic if for every non-empty subset X of V with at most k elements, the sub-tournaments T[X] and T′[X] are half-isomorphic. A tournament T is (⩽k)-half-reconstructible provided that every tournament T′ which is (⩽k)-half-isomorphic to T is half-isomorphic to it. In 1995, Y. Boudabbous and G. Lopez showed that the tournaments are (⩽7)-half-reconstructible. In this Note, we characterize the (⩽k)-half-reconstructible tournameents for 3⩽k⩽6. To cite this article: Y. Boudabbous et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).