Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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