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

RésuméConsidérons un tournoi T=(S,A). À chaque partie X de S est associé le sous-tournoi T(X)=(X,A∩(X×X)) de T induit par X. On dit que le tournoi T abrite un tournoi T′ lorsque T′ est isomorphe à un sous-tournoi de T. Une partie X de S est un intervalle de T lorsque pour tous a,b∈X et x∈S∖X, (a,x)∈A si et seulement si (b,x)∈A. Par exemple, ∅, {x} (x∈S) et S sont des intervalles de T, appelés intervalles triviaux. Un tournoi, dont tous les intervalles sont triviaux, est indécomposable. En 2003, B.J. Latka a caractérisé la classe T des tournois indécomposables nʼabritant pas un certain tournoi W5 à 5 sommets. Dans cet article, nous nous intéressons, dans le cas dʼun tournoi indécomposable T, à lʼensemble W5(T) des sommets x∈S pour lesquels il existe une partie X de S telle que x∈X et T(X) est isomorphe à W5. Nous montrons que pour un tournoi indécomposable T nʼappartenant pas à la classe T, |W5(T)|⩾|S|−2, et que |W5(T)|⩾|S|−1 lorsque |S| est pair. À lʼaide dʼexemples, nous vérifions aussi que cet énoncé est optimal.

We consider a tournament T=(V,A). For each subset X of V is associated the subtournament T(X)=(X,A∩(X×X)) of T induced by X. We say that a tournament T′ embeds into a tournament T when T′ is isomorphic to a subtournament of T. A subset X of V is an interval of T provided that for a,b∈X and x∈V∖X, (a,x)∈A if and only if (b,x)∈A. For example, ∅, {x} (x∈V) and V are intervals of T, called trivial intervals. A tournament is indecomposable if all its intervals are trivial. In 2003, B.J. Latka characterized the class T of the indecomposable tournaments into which a certain tournament W5 on 5 vertices does not embed. In the case of an indecomposable tournament T, we study the set W5(T) of vertices x∈V for which there exists a subset X of V such that x∈X and T(X) is isomorphic to W5. We prove the following: for any indecomposable tournament T, if T∉T, then |W5(T)|⩾|V|−2 and |W5(T)|⩾|V|−1 if |V| is even. By giving examples, we also verify that this statement is optimal.