Let (V,A)(V,A) be a tournament. A subset of vertices V′subseteqV is stable if
there exists no vinVsetminusV′ 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 TsubseteqV′cup{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