# Disjoint stable sets in tournaments

Let $(V,A)$ be a tournament. A subset of vertices $V'\subseteq V$ is stable if there exists no $v\in V\setminus V'$ such that $V'\cup${$v$} contains an inclusion-maximal transitive subtournament with source $v$.

(In other words, $V'$ is stable if for every transitive subtournament $T\subseteq V'\cup${$v$} with $v\in T$ and $(v,x)\in A$ for all $x\in T\setminus${$v$}, there is a $w\in V'$ such that $(w, x)\in A$ for all $x\in T$.)

Is it true that no tournament contains two disjoint stable sets?

The statement would imply that every tournament contains a unique minimal stable set, which would have several appealing consequences in the social sciences. The statement is a weak version of a conjecture by Schwartz (see this paper and the references therein). Computer analysis has shown that there exists no counter-example with less than 13 vertices.

• This looks like an interesting question, but the end of the first paragraph after "i.e." is not very easy to parse grammatically. I'm also confused about whether "for every transitive subtournament... for all x \in T" is a definition of stable set or of inclusion-maximal subtournament. Can anyone clear this up for me? – Harrison Brown Dec 17 '09 at 16:16
• The statement after "i.e." is a restatement of what it means for V' to be stable. That is, it is saying that there is no v such that V' with {v} contains a transitive tournament with source v that is inclusion-maximal (since we can expand it with w). – Thomas Bloom Dec 17 '09 at 20:04