|
|||||
|
|
A counterexample to a conjecture of Schwartz |
|
| Authors: | Felix Brandt Maria Chudnovsky Ilhee Kim Gaku Liu Sergey Norin Alex Scott Paul Seymour Stephan Thomassé |
| Institution: | 1. Technische Universit?t München, Munich, Germany 2. Columbia University, New York, NY, USA 3. Princeton University, Princeton, NJ, USA 4. McGill University, Montreal, QC, Canada 5. University of Oxford, Oxford, UK 6. Université Montpelier 2, Montpelier, France |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |