Monday, 23 April 2007

co.combinatorics - Disjoint stable sets in tournaments

Let (V,A)(V,A) be a tournament. A subset of vertices VsubseteqV is stable if
there exists no vinVsetminusV such that Vcup{v} contains an inclusion-maximal transitive subtournament with source v.



(In other words, V is stable if for every transitive subtournament TsubseteqVcup{v} with vinT and (v,x)inA for all xinTsetminus{v}, there is a winV such that (w,x)inA for all xinT.)



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