TY - JOUR
T1 - A counterexample to a conjecture of Schwartz
AU - Brandt, Felix
AU - Chudnovsky, Maria
AU - Kim, Ilhee
AU - Liu, Gaku
AU - Norin, Sergey
AU - Scott, Alex
AU - Seymour, Paul
AU - Thomassé, Stephan
PY - 2013/3
Y1 - 2013/3
N2 - In 1990, motivated by applications in the social sciences, Thomas Schwartz made a conjecture about tournaments which would have had numerous attractive consequences. In particular, it implied that there is no tournament with a partition A, B of its vertex set, such that every transitive subset of A is in the out-neighbour set of some vertex in B, and vice versa. But in fact there is such a tournament, as we show in this article, and so Schwartz' conjecture is false. Our proof is non-constructive and uses the probabilistic method.
AB - In 1990, motivated by applications in the social sciences, Thomas Schwartz made a conjecture about tournaments which would have had numerous attractive consequences. In particular, it implied that there is no tournament with a partition A, B of its vertex set, such that every transitive subset of A is in the out-neighbour set of some vertex in B, and vice versa. But in fact there is such a tournament, as we show in this article, and so Schwartz' conjecture is false. Our proof is non-constructive and uses the probabilistic method.
UR - http://www.scopus.com/inward/record.url?scp=84872607970&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872607970&partnerID=8YFLogxK
U2 - 10.1007/s00355-011-0638-y
DO - 10.1007/s00355-011-0638-y
M3 - Article
AN - SCOPUS:84872607970
SN - 0176-1714
VL - 40
SP - 739
EP - 743
JO - Social Choice and Welfare
JF - Social Choice and Welfare
IS - 3
ER -