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.

Improve this question
$\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$
    – Harrison Brown
    Commented 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$
    – Thomas Bloom
    Commented Dec 17, 2009 at 20:04

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .