25
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$ Dec 17, 2009 at 16:16
  • $\begingroup$ 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). $\endgroup$ Dec 17, 2009 at 20:04

1 Answer 1

8
$\begingroup$

The statement is false. The existence of a counter-example using a probabilistic argument was shown by Chudnovsky, Kim, Liu, Norin, Scott, Seymour, and Thomasse.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.