Skip to main content

A counterexample to a conjecture of Schwartz

Author(s): Brandt, Felix; Chudnovsky, Maria; Kim, Ilhee; Liu, Gaku; Norin, Sergey; et al

To refer to this page use:
Abstract: 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.
Publication Date: Mar-2013
Electronic Publication Date: 17-Jan-2012
Citation: Brandt, Felix, Chudnovsky, Maria, Kim, Ilhee, Liu, Gaku, Norin, Sergey, Scott, Alex, Seymour, Paul, Thomassé, Stephan. (2013). A counterexample to a conjecture of Schwartz. Social Choice and Welfare, 40 (3), 739 - 743. doi:10.1007/s00355-011-0638-y
DOI: doi:10.1007/s00355-011-0638-y
ISSN: 0176-1714
EISSN: 1432-217X
Pages: 739 - 743
Type of Material: Journal Article
Journal/Proceeding Title: Social Choice and Welfare
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.