Monday 23 April 2007

co.combinatorics - Disjoint stable sets in tournaments

Let $(V,A)$ be a tournament. A subset of vertices $V'subseteq V$ is stable if
there exists no $vin Vsetminus 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 $Tsubseteq V'cup${$v$} with $vin T$ and $(v,x)in A$ for all $xin Tsetminus${$v$}, there is a $win V'$ such that $(w, x)in A$ for all $xin 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.

No comments:

Post a Comment