Ilhee Kim (김일희), A counterexample to a conjecture of Schwartz

A counterexample to a conjecture of Schwartz
Ilhee Kim (김일희)
Princeton University, Princeton, NJ, USA
2012/01/11 Wed 4PM-5PM
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 and so Schwartz’ conjecture is false. Our proof is non-constructive and uses the probabilistic method.
This is joint work with Felix Brandt, Gaku Liu, Maria Chudnovsky, Sergey Norin, Alex Scott, Paul Seymour, and Stephan Thomassé.


Comments are closed.